Luận văn Thạc sĩ Toán học: Phương pháp đếm hai lần và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:68

Thêm vào BST

Báo xấu

13
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phương pháp đếm hai lần “double counting” đã được nhóm tác giả Law Ka Ho, Leung Tat Wing và Li Kim Jin đăng tải trên tạp chí Mathematical Excalibur (Volume 13, Number 4, 2008) đưa ra các minh họa sinh động cho việc vận dụng phương pháp đếm hai lần vào giải một vài đề thi toán quốc tế. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp đếm hai lần và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐỖ THỊ THÚY HÒA PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- ĐỖ THỊ THÚY HÒA PHƢƠNG PHÁP ĐẾM HAI LẦN VÀ ỨNG DỤNG Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. Trịnh Thanh Hải THÁI NGUYÊN - 2019
i Mục lục Mở đầu 1 1 Kiến thức chuẩn bị 3 1.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Cơ sở của phương pháp đếm . . . . . . . . . . . . . . 3 1.1.2 Hoán vị, chỉnh hợp và tổ hợp . . . . . . . . . . . . . 9 1.2 Một số phương pháp giải bài toán đếm của toán tổ hợp . . . 13 1.2.1 Sử dụng công thức bao hàm và loại trừ . . . . . . . . 13 1.2.2 Sử dụng phương pháp hệ thức truy hồi . . . . . . . . 16 1.2.3 Sử dụng phương pháp liệt kê các trường hợp . . . . . 18 1.2.4 Xây dựng song ánh giải một số bài toán tổ hợp . . . 21 2 Vận dụng phương pháp đếm hai lần vào giải bài toán đếm 25 2.1 Ý tưởng của phương pháp đếm hai lần . . . . . . . . . . . . 25 2.2 Một số nguyên lý, tính chất của toán tổ hợp thường được vận dụng vào giải bài toán đếm . . . . . . . . . . . . . . . . . . 29 2.3 Vận dụng phương pháp đếm hai lần vào giải các bài toán đếm 32 2.3.1 Đếm số tập con, số cặp và số hoán vị . . . . . . . . . 32 2.3.2 Phương pháp đếm hai lần và đồ thị hữu hạn . . . . . 47 2.3.3 Phương pháp ma trận liên thuộc . . . . . . . . . . . 51 2.4 Một số bài toán đề nghị . . . . . . . . . . . . . . . . . . . . 62 Kết luận 63 Tài liệu tham khảo 64
1 Mở đầu Toán tổ hợp là một bài toán khó, thường xuất hiện trong các kì thi học sinh giỏi cấp tỉnh, cấp quốc gia và quốc tế. Chính vì vậy toán tổ hợp luôn dành được sự quan tâm rất lớn từ các bạn học sinh, các thầy, cô giáo và các nhà toán học. Mặc dù vậy, tài liệu cho toán tổ hợp dành cho học sinh giỏi ở Việt nam vẫn còn rất ít và hạn chế. Phương pháp đếm hai lần “double counting” đã được nhóm tác giả Law Ka Ho, Leung Tat Wing và Li Kim Jin đăng tải trên tạp chí Mathematical Excalibur (Volume 13, Number 4, 2008) đưa ra các minh họa sinh động cho việc vận dụng phương pháp đếm hai lần vào giải một vài đề thi toán quốc tế. Xuất phát từ thực tế trên và với mục đích tích lũy thêm các kiến thức về cách giải các bài toán đếm của toán tổ hợp với phương pháp đếm hai lần và vận dụng vào giải một số bài toán đếm trong các đề thi học sinh giỏi trong nước và quốc tế làm tư liệu cho công việc giảng dạy của bản thân, tôi đã lựa chọn hướng nghiên cứu vận dụng phương pháp đến hai lần vào giải một số bài toán đếm. Luận văn tập trung vào hoàn thành các nhiệm vụ chính sau: • Tìm hiểu bài toán đếm của toán tổ hợp và các nguyên lý, tính chất của toán tổ hợp thường được vận dụng để đưa ra lời giải cho các bài toán đếm. • Cơ sở toán học của phương pháp “Đếm hai lần” trong việc tìm lời giải cho bài toán đếm của toán tổ hợp. • Sưu tầm một số bài toán, đề thi và bài toán đếm của toán tổ hợp dành cho học sinh giỏi.
2 • Đưa ra lời giải bằng cách vận dụng phương pháp “Đếm hai lần” cho một số bài toán đếm dành cho học sinh giỏi. Ngoài ra luận văn cũng đưa ra các cách giải khác nhau của cùng một bài toán đếm và so sánh những phương pháp giải đó với việc vận dụng phương pháp đếm hai lần để có những nhận xét thú vị. Thái Nguyên, ngày 31 tháng 3 năm 2019 Tác giả luận văn Đỗ Thị Thúy Hòa
3 Chương 1 Kiến thức chuẩn bị 1.1 Đặt vấn đề Như chúng ta biết, các khái niệm hoán vị, chỉnh hợp, tổ hợp được hình thành từ các phép đếm. Các khái niệm này ra đời giúp chúng ta trình bày bài toán đếm đơn giản hơn. Tuy nhiên, khi gặp các bài chứng minh các đẳng thức liên quan đến hoán vị, chỉnh hợp, tổ hợp thì chúng ta thường sử dụng các biến đổi đại số hoặc khai triển nhị thức Newton để chứng minh. Do đó, việc chứng minh các bài toán tổ hợp và các khái niệm của nó không có mối quan hệ nào. Điều này ít nhiều làm mất đi vẻ đẹp của các khái niệm toán học nói chung và các khái niệm về hoán vị, chỉnh hợp nói riêng. Trong nội dung chương 1 của luận văn, tôi sẽ giới thiệu cách chứng minh các bài toán tổ hợp bằng phương pháp đếm. Nội dung mục này được tham khảo chủ yếu trong tài liệu [1] và một số bài toán hay trong các đề thi học sinh giỏi được tác giả sưu tầm và trình bày. 1.1.1 Cơ sở của phương pháp đếm Một bài toán tổ hợp thường liên quan mật thiết với việc “đếm” số khả năng thực hiện một hành động nào đó. Phép đếm có hai quy tắc cơ bản là phép cộng và phép nhân. Quy tắc 1.1 (Quy tắc cộng). Giả sử có k công việc T1 , T2 , . . . , Tk . Các việc này có thể làm tương ứng bằng n1 , n2 , . . . , nk cách và giả sử không có hai
4 việc nào có thể làm đồng thời. Khi đó số cách làm một trong k việc đó là n1 + n2 + · · · + nk . Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp như sau: Cho n tập hợp A1 , A2 , . . . , An là các tập hợp hữu hạn đôi một rời nhau, tức là ∀1 ≤ i, j ≤ n, Ai ∩ Aj = ∅ nếu i 6= j. Khi đó số cách chọn a1 , n S hoặc a2 , . . . , hoặc an sẽ bằng số cách chọn phần tử a thuộc Ak và bằng k=1 n S n P | Ak | = |Ak |. k=1 k Ví dụ 1.1. Trong một tiết tự học, trên bàn giáo viên có 10 quyển sách tiếng Anh, 10 quyển bài tập Toán và 5 quyển bài tập Hóa. Hỏi có bao nhiêu cách chọn một quyển sách? Chứng minh. Gọi A1 , A2 , A3 lần lượt là tập các quyển sách tiếng Anh, bài tập Toán và bài tập Hóa. Khi đó, có 10 cách chọn một quyển sách tiếng Anh, tức là |A1 | = 10. Có 10 cách chọn một quyển bài tập Toán, tức là |A2 | = 10. Có 5 cách chọn một quyển bài tập Hóa, nghĩa là |A3 | = 5. Vậy, theo quy tắc cộng, số cạch chọn một quyển sách là |A1 | + |A2 | + |A3 | = 10 + 10 + 5 = 25. Bản chất toán học của quy tắc cộng là công thức tính số phần tử của hợp n tập hợp hữu hạn đôi một không giao nhau. Tuy nhiên trong nhiều bài toán tổ hợp, chúng ta phải tính số phần tử của hợp n tập hợp bất kì (không nhất thiết rời nhau). Khi đó, ta có quy tắc cộng cho số phần tử của hợp của n tập hợp bất kỳ, thường được gọi là công thức bao hàm và loại trừ. Định lý 1.1 (Công thức bao hàm và loại trừ). Cho n ≥ 2 tập hợp hữu hạn
5 A1 , . . . , An . Khi đó ta có n X X X |A1 ∪ A2 ∪ . . . ∪ An | = |Ai | − |Ai ∩ Ak | + |Ai ∩ Aj ∩ Ak | i=1 1≤i
6 a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn a3 , . . . Cuối cùng với mỗi cách chọn a1 , a2 , . . . , an−1 có mn cách chọn đối tượng an . Như vậy ta có m1 .m2 . . . mn−1 .mn cách chọn đối tượng a1 , rồi chọn đối tượng a2 , rồi đến a3 , . . . , rồi đến an . Tương tự như quy tắc cộng, quy tắc nhân phát biểu bằng ngôn ngữ tập hợp như sau: Giả sử có n tập hợp hữu hạn A1 , A2 , . . . , An . Khi đó, số cách chọn (S) bộ gồm n phần tử (a1 , a2 , . . . an ) với ai ∈ Ai , (1 ≤ i ≤ n) sẽ là n Y S = |A1 × A2 × . . . × An | = m1 .m2 . . . mn = mk . k=1 Ví dụ 1.3. Từ các chữ số {0, 1, 3, 5, 7} có thể lập được bao nhiêu số tự nhiên có 3 chữ số đôi một khác nhau? Chứng minh. Ta gọi số tự nhiên có 3 chữ số cần tìm là abc. Ta thấy, có 4 cách chọn a, 4 cách chọn b và 3 cách chọn c từ các chữ số {0, 1, 3, 5, 7}. Như vậy theo quy tắc nhân, ta có 4.4.3 = 48 số tự nhiên có 3 chữ số đôi một khác nhau. Để áp dụng quy tắc nhân, điều cốt yếu là phải thiết kế một mô hình gồm việc thực hiện nhiều công đoạn. Số cách thực hiện ở mỗi công đoạn phải không phụ thuộc vào cách nào đã thực hiện ở công đoạn trước đó. Thành thử, muốn sử dụng được quy tắc nhân, mô hình của ta bao gồm việc thực hiện liên tiếp các công đoạn và số cách thực hiện ở mỗi công đoạn phải như nhau với mọi cách đã thực hiện ở công đoạn trước đó. Ví dụ 1.4. Có bốn người A, B, C, D cần chọn ba người vào chức Giám đốc, Kế toán trưởng và Chủ tịch Hội đồng quản trị. Giả sử việc chọn nhân sự phải thảo mãn yêu cầu: Ông A không thể được chọn làm Giám đốc, chức Chủ tịch HĐQT phải là ông C hoặc ông D. Hỏi có bao nhiêu cách chọn? Giải. Việc chọn ba vị trí chức Giám đốc, Kế toán trưởng và Chủ tịch Hội đồng quản trị tiến hành theo 3 công đoạn: Công đoạn 1: Chọn Giám đốc: có 3 cách chọn (chọn B, C, D). Công đoạn 2: Chọn Kế toán trưởng: có 3 cách chọn Kế toán trưởng từ ba người còn lại.
7 Công đoạn 3: Chọn Chủ tịch Hội đồng quản trị: có 2 cách chọn (ông C hoặc D). Theo quy tắc nhân thì có 3.3.2 = 18 cách chọn. Tuy nhiên đáp số này không chính xác vì số cách thực hiện công đoạn 3 phụ thuộc vào kết quả của các công đoạn 1 và 2 trước đó. Nếu ở các công đoạn trước, ông C và ông D đã được chọn thì ở công đoan 3 chỉ có 1 cách hoặc không có. Tuy nhiên, nếu việc chọn ba vị trí Giám đốc, Kế toán trưởng và Chủ tịch hội đồng quản trị được tiến hành theo ba công đoạn khác thì vẫn có thể áp dụng quy tắc nhân. Cụ thể như sau: Công đoạn 1: Chọn Chủ tịch hội đồng quản trị: có 2 cách chọn C hoặc D. Công đoạn 2: Chọn Giám đốc: Ta luôn có 2 cách chọn dù kết quả của công đoạn 1 thế nào. Sau công đoạn 1 còn 3 người, trong đó có ông A. Bỏ ông A ra thì còn 2 người có thể chọn vào chức Giám đốc. Công đoạn 3: Chọn Kế toán trưởng: luôn có 2 cách từ 2 người còn lại. Vậy có 2.2.2 = 8 cách chọn. Việc chia giai đoạn trong bài toán trên là ví dụ minh họa cho chúng ta thấy những bước cụ thể để thực hiện công việc cần làm. Chúng ta có thể không cần trình bày cụ thể các giai đoạn trong lời giải. Ngoài ra, để giải quyết một bài toán, chúng ta có thể kết hợp nhiều quy tắc khác nhau. Do vậy, chúng ta cần nắm rõ các quy tắc để áp dụng trong các trường hợp cụ thể. Tiếp theo, chúng ta sẽ đề cập đến Nguyên lý ngăn kéo Dirichlet. Người đầu tiên đề xuất ra nguyên lý này là nhà toán học người Đức Perter Guster Dirichlet (1805-1859) khi ông đề cập tới nó với tên gọi “nguyên lý ngăn kéo” (Schubfachprinzip). Người ta thường gọi “nguyên lý ngăn kéo Dirichlet” hay đôi khi gọi gọn là "nguyên lý Dirichlet" (tên gọi gọn này có thể gây ra nhầm lẫn với nguyên lý Dirichlet về hàm điều hòa). Có nhiều cách phát biểu cho nguyên lý ngăn kéo Diriclet (đối tượng phát biểu là chim hoặc thỏ). Nội dung nguyên lý như sau: Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ. Đây được coi như nguyên lý Dirichlet cơ bản. Nguyên lý 1.1 (Nguyên lý ngăn kéo Dirichlet mở rộng). Nếu nhốt n con
8 n+m−1 thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất m con thỏ. Ở đây ta dùng kí hiệu [x] là phần nguyên của số x. Chứng minh. Giả sử mọi chuồng thỏ không có đến n+m−1 n−1 n−1 = +1 = +1 m m m n−1 con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng con. Từ m n−1 đó suy ra tổng số con thỏ không vượt quá m. ≥ n − 1 con. Vô lý. m Vậy giả sử ban đầu là sai. Nguyên lý ngăn kéo Dirichlet tưởng chừng đơn giản như vậy nhưng nó là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó đặc biệt được áp dụng trong các lĩnh vực khác nhau của toán học. Nguyên lý này thực chất là một định lý về tập hữu hạn. Người ta có thể phát biểu nguyên lý này dưới dạng tập hợp như sau. Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B. Ví dụ 1.5. Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau.
9 1.1.2 Hoán vị, chỉnh hợp và tổ hợp Định nghĩa 1.1. Cho tập hợp A gồm n phần tử, n ≥ 0. Mỗi cách sắp xếp n phần tử của tập hợp A theo một thứ tự nào đó được gọi là một hoán vị của n phần tử đã cho, kí hiệu là Pn . Ta có công thức Pn = n! Định nghĩa 1.2. Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần được kí hiệu là P (n1 , n2 , . . . , nk ) và được tính bằng công thức n! P (n1 , n2 , . . . , nk ) = n1 !n2 ! . . . nk ! Ví dụ 1.6. Với các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm chín chữ số, trong đó mỗi chữ số 0, 1, 2, 3 xuất hiện đúng một lần, chữ số 4 xuất hiện đúng hai lần và chữ số 5 xuất hiện đúng ba lần? Chứng minh. Xét một số tùy ý x = 140525345 và kí hiệu các vị trí của x một cách hình thức, ta có x = a1 a2 a3 a4 a5 a6 a7 a8 a9 . Khi đó, mỗi số x tương ứng với một hoán vị của chín phần tử a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 . Số các hoán vị khác nhau của chín phần tử ai (1 ≤ i ≤ 9) là 9! song do a2 = a8 = 4, nên khi đổi chỗ a2 và a8 cho nhau, thì hoán vị a1 a2 a3 a4 a5 a6 a7 a8 a9 vẫn chỉ cho ta số x. Tương tự đổi chỗ hai trong ba phần tử a4 , a6 , a9 cho nhau ta vẫn nhận được số x. Như vậy, khi thực hiện 2! hoán vị a2 , a8 và 3! hoán vị a4 , a6 , a9 ta chỉ được một số cần tìm x. Vậy số các số có thể lập được là 9! S= = 30240. 2!3!
10 Định nghĩa 1.3. Cho tập hợp A gồm n phần tử, n ≥ 1. Mỗi bộ gồm k (0 ≤ k ≤ n) phần tử được sắp thứ tự của tập A được gọi là một chỉnh hợp chập k của n phần tử thuộc A và được kí hiệu là Akn . Số chỉnh hợp chập k của n phần tử được tính bởi công thức n! Akn = n(n − 1) . . . (n − k + 1) = . (n − k)! Nhận xét 1.1. Một chỉnh hợp chập n của n được gọi là một hoán vị của n phần tử, ta có Ann = Pn = n!. Định nghĩa 1.4. Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập gồm n phần tử được gọi là một chỉnh hợp lặp chập k của n phần tử. Số chỉnh hợp lặp chập k của n phần tử, kí hiệu Akn , bằng số ánh xạ từ tập k phần tử đến tập n phần tử và bằng nk , tức là Akn = nk . Ví dụ 1.7. Từ bốn chữ số 1, 2, 3, 5 có thành lập được bao nhiêu số chẵn gồm bốn chữ số? Chứng minh. Vì tập {1, 2, 3, 5} chỉ có duy nhất một số chẵn là 2, nên chúng ta gọi x = abcd, với a, b, c, d ∈ {1, 2, 3, 5} là các số cần tìm. Do số cần tìm là chẵn nên d = 2. Mặt khác a, b, c có thể bằng nhau nên y = abc là một chỉnh hợp lặp chập 3 của bốn phần tử 1, 2, 3, 5. Để thành lập số x ta chỉ cần lấy một số y nào đó rồi thêm số 2 vào cuối. Bởi vậy, số các số x = abc2 bằng số các số y = abc và bằng A34 = 43 = 64. Định nghĩa 1.5. Cho tập hợp A gồm n phần tử, n ≥ 1. Mỗi tập con gồm k (0 ≤ k ≤ n) phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho. Nhận xét 1.2. Hai tổ hợp được coi là khác nhau khi và chỉ khi có ít nhất một phần tử khác nhau.
11 Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử được kí hiệu là Cnk và được tính theo công thức n! Cnk = . k!(n − k)! Định nghĩa 1.6. Cho A = {a1 , a2 , . . . , an }. Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n) của một tập hợp là một bộ gồm m phần tử, mà mỗi phần tử này là một trong nhưng phần tử của A. Ta sử dụng kí hiệu Cnm để kí hiệu số tổ hợp lặp chập m của n phần tử. k Mệnh đề 1.1. Số tổ hợp chập k từ tập n phần tử bằng Cn+k−1 . Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n − 1 thanh đứng và k ngôi sao. Ta dùng n − 1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. Chẳng hạn, tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi: ∗∗ | ∗| | ∗ ∗∗ mô tả tổ hợp chứa đúng 2 phần tử thứ nhất, 1 phần tử thứ hai, không có phần tử thứ ba và 3 phần tử thứ tư của tập hợp. Mỗi dãy n − 1 thanh và k ngôi sao ứng với một xâu nhị phân có độ dài n + k − 1 với k số 1. Do đó số các dãy n − 1 thanh đứng và k ngôi sao chính là số tổ hợp chập k từ tập n + k − 1 phần tử. Ví dụ 1.8. Giả sử có 4 loại bóng mầu xanh, đỏ, tím, vàng với số lượng mỗi loại không hạn chế. Hai bộ bóng được xem là khác nhau nếu có ít nhất một mầu với số lượng thuộc hai bộ khác nhau. Hỏi có bao nhiêu cách chọn ra các bộ 6 quả bóng khác nhau. Chứng minh. Vì trong mỗi bộ sáu quả có thể có các quả bóng cùng mầu và không phân biệt thứ tự chọn, nên số cách chọn khác nhau bằng số tổ hợp lặp chập 6 của 4 phần tử (tập hợp bóng cùng mầu được coi là một phần tử) và được tính bằng công thức 6 9! C46 = C6+4−1 = = 84. 6!3!
12 Mệnh đề 1.2. Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, . . . , nk phần tử như nhau n! thuộc loại k bằng . n1 !n2 ! . . . nk ! Chứng minh. Để xác định số hoán vị trước tiên chúng ta nhận thấy có Cnn1 cách giữ n1 chỗ cho n1 phần tử loại 1, còn lại n − n1 chỗ trống. Sau n2 đó có Cn−n 1 cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n − n1 − n2 chỗ trống. Tương tự ta đặt các phần tử loại 3, loại 4, . . . , loại k − nk 1 vào các chỗ trống trong hoán vị. Cuối cùng có Cn−n1 −···−nk−1 cách đặt nk phần tử loại k vào hoán vị. Theo quy tác nhân tất cả các hoán vị là n2 nk n! Cnn1 .Cn−n1 · · · C n−n1 −···−nk−1 = . n1 !n2 ! . . . nk ! Ví dụ 1.9. Có bao nhiêu cách chia những xấp có 5 quân bài cho mỗi một người chơi trong bàn chơi có 4 người từ cỗ bài chuẩn có 52 quân bài. Chứng minh. Ta nhận thấy người đầu tiên có thể nhận được 5 quân bài bằng 5 C52 cách, còn 47 quân bài. Người thứ hai có thể nhận được 5 quân bài bằng 5 C47 cách, còn 42 quân bài. Người thứ 3 có thể nhận được 5 quân bài bằng 5 C42 cách, còn 37 quân bài. Người thứ tư có thể nhận được 5 quân bài bằng 5 5 5 5 5 52! C37 cách. Như vậy theo nguyên lý nhân ta có C52 .C47 .C42 .C37 = 5!5!5!5!32! cách chia 4 người chơi mỗi người một xấp 5 quân bài. Ví dụ trên là bài toán điển hình cho việc phân bố các đồ vật khác nhau vào các hộp khác nhau. Các đồ vật là 52 quân bài, còn 4 hộp là 4 người chơi và số còn lại để trên bàn. Số cách sắp xếp các đồ vật vào trong hộp được cho bởi mệnh đề sau. Mệnh đề 1.3. Số cách phân chia n đồ vật khác nhau vào trong k hộp khác nhau sao cho có ni vật được đặt vào trong hộp thứ i, với i = 1, 2, . . . , k bằng n! . n1 !n2 ! . . . nk !(n − n1 − · · · − nk )! Ví dụ 1.10. Trong một buổi giới thiệu sản phẩm, công ty phát 100 sản phẩm dùng thử cho nhân viên tiếp thị sản phẩm. Mỗi một khách hàng ghé qua gian hàng trưng bày sản phẩm, nhân viên sẽ phát cho họ 2 sản phẩm tặng kèm và 1 phiếu mua hàng giảm giá 20% sản phẩm. Có bao nhiêu cách
13 phát những sản phẩm khuyến mại cho khách hàng biết rằng có 25 khách hàng ghé gian hàng trưng bày. 2 Chứng minh. Ta nhận thấy, khách hàng đầu tiên có C100 cách để nhận sản phẩm khuyến mại. Chúng ta còn 98 sản phẩm khuyến mại để tặng cho các 2 khách hàng tiếp theo. Người thứ hai có C98 cách nhận sản phẩm khuyến 2 mại. Tương tự người thứ 3 chúng ta có C96 cách nhận . . . Như vậy theo quy tắc nhân và áp dụng mệnh đề 1.3 chúng ta có số cách phát các sản phẩm khuyến mại cho 25 khách hàng là 100! 100! = . 2!2!2! . . . 2!(100 − 2.25)! 2!2! . . . 2!50! 1.2 Một số phương pháp giải bài toán đếm của toán tổ hợp 1.2.1 Sử dụng công thức bao hàm và loại trừ Một trong những kết quả nền tảng của lí thuyết tổ hợp là định lý về “Công thức bao hàm và loại trừ”. Vì thực chất, công thức tính số phần tử của hợp các tập hợp đã là công thức bao hàm và loại trừ và được đề cập trong mục 1.1.1 của luận văn, bởi vì trong công thức này đối với mỗi phần tử đã tính được số lần nó được đếm và số lần nó không được đếm. Chúng ta sẽ mở rộng thêm công thức bao hàm và loại trừ: Cho tập hợp A và k tập con của nó Ai ⊂ A, i = 1, k. Nếu đã biết lực lượng của các tập con Ai và của giao 2, 3 . . . , k tập con của A, thì có bao nhiêu phần tử thuộc A, mà không nằm trong bất kỳ một tập con Ai nào. (i) Cho A là tập hữu hạn và A1 ⊂ A. Khi đó A1 ∪ A1 = A nên |A1 | = |A| − |A1 |. (1.1) (ii) Cho A và A1 , A2 ⊂ A. Khi đó |A1 ∩ A2 | = |A| − |A1 | − |A2 | + |A1 ∩ A2 |. (1.2)
14 (iii) Cho A và A1 , A2 , A3 ⊂ A. Khi đó |A1 ∩ A2 ∩ A3 | = |A| − |A1 | − |A2 | − |A3 | + |A1 ∩ A2 | + |A1 ∩ A3 | + |A3 ∩ A2 | − |A1 ∩ A2 ∩ A3 |. (1.3) (iv) Cho A và A1 , A2 , A3 , A4 ⊂ A. Khi đó |A1 ∩ A2 ∩ A3 ∩ A4 | = |A| − |A1 | − |A2 | − |A3 | − |A4 | + |A1 ∩ A2 | + |A1 ∩ A3 | + |A1 ∩ A4 | + |A3 ∩ A2 | + |A4 ∩ A2 | + |A3 ∩ A4 | − |A1 ∩ A2 ∩ A3 | − |A1 ∩ A2 ∩ A4 | − |A2 ∩ A3 ∩ A4 | + |A1 ∩ A2 ∩ A3 ∩ A4 |. (1.4) (v) Bằng phép quy nạp theo n (n ≥ 2) đối với tập hợp A và n tập hợp con A1 , A2 , . . . , An ⊂ A có công thức n \ n X n X | Ai | = |A| − |Ai | + |Ai ∩ Aj | − |A1 ∩ A2 ∩ A3 | i=1 i=1 i6=j − · · · − |An−2 ∩ An−1 ∩ An | + · · · + (−1)n |A1 ∩ A2 ∩ . . . ∩ An |. (1.5) Chúng ta sẽ xét một số bài toán trong chương trình trung học phổ thông sử dụng công thức trên để giải như sau. Bài toán 1.1. Có bao nhiêu số tự nhiên từ 1 đến 5000 mà không chia hết cho 2, không chia hết cho 5 và cũng không chia hết cho 9? . Chứng minh. Gọi tập A = {1, 2, . . . , 5000}, A1 = {a ∈ A| a .. 2}, A2 = {a ∈ . . A| a .. 5}, A3 = {a ∈ A| a .. 9}. Theo nguyên lý bù trừ, số các số nguyên dương từ 1 đến 5000 mà không chia hết cho 2, không chia hết cho 5 và cũng không chia hết cho 9 là |A \ (A1 ∪ A2 ∪ A3 )| = |A| − (|A1 | + |A2 | + |A3 |) + |A1 ∩ A2 | + |A2 ∩ A3 | + |A1 ∩ A3 | − |A1 ∩ A2 ∩ A3 |,
15 trong đó 5000 5000 5000 |A1 | = = 2500, |A2 | = = 1000, |A3 | = = 555; 2 5 9 5000 5000 |A1 ∩ A2 | = = 500, |A1 ∩ A3 | = = 277; 2.5 2.9 5000 5000 |A2 ∩ A3 | = = 111, |A1 ∩ A2 ∩ A3 | = = 55; 5.9 2.5.9 Thay vào công thức trên ta được |A\(A1 ∪A2 ∪A3 )| = 5000−(2500+1000+555)+500+277+111−55 = 1778. Nhận xét 1.3. Chúng ta có thể áp dụng mở rộng của công thức bao hàm và loại trừ để giải bài toán trên như sau: Với cách đặt các tập A, A1 , A2 , A − 3 như trên thì số các số tự nhiên từ 1 đến 5000 mà không chia hết cho 2, không chia hết cho 5 và cũng không chia hết cho 9 bằng lực lượng của tập A1 ∩ A2 ∩ A3 và được tính bằng công thức (1.3): |A1 ∩ A2 ∩ A3 | = 5000 − 2500 − 1000 − 555 + 500 + 277 + 111 − 55 = 1778. Bài toán 1.2. Một cuộc Hội thao cấp xã có bốn môn thi: Cầu lông, bóng bàn, chạy và cờ tướng. Có 100 vận động viên tham gia. Khi tổng kết, Ban tổ chức nhận thấy rằng: Môn cầu lông có 18 vận động viên tham gia, môn bóng bàn có 26 vận động viên tham gia, môn chạy có 19 vận động viên tham gia và môn cờ tướng có 24 vận động viên tham gia, trong đó 5 người tham gia cả cầu lông và bóng bàn; 2 người tham gia cả cầu lông và chạy; 3 người tham gia cầu lông và cờ tướng; 5 người tham gia bóng bàn và chạy; 4 người tham gia bóng bàn và cờ tướng; 3 người tham gia chạy và cờ tướng; 2 người tham gia đồng thời cả cầu lông, bóng bàn và chạy; 3 người tham gia cầu lông, bóng bàn và cờ tướng; 2 người tham gia cầu lông, chạy và cờ tướng; 4 người tham gia bóng bàn, chạy và cờ tướng; 1 người tham gia đồng thời cả bốn môn của Hội thao. Hỏi có bao nhiêu vận động viên không tham gia thi đấu một môn nào của Hội thao?
16 Chứng minh. Gọi A là tập gồm tất cả các vận động viên tham gia Hội thao, A1 tập các vận động viên tham gia môn cầu lông, A2 tập các vận động viên tham gia môn bóng bàn, A3 tập các vận động viên tham gia môn chạy, A4 tập các vận động viên tham gia môn cờ tướng. Khi đó, số vận động viên không tham gia thi đấu một môn nào của Hội thao chính bằng lực lượng của tập A1 ∩ A2 ∩ A3 ∩ A4 và được tính nhờ công thức (1.4): |A1 ∩ A2 ∩ A3 ∩ A4 | = 100(18 + 26 + 19 + 24) + (5 + 2 + 3 + 5 + 4 + 3) − (2 + 3 + 2 + 4) + 1 = 100 − 8 + 22 − 11 + 1 = 25. 1.2.2 Sử dụng phương pháp hệ thức truy hồi Đôi khi rất khó định nghĩa một đối tượng một cách tường minh. Nhưng có thể dễ dàng định nghĩa đối tượng này qua chính nó. Kỹ thuật này được gọi là đệ quy. Định nghĩa đệ quy của một dãy số định rõ giá trị của một hay nhiều hơn các số hạng đầu tiên và quy tác xác định các số hạng tiếp theo từ các số hạng đi trước. Định nghĩa đệ quy có thể dùng để giải các bài toán đếm. Khi đó quy tắc tìm các số hạng từ các số hạng đi trước được gọi là đệ quy truy hồi. Định nghĩa 1.7. Hệ thức truy hồi (hay công thức truy hồi) đối với dãy số {an } là công thức biểu diễn an qua một hay nhiều số hạng đi trước của dãy. Dãy số được gọi là lời giải hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa mãn hệ thức truy hồi này. Nội dung cơ bản của phương pháp này như sau: Thay vì ta đếm trực tiếp an theo yêu cầu bài toán, ta sẽ thiết lập hệ thức quan hệ giữa an , an−1 , . . . để từ đó tính được an . Chúng ta sẽ giải một số bài toán sau bằng hệ thức truy hồi. Bài toán 1.3. Giả sử một người gửi 10 triệu đồng vào tài khoản tiết kiệm của mình tại ngân hàng với lãi suất 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền trong tài khoản của mình?
17 Chứng minh. Gọi Pn là tổng số tiền có trong tài khoản tiết kiệm sau n năm. Vì số tiền có trong tài khoản sau n năm bằng số có sau n − 1 năm cộng lãi suất của năm thứ n, nên ta thấy dãy {Pn } thỏa mãn hệ thức truy hồi sau: P0 = 10; P1 = P0 + 0, 11P0 = 1, 11P0 P2 = P1 + 0, 11P1 = 1, 11P1 = (1, 11).(1, 11)P0 = (1, 11)2 P0 ... Pn = Pn−1 + 0, 11Pn−1 = (1, 11)Pn−1 = (1, 11)n P0 . Từ đó suy ra Pn = (1, 11)n .10, thay n = 30 ta được P30 = (1, 11)30 .10 ≈ 228, 9 triệu đồng. Bài toán 1.4. [1] Giả sử Fk là tập hợp tất cả các bộ (A1 , A2 , . . . , Ak ), trong đó Ai (i = 1, 2, . . . , k) là một tập con của {1, 2, . . . , n} (các tập A1 , A2 , . . . , Ak có thể trùng nhau). Hãy tính X Sn = |A1 ∪ A2 ∪ . . . ∪ Ak |. (A1 ,A2 ,...,Ak )∈Fk (Trường hợp n = 1998 là bài thi APMO 1998). Chứng minh. Do có 2n tập con của {1, 2, . . . , n} nên có 2nk bộ (A1 , A2 , . . . , Ak ). Với mỗi k−bộ (A1 , A2 , . . . , Ak ) của tập {1, 2, . . . , n − 1}, ta có thêm hoặc không thêm n vào tập Ai để được k−bộ (A1 , A2 , . . . , Ak ) của {1, 2, . . . , n}. Với chú ý rằng số k−bộ (A1 , A2 , . . . , Ak ) của tập {1, 2, . . . , n − 1} là 2(n−1)k và có 2k − 1 cách thêm n vào k−bộ (A1 , A2 , . . . , Ak ) của tập {1, 2, . . . , n − 1} thì ta có Sn = 2k Sn−1 + (2k − 1).2k(n−1) . Dễ thấy S1 = 2k − 1. Từ đấy bằng quy nạp ta chứng minh được Sn = n.(2k − 1).2k(n−1) . Bài toán 1.5 (IMO 1979, [1]). Cho A và E là hai đỉnh đối tâm của một hình tám cạnh đều. Có một con ếch bắt đầu nhảy từ A. Tại bất cứ đỉnh nào