- PHƢƠNG PHÁP “QUỸ ĐẠO” VÀ ỨNG DỤNG VÀO GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP. - 1.1 Bài toán đếm trong toán tổ hợp. - 1.3 Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán THPT. - Chương 2 Vận dụng phương pháp “quỹ đạo” vào giải một số bài toán tổ hợp 15 2.1 Phương pháp “quỹ đạo. - 2.1.1 Quan niệm về “quỹ đạo. - 2.1.2 Một số tính chất về “quỹ đạo. - 2.2.1 Bài toán sắp hàng. - 2.2.2 Bài toán bỏ phiếu. - 2.2.4 Một số bài toán khác. - 25 2.3 Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo. - Một trong các phương pháp có hiệu quả để giải một số bài toán tổ hợp là phương pháp “quỹ đạo”. - Ý tưởng của phương pháp “quỹ đạo” là chỉ ra cách giải thích hình học để đưa ra lời giải cho bài toán tổ hợp, mà chủ yếu là các bài toán tổ hợp đếm các đường đi (hay số các “quỹ đạo”) theo một tính chất xác định nào đó (hay còn gọi là phương pháp quy các bài toán đếm về các bài toán đếm số đường đi trên lưới nguyên).. - Phương pháp “quỹ đạo” không chỉ ứng dụng được vào giải một số bài toán tổ hợp liên quan đến lưới nguyên mà còn có thể vận dụng được để đưa ra lời giải cho một số bài toán về dãy số. - ta có thể vận dụng tư tưởng của phương pháp “quỹ đạo” để đưa ra các thuật toán “tốt” hơn.. - Ý tưởng toán học của phương pháp “quỹ đạo” trong việc tìm lời giải cho bài toán đếm của toán tổ hợp.. - Đưa ra ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo” thông qua thuật toán đường đi của con Robot.. - Bài toán đếm trong toán tổ hợp.. - Vận dụng phương pháp “quỹ đạo” vào giải một số bài toán tổ hợp. - Phương pháp “quỹ đạo”.. - Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo”.. - a k ) gồm k phần tử (có thể trùng nhau) của A. - Trong bài toán đếm, một số phần tử có thể giống nhau. - Hàm sinh có thể được áp dụng trong các bài toán đếm. - 1 cách chọn 0 phần tử.. - 1 cách chọn 1 phần tử.. - 0 cách chọn 2 phần tử trở lên.. - 2 cách chọn 1 phần tử.. - 1 cách chọn 2 phần tử.. - 0 cách chọn 3 phần tử trở lên.. - 2.1 Phương pháp “quỹ đạo”. - Trong mục này chúng tôi sẽ trình bày về phương pháp “quỹ đạo” và một số tính chất liên quan.. - 2.1.1 Quan niệm về “quỹ đạo”. - Phương pháp chứng minh một công thức tổ hợp bởi số đường đi ngắn nhất gọi là phương pháp “quỹ đạo”.. - Ta gọi một “quỹ đạo” từ gốc tọa độ O(0, 0) đến điểm A(m, n) là đường gấp khúc nối các điểm O(0, 0). - 2.1.2 Một số tính chất về “quỹ đạo”. - Khi đó số các “quỹ đạo” từ A đến B cắt trục Ox hoặc có điểm chung với Ox bằng số các “quỹ đạo” từ A 0 đến B.. - “quỹ đạo” T từ A đến B cắt Ox tương ứng với một “quỹ đạo” xác định từ A 0 đến B. - Ngược lại mỗi một “quỹ đạo” từ A 0 đến B tương ứng với một và chỉ một. - “quỹ đạo” từ A đến B cắt Ox (lấy đoạn “quỹ đạo” từ A 0 đến B đến điểm gặp đầu tiên và lấy đối xứng đoạn này qua Ox). - Như vậy ta đã thiết lập được song ánh từ tập hợp các “quỹ đạo” từ A đến B cắt Ox vào tập hợp các “quỹ đạo” từ A 0 đến B. - Giả sử S[m, n] là số tất cả các “quỹ đạo” nối điểm O(0, 0) với điểm A(m, n). - Giả sử “quỹ đạo” gồm p đoạn hướng lên trên và q đoạn hướng xuống dưới. - Vì “quỹ đạo” hoàn toàn được xác định nếu chỉ ra được những đoạn nào hướng lên trên nên số “quỹ đạo” từ điểm O(0, 0) đến điểm A(m, n) bằng C. - Khi đó số “quỹ đạo” từ điểm O(0, 0) đến điểm A(m, n) luôn có đỉnh trên trục hoành (trừ điểm O) bằng. - Chú ý rằng tất cả các “quỹ đạo” nối điểm O(0, 0) với điểm A(m, n) và không cắt trục hoành phải đi qua điểm P (1, 1). - Số “quỹ đạo” đi từ P đến A bằng S[m − 1, n − 1]. - Số “quỹ đạo” đi từ điểm P đến điểm A và cắt trục hoành bằng số “quỹ đạo” đi từ điểm P 0 (1, −1) đến điểm A (theo Mệnh đề 2.1.2), nghĩa là bằng S[m − 1, n + 1]. - Do đó số “quỹ đạo” cần tìm bằng. - Khi đó trong C n 2n “quỹ đạo” nối điểm O(0, 0) với điểm T có. - Đúng B 2n−2 “quỹ đạo” nằm trên trục hoành và không có điểm chung với trục hoành (trừ các điểm O và T. - Đúng B 2n “quỹ đạo” không có đỉnh nằm dưới trục hoành.. - Chú ý rằng tất cả các “quỹ đạo” nối điểm O với điểm T nằm trên trục hoành và không có điểm chung khác với trục hoành nhất thiết. - Theo Mệnh đề 2.1.3, số “quỹ đạo” nối điểm O với điểm T 1 và không cắt trục hoành bằng. - Ta xét “quỹ đạo” nối điểm O với T và không có đỉnh nằm dưới trục hoành.. - Số “quỹ đạo” nối điểm O với điểm T và không có đỉnh nằm dưới trục hoành bằng số “quỹ đạo” nối điểm O 1 với điểm T và nằm trên trục O 1 X 1 . - Số “quỹ đạo” này bằng. - Giả sử B 2k,2n là số “quỹ đạo” nối điểm O với điểm T (2n, 0) có 2k cạnh nằm trên trục hoành và 2n − 2k cạnh còn lại nằm dưới trục hoành (k = 0, 1. - Đối với các “quỹ đạo” không có đỉnh nằm dưới trục hoành đã được xét trong Mệnh đề 2.1.4, ta có B 2n,2n = B 2n . - Tổng số các “quỹ đạo” nối điểm O với điểm T bằng (n + 1)B 2n , từ đó suy ra. - Bài toán 2.2.1. - Ta gọi đường gấp khúc như vậy là một “quỹ đạo”, tương ứng với cách sắp hàng của người mua vé. - Tổng số các “quỹ đạo” bằng C n n+m. - Chú ý rằng các “quỹ đạo” tương ứng với cách sắp hàng của người mua vé để không ai phải chờ trả tiền thừa sẽ không cắt đường thẳng y = −1.. - Ta sẽ chứng minh rằng số “quỹ đạo” cắt đường y = −1 bằng C n+1 m+n. - Với mỗi “quỹ đạo” Q cắt đường thẳng y = −1 hay có một điểm chung với nó ta thiết lập tương ứng giữa Q với một “quỹ đạo” Q 0 theo cách sau:. - Toàn bộ “quỹ đạo” Q 0 kết thúc ở điểm A 0 m+n (m + n, m − n − 2) là ảnh của điểm A m+n. - Sự tương ứng đã thiết lập là một - một (hay là song ánh), do đó số “quỹ đạo” cắt đường thẳng y = −1 bằng số đường gấp khúc nối điểm O với điểm A 0 m+n . - Vậy số “quỹ đạo” cắt đường thẳng y = −1 bằng C n+1 m+n. - Từ kết quả ở 2) suy ra rằng số “quỹ đạo” tương ứng với cách sắp hàng của người mua vé để không có người nào phải chờ trả tiền thừa bằng:. - Gọi u là một phần tử của U . - Thật vậy, trong trường hợp này bài toán đưa về việc tính số “quỹ đạo” từ điểm O(0, 0) đến điểm A m+n (m + n, n − m) không cắt đường thẳng y = −(p + 1). - Khi đó số “quỹ đạo” cắt đường thẳng đó bằng số “quỹ đạo” từ điểm B(0, −2(p + 1)) đến điểm A m+n (n + m, n − m), nghĩa là bằng C p+n+1 m+n = C m−p−1 m+n (theo hệ thức C k n = C n−k n. - Số “quỹ đạo” cần tìm của bài toán là C n m+n − C m−p−1 m+n. - Bài toán 2.2.2. - Ta xét “quỹ đạo” với các điểm O S 1. - Rõ ràng mỗi cách bỏ phiếu tương ứng với một “quỹ đạo” xác định. - Mỗi “quỹ đạo” gồm a + b đoạn thẳng, trong đó có a đoạn hướng lên trên. - “quỹ đạo” bằng C a a+b . - Ứng cử viên A luôn dẫn đầu nếu “quỹ đạo” tương ứng đi qua điểm (1, 1) và không cắt trục hoành. - Số “quỹ đạo” như vậy bằng. - Bài toán 2.2.3 (Quy tắc Pascal). - Bài toán Pascal có thể giải bằng phương pháp “quỹ đạo” như sau:. - Phương pháp “quỹ đạo”. - Bài toán 2.2.4. - Bài toán 2.2.5. - Bài toán 2.2.6. - Bài toán 2.2.7 (Bài tuyển chọn Đội tuyển Việt Nam dự IMO, 2003). - Bài toán 2.2.8 (Bài toán “Dyck path. - Bài toán 2.2.9. - Chúng ta đưa về bài toán đường đi quen thuộc. - Bài toán 2.2.10. - Bài toán 2.2.11. - 2.3 Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo”. - Phương án 2: Vận dụng ý tưởng của khái niệm “quỹ đạo” và phương pháp. - “quỹ đạo” ta chọn phương án: Robot được thiết kế sao cho nó có thể di chuyển sang phải hoặc lên trên (tức là chỉ được phép di chuyển theo hướng dương của các trục tọa độ). - Trong đó việc vận dụng phương pháp “quỹ đạo” cho ta ý tưởng tốt để đưa ra các thuật toán tối ưu.. - Trong các phương pháp giải toán tổ hợp, tên gọi Phương pháp “quỹ đạo”. - ta có thể vận dụng tư tưởng của phương pháp “quỹ đạo” để đưa ra các thuật toán “tốt” hơn. - Trình bày phương pháp “quỹ đạo”, các tính chất “quỹ đạo” và vận dụng phương pháp “quỹ đạo” vào giải một số bài toán tổ hợp, bài toán về dãy số (ví dụ như các bài toán 2.2.8. - Trình bày ý nghĩa của khái niệm “quỹ đạo” và tính ứng dụng của phương pháp “quỹ đạo” thông qua bài toán, thuật toán đường đi của Robot, tìm đường đi tối ưu của Robot...
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt