Nguyên lý bao hàm & loại trừ và ứng dụng

  • Số trang: 13 |
  • Loại file: PDF |
  • Lượt xem: 28 |
  • Lượt tải: 0
thuvientrithuc1102

Đã đăng 15337 tài liệu

Mô tả:

1 2 BỘ GIÁO DỤC VÀ ĐÀO TẠO Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG ĐẠI HỌC ĐÀ NẴNG TRẦN LÊ HẠNH ĐOAN Người hướng dẫn khoa học: PGS.TSKH.Trần Quốc Chiến NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ Phản biện 1: TS. Cao Văn Nuôi ỨNG DỤNG Phản biện 2: PGS. TS. Trần Đạo Dõng Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.40 Luận văn sẽ ñược bảo vệ tại Hội ñồng chấm Luận văn tốt nghiệp thạc sĩ khoa học tại Đại học Đà Nẵng ngày 29 tháng 05 năm 2011. TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Có thể tìm hiểu luận văn tại: Đà Nẵng - Năm 2011 - Trung tâm thông tin - Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng. 4 3 MỞ ĐẦU 2. Mục ñích nghiên cứu Từ các ứng dụng nguyên lý bao hàm và loại trừ giải lớp các bài 1. Lý do chọn ñề tài Cùng với sự phát triển với tốc ñộ nhanh của công nghệ thông toán tương tự cụ thể. tin, lý thuyết tổ hợp ñã trở thành lĩnh vực toán học quan trọng và cần 3. Đối tượng nghiên cứu thiết cho nhiều lĩnh vực khoa học và ứng dụng. Nhiều bài toán hiện Đối tượng nghiên cứu: nguyên lý bao hàm và loại trừ. nay ñược giải quyết bằng cách quy chúng về các bài toán tổ hợp. Phạm vi nghiên cứu: nội dung của nguyên lý bao hàm và loại Lý thuyết tổ hợp nghiên cứu việc phân bố, sắp xếp các phần tử của một hoặc nhiều tập hợp, thoả mãn một số ñiều kiện nào ñó. Các bài toán tổ hợp rất phong phú và ña dạng: bài toán tồn tại, bài toán ñếm, bài toán liệt kê và bài toán tối ưu. Trong các bài toán ñó thì bài toán ñếm ñược ứng dụng rộng rãi và ña dạng. Từ các cấu hình tổ hợp cơ bản người ta hình thành nên hệ thống các cấu hình tổ hợp mở rộng và nâng cao. trừ, ứng dụng của nguyên lý này. 4. Phương pháp nghiên cứu Gián tiếp thông qua các tài liệu: sách, giáo trình, tạp chí toán học tuổi trẻ, truy cập các trang web. Trực tiếp thông qua sự hướng dẫn của thầy và việc trao ñổi thảo luận với các bạn. 5. Ý nghĩa khoa học và thực tiễn Công thức xác ñịnh số phần tử của hợp một số tập hữu hạn Đề tài góp phần nghiên cứu, hỗ trợ học sinh khi học phần tổ thường ñược dùng trong nhiều bài toán ñếm. Một trong những công hợp, giải một số bài toán số học mà việc giải chúng có nhiều ứng thức ñó là nguyên lý bao hàm và loại trừ của tập hợp. Sử dụng dụng trong trong các lĩnh vực toán học, tin học. nguyên lý này và phối hợp một số phương pháp khác trên tập hợp 6. Nội dung luận văn chẳng hạn phương pháp ánh xạ, ta có thể giải một số dạng toán. 1) Mở ñầu Trong lý thuyết tổ hợp, nguyên lý bao hàm và loại trừ là 2) Chương 1. Đại cương về tổ hợp phương pháp ñếm nâng cao giải các bài toán ñếm, nó có nhiều ứng 3) Chương 2. Nguyên lý bao hàm và loại trừ dụng hay. Trong các kỳ thi học sinh giỏi quốc gia, thi Olympic toán 4) Chương 3. Ứng dụng của nguyên lý bao hàm và loại trừ quốc tế, thi Olympic sinh viên giữa các trường ñại học và cao ñẳng 5) Kết luận các bài toán liên quan ñến dạng này hay ñược ñề cập và thường thuộc loại rất khó. Chính vì các lý do trên, tôi ñã nghiên cứu và chọn: “NGUYÊN LÝ BAO HÀM & LOẠI TRỪ VÀ ỨNG DỤNG ” làm ñề tài luận văn thạc sĩ của mình. 6 5 CHƯƠNG 1. ĐẠI CƯƠNG VỀ TỔ HỢP Nếu ta ký hiệu số chỉnh hợp có lặp chập k của n phần tử của A bằng AR (n, k) thì 1.1 Sơ lược lịch sử AR (n, k) = nk 1.2 Các quy tắc ñếm cơ bản 1.2.1 Quy tắc tương ứng một – một. Nếu tồn tại tương ứng 1.3.2 Chỉnh hợp không lặp • Định nghĩa. Một chỉnh hợp không lặp chập k của n phần tử một – một giữa các phần tử của các tập hữu hạn A 1 và A 2 , thì A 1 khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã và A 2 có cùng số các phần tử. cho. Các thành phần không ñược lặp lại. Chỉnh hợp không lặp ñơn Giả sử A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ. Ta ñịnh nghĩa giản gọi là chỉnh hợp. tích Đề-các của A 1 , A 2 ,...A n , kí hiệu là A 1 × A 2 ...× A n , là tập bao gồm tất cả các bộ có thứ tự ( a1 , a2 , ..., an ) gồm n thành phần a1 , a2 , ..., an sao cho a1 ∈ A1 , a2 ∈ A2 ,..., an ∈ An 1.2.2 Quy tắc nhân. Nếu A 1 , A 2 ,...A n là các tập hữu hạn bất kỳ và A 1 × A 2 ...× A n là tích Đề các của các tập ñó thì A1 × A2 × ... × An = A1 A2 ... An 1.2.3 Quy tắc cộng. Nếu A 1 , A 2 ,...A n là các tập hữu hạn ñôi một rời nhau, tức là Ai ∩ AJ = φ nếu i ≠ j thì Kí hiệu số các chỉnh hợp chập k của n phần tử của A là A(n, k) ta có  n!  A ( n, k ) =  ( n − k ) !  0 1.3 Cấu hình tổ hợp cơ bản 1.3.1 Chỉnh hợp lặp • Định nghĩa. Một hoán vị của n phần tử khác nhau là một cách sắp xếp thứ tự các phần tử ñó. Hoán vị có thể coi là trường hợp riêng của chỉnh hợp không lặp chập k của n trong ñó k = n. Ta có số hoán vị là P(n) = n! 1.3.4 Hoán vị vòng quanh Số hoán vị vòng quanh của n phần tử khác nhau ( Qn ) ñược tính bằng công thức Qn = (n − 1)! • Định nghĩa. Một chỉnh hợp lặp chập k của n phần tử khác nhau là một bộ có thứ tự gồm k thành phần lấy từ n phần tử ñã cho. Các thành phần có thể ñược lặp lại. khi k > n 1.3.3 Hoán vị không lặp A1 ∪ A2 ∪ ... − ∪ An = A1 + A2 + ... + An Ở ñây Ai là lực lượng ( số các phần tử ) của tập A i khi k ≤ n 1.3.5 Tổ hợp • Định nghĩa. Một tổ hợp chập k của n phần tử khác nhau là một bộ không kể thứ tự gồm k thành phần khác nhau lấy từ n phần tử 7 8 ñã cho. Nói cách khác ta có thể coi một tổ hợp chập k của n phần tử với m = m1 + m2 + ... + mn . khác nhau là một tập con có k phần tử từ n phần tử ñã cho. • Hệ quả. Giả sử tập S có n phần tử, trong ñó có n1 phần tử Nếu ta ký hiệu số tổ hợp chập k của n phần tử của A bằng C(n, kiểu 1, n2 phần tử kiểu 2, ... , nk phần tử kiểu k. Khi ñó số các hoán k) thì vị n phần tử của S là  n! khi 1 ≤ k ≤ n  C (n, k ) =  k!(n − k )! 0 khi k > n  P ( n ; n 1 , n 2 , . .. , n k Mỗi tổ hợp chập k của n phần tử của A có thể xem như là 1 tập ) = n! n 1 ! n 2 ! . . .n k ! 1.4.2 Tổ hợp lặp con lực lượng k của A. Vì vậy C(n, k) chính bằng số các tập con lực • Định nghĩa. Tổ hợp lặp chập k từ n phần tử khác nhau là lượng k của A. Với k = 0, vì chỉ có 1 tập con của A lực lượng 0 là tập một nhóm không phân biệt thứ tự gồm k phần tử trích từ n phần tử ñã rỗng nên ta có thể ñịnh nghĩa một cách tự nhiên rằng C(n, 0) = 1. Khi cho, trong ñó các phần tử có thể ñược lặp lại. ñó ñẳng thức C (n, k ) = • Định lý 2. Giả sử X có n phần tử khác nhau. Khi ñó số tổ n! cũng ñúng cho cả k = 0. k !(n − k )! hợp lặp chập k từ n phần tử của X, ký hiệu CR(n, k), là 1.4 Cấu hình tổ hợp mở rộng CR(n, k) = C(k + n – 1, n - 1) = C(k + n – 1, k). 1.4.1 Hoán vị lặp 1.4.3 Phân hoạch của tập hợp. Số Sterling loại 2 và số Bell • Định nghĩa. Hoán vị lặp là hoán vị trong ñó mỗi phần tử Giả sử A là tập hữu hạn với A = n , còn k là 1 số nguyên ñược ấn ñịnh một số lần lặp lại cho trước. Ký hiệu số các hoán vị có lặp của các phần tử a 1 , a 2 , ... , a n với tham số lặp m1 , m2 , ..., mn là P ( m; m1 , m2 , ..., mn ) . • Định lý 1. Số hoán vị lặp của n phần tử khác nhau, trong ñó phần tử thứ nhất lặp m1 lần, phần tử thứ hai lặp m2 lần, ... , phần tử dương. Ta cũng giả sử A1 = A . S là sơ ñồ sắp xếp “tập { X1 , X 2 , ... , X k } với X1 , X 2 , ... , X k cũng là các “tập” ñể ta xếp các phần tử của A 1 vào ”, R1 là ñiều kiện “mọi phần tử của A 1 ñều ñược sắp xếp vào một trong các “tập” X1 , X 2 , ... , X k ”, R2 là ñiều kiện “với mọi i = 1, ... , k có ít nhất một phần tử của thứ n lặp mn lần là m! P (m; m1, m2,...mn) = m !m !...m ! 1 2 n A1 ñược xếp vào Xi ”. 10 9 Khi ñó, một cấu hình tổ hợp trên A1 theo S thỏa mãn các ñiều kiện R1 và R2 ñược gọi là một phân hoạch của A thành k khối. Số tất cả các phân hoạch thành k khối của một tập A lực lượng 1.4.5 Phân hoạch không thứ tự tổ hợp • Định nghĩa. Cho X là tập n phần tử khác nhau, các số nguyên dương n1 , n2 , ... , nk và p1 , p2 , ... , pk thỏa n1 p1 + n 2 p 2 + ... + n k p k = n n ñược gọi là số Sterling loại 2 và ñược ký hiệu là S(n, k). Dễ thấy rằng S(n, k) = 0 nếu k > n. Ta cũng quy ước rằng S(n, 0) = 0. Số Tn = S(n, 1) + S ( n, 2 ) + ... + S(n, n) ñược gọi là số Bell. Như vậy, số Bell chính là số tất cả các phân hoạch của tập A lực lượng n. Việc tính S(n, k) và Tn sẽ ñược trình bày trong phần ứng dụng của nguyên lý bao hàm và loại trừ. 1.4.4 Phân hoạch thứ tự tổ hợp • Định nghĩa. Cho X là tập n phần tử khác nhau, r ≤ n và S ⊂ X có r phần tử. Một phân hoạch {S1 , S2 , ... , Sn } có thứ tự của S gọi là 1 phân hoạch thứ tự tổ hợp chập r của X. Nếu r = n, thì gọi là các số nguyên dương n1 , n2 , ... , nk thỏa n1 + n2 + ... + nk = r . Số các phân hoạch thứ tự tổ hợp chập r của X dạng {S1 , S2 , ... , Sk } có S1 = n1 , S2 = n2 , ... , Sk = nk ñược ký hiệu là C ( n; n1 , n2 , ... , nk ) . • Định lý3. C ( n; n1 , n2 , ... , nk ) tập lực lượng n2 , ... , pk tập lực lượng nk gọi là phân hoạch không thứ tự của X. • Định lý 4. Số phân hoạch không thứ tự của X với p1 tập lực lượng n1 , p2 tập lực lượng n2 , ... , pk tập lực lượng nk là C (n; n1 ..., n1 , n2 ,..., n2 , nk ,..., nk ) n! = p1 p p p1! p2 !... pk ! p1!(n1!) p2 !(n2 !) 2 ... p k !(nk !) k (trong tử số C ( n; n1 , ..., n1 , n2 , ... , n2 , nk , ... , nk ) số n1 lặp lại p1 lần, số n2 lặp lại p2 lần,..., số nk lặp lại pk lần). ◊ Ví dụ 9 phân hoạch thứ tự của X. Cho Một hệ thống các tập con của X gồm p1 tập lực lượng n1 , p2 n! = = P(n; n1 , n2 , ..., nk , n − r ) n1 !.n2 !...nk ! ( n − r )! C ( n; n1 , n2 , ... , nk ) ñược gọi là hệ số ña thức. (i) Số cách chia 21 học sinh vào 3 lớp học buổi sáng, buổi chiều và buổi tối, mỗi lớp 7 sinh viên là C ( 21; 7, 7, 7 ) = 21! ( 7!) (phân hoạch thứ tự) 3 (ii) Số cách chia 21 học sinh thành 3 tổ, mỗi tổ 7 học sinh là C ( 21; 7, 7, 7 ) 3! = 21! ( 7!) 3 3! (phân hoạch không thứ tự). 11 CHƯƠNG 2. NGUYÊN LÝ BAO HÀM VÀ LOẠI TRỪ 2.1 Nguyên lý bao hàm và loại trừ dạng kinh ñiển 2.1.1 Công thức 1 (Nguyên lý bao hàm và loại trừ cho hai 12 2.1.3 Công thức 3 (Nguyên lý bao hàm và loại trừ dạng kinh ñiển) X1 ∪ X 2 ∪ ... ∪ X n = tập hợp) Có bao nhiêu phần tử trong hợp của hai tập hữu hạn phần tử? Số các phần tử trong hợp hai tập A và B bằng tổng các phần tử của mỗi tập trừ ñi số phần tử của giao hai tập hợp, tức là A ∪ B = A + B − A ∩ B +(−1)k +1 ∑ 1≤i1 4 và có tính chất A 3 là x3 > 6 . Khi ñó số nghiệm thỏa mãn các bất ñẳng thức x1 ≤ 3 , x2 ≤ 4 và x 3 ≤ 6 bằng A1 ∩ A2 ∩ A3 = A − A1 − A2 − A3 + A1 ∩ A2 + A1 ∩ A3 + A2 ∩ A3 − A1 ∩ A2 ∩ A3 = 78 - 36 - 28 - 15 + 6 + 1 + 0 – 0 = 6. Có bao nhiêu số nguyên dương từ 1 ñến 1000 mà không chia hết cho 2, không chia hết cho 3 và cũng không chia hết cho 7? Giải. Ký hiệu A ={1, 2, 3,…,1000}, A2 = {a ∈ A / a không chia hết cho 2}, A 3 = {a ∈ A / a không chia hết cho 3}, A 7 = 3.3. Sàng Eratosthenes Nguyên lý bù trừ cũng có thể ñược dùng ñể tìm số các số nguyên tố nhỏ hơn một số nguyên dương nào ñó. Cần nhớ rằng một hợp số chia hết cho một số nguyên tố không lớn hơn căn bậc hai của {a ∈ A / a không chia hết cho 7}. Khi ñó A \ ( A2 ∪ A3 ∪ A7 ) là tập nó. Do ñó, ñể tìm các số nguyên tố không vượt quá 100 thì ñiều cần tất cả các số từ 1 ñến 1000 mà không chia hết cho 2, không chia hết chú ý ñầu tiên là một hợp số nhỏ hơn 100 phải có một thừa số nguyên cho 3 và cũng không chia hết cho 7. tố không lớn hơn 10. Vì nhỏ hơn 10 chỉ có các số nguyên tố là 2, 3, 5, 7, nên các số nguyên tố không vượt quá 100 gồm bốn số nguyên tố Theo nguyên lý bao hàm và loại trừ , ta có A \ ( A 2 ∪ A3 ∪ A 7 ) = A − A 2 ∪ A3 ∪ A 7 = 1000 -714 =286 3.2. Bài toán xác ñịnh số nghiệm nguyên của một phương trình với một số ràng buộc nào ñó Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm, trong ñó x 1 , x 2 và x 3 là các số nguyên không âm với x1 ≤ 3 , x2 ≤ 4 và x3 ≤ 6? Giải. Để áp dụng nguyên lý bao hàm và loại trừ, gọi tổng số nghiệm là A ; nghiệm có tính chất A 1 là x1 > 3 , có tính chất A 2 là trên và tất cả các số nguyên dương nhỏ hơn 100 không chia hết cho 2, 3, 5, 7. Để áp dụng nguyên lý bao hàm và loại trừ , ta gọi A1 là tính chất chia hết cho 2, A2 là tính chất chia hết cho 3, A3 là tính chất chia hết cho 5, A4 là tính chất chia hết cho 7. Vậy số nguyên tố không vượt quá 100 là A1 ∩ A2 ∩ A3 ∩ A4 + 4 = 21 + 4 = 25 Do ñó có 25 số nguyên tố không vượt quá 100. 3.4. Bài toán ñếm số các số nguyên dương nhỏ hơn số nguyên dương n và nguyên tố cùng nhau với n ( ϕ - hàm Euler) Hai số nguyên ñược gọi là nguyên tố cùng nhau nếu chúng không có ước số chung khác 1. Với mỗi số nguyên dương n, ký hiệu 18 17 bằng ϕ ( n) số các số nguyên dương nhỏ hơn hoặc bằng n mà nguyên tố cùng nhau với n. Hàm ϕ ( n) ñược gọi là ϕ - hàm Euler. Giả sử kí hiệu D n là số mất thứ tự của một tập có n phần tử. Bây giờ ta xét bài toán sau: Bài toán: Hãy tính giá trị của ϕ ( n) theo n. Giải. Giả sử n = p1α1 p2α2 ... pk αk Bài toán: Hãy tìm số mất thứ tự của một tập có n phần tử. là phân tích chính tắc của n Giải . Giả sử A là tập tất cả các hoán vị của tập X, Ai = {a ∈ A / xi là ñiểm bất ñộng của a}. Khi ñó A\ ( A1 ∪ ... ∪ An ) thành tích các thừa số nguyên tố, ở ñây α1 , α 2 ,..., α k là các số là tập tất cả các hoán vị của x mà không có ñiểm bất ñộng nào. Theo nguyên dương. Ta cũng giả sử A = {1, 2, …,n}, A pi = {a ∈ A / a nguyên lý bao hàm và loại trừ , ta có A1 ∪... ∪ An = chia hết cho p i }, i = 1, 2, …,k. Khi ñó n n Api = , Api ∩ Ap j = (i ≠ j ),... pi pi p j 1 k 1 1≤i ≤n i D n = A \ ( A1 ∪ ... ∪ An ) = A − A1 ∪ ... ∪ An 1  1 1 1 = n !1 − + − + ... + (−1) n  n!   1! 2! 3! k n n n n n  = n −  + ... + − − ... − + ... + (−1)k +1  p p p p p p p p k 1 2 k −1 k 1 2... pk   1  1  1   1  = n 1− 1−  ....1−   p1  p2   pk  3.5. Bài toán tìm số xáo trộn của một hoán vị có n phần tử Trước tiên ta lưu ý: Cho tập hợp có n phần tử. Khi ñó mỗi hoán vị của n phần tử trên sao cho không có phần tử nào ở nguyên vị trí ban ñầu ñược gọi là một xáo trộn của tập n phần tử ñã cho. Số tất cả các xáo trộn ñược gọi là số mất thứ tự. Ví dụ hoán vị 21453 là một xáo trộn của 12345 vì không có số 3.6. Bài toán bỏ thư. Có n lá thư và n phong bì ghi sẵn ñịa chỉ. Bỏ ngẫu nhiên các thư vào các phong bì sao cho mỗi phong bì chỉ chứa một thư. a) Hỏi xác suất ñể không lá thư nào ñúng ñịa chỉ bao nhiêu ? b) Hỏi xác suất ñể ñúng r lá thư ñúng ñịa chỉ là bao nhiêu (r ≤ n ) ? Sử dụng nguyên lý bao hàm và loại trừ, ta có   a) Xác suất cần tìm là  1 − nào ở nguyên vị trí ban ñầu của nó. Tuy nhiên, 21543 không phải là một xáo trộn của 12345 vì hoán vị này ñể số 4 ở nguyên vị trí ban ñầu của nó. 1≤i < j ≤n Ai ∩ Aj + ... + (−1)n+1 A1 ∩... ∩ An , Vậy Áp dụng nguyên lý bao hàm và loại trừ , ta ñược ϕ ( n ) = A \ ( A p ∪ ... ∪ A p ) = A − A p ∪ ... ∪ A p ∑A− ∑ b) Xác suất cần tìm là 1 1 1 1 + − + ... + (−1)n  1! 2! 3! n!  1 1 1 1 (−1) n− r  1 − + − + ... +   r !  1! 2! 3! (n − r )!  20 19 3.7. Bài toán ñếm số các hàm toàn ánh. Nguyên lý bù trừ cũng có thể ñược dùng ñể xác ñịnh số các k ! S ( n, k ) = Hãy ñếm số toàn ánh từ tập X vào tập Y. Giải. Ký hiệu T là tập hợp tất cả các toàn ánh từ X vào Y. Theo nguyên lý bao hàm và loại trừ , ta có T = k ( − 1) r C ( k , r )( k − r ) n ∑ r =0 3.8. Bài toán xếp n cặp vợ chồng (Lucas) Một bàn tròn có 2n ghế. Cần sắp n cặp vợ chồng sao cho ñàn r C ( k , r )( k − r ) n ⇒ S ( n , k ) = r =0 1 k ∑ ( − 1) r C ( k , r )( k − r ) n k ! r=0 3.10. Một số bài toán sử dụng nguyên lý bao hàm và loại hàm toàn ánh từ tập có n phần tử ñến tập có k phần tử. Bài toán: Cho hai tập hợp X và Y có X = n , Y = k , n ≥ k . k ∑ ( − 1) trừ trong kỳ thi Olympic quốc tế, thi học sinh giỏi quốc gia và tạp chí toán học tuổi trẻ. Bài 1 { x1 , x2 , , ... , xn } của Một hoán vị {1, 2, ... , 2n} với tập hợp n nguyên dương, ñược gọi là có tính chất P nếu xi − xi +1 = n , với ít nhất một giá trị i ∈ {1, 2, ... , 2 n − 1} . Chứng minh rằng với mỗi số n, số hoán vị có tính chất P lớn hơn số hoán vị không có tính chất P. {1, 2, ... , n, n + 1, n + 2, ... ,2 n} . Giải. Đặt M = ông ngồi xen kẽ ñàn bà và không có cặp vợ chồng nào ngồi cạnh Lưu ý nhau (có tính ñến vị trí ghế và thứ tự chỗ ngồi). Hỏi có bao nhiêu 1 − ( n + 1) = n và 2 − ( n + 2 ) = n . Gọi cách xếp? của M sao cho trong các hoán vị ñó, hai phần tử k và k + n ñứng kề Giải. Gọi số phải tìm là M n . Theo nguyên lý bao hàm và loại nhau. Gọi A là tập tất cả các hoán vị có tính chất P. Ta thấy A = U Ak nên trừ, ta có. n M n = 2.n !.∑ (−1) k =0 k k 2n C (2n − k , k ).(n − k )! 2n − k A = UA k k 3.9. Bài toán tính số Sterling loại 2 Bài toán: Tính số Sterling loại hai S ( n, k ) qua n và k. Giải. Ak là tập tất cả các hoán vị Mỗi phân hoạch k khối của tập X có n phần tử có thể = ∑A k − (không kể thứ tự) sao cho thùng nào cũng có phần tử của X. Hoán vị các thùng B1 ,..., Bk , ta thấy một phân bố như vậy sẽ sinh k! hàm toàn ánh từ tập X vào tập { B1 ,..., Bk } . Suy ra k ∩ Ah + ∑ k ( 2n )! Y = {( x, y, z ) y ∈ D , x ∈ E , z ∈ E , x + y + z M m} , 2 Z = {( x, y, z ) z ∈ D , x ∈ E , y ∈ E , x + y + z M m} , Bài 2 Cho hai số nguyên dương m và n sao cho n + 2 chia hết Khi ñó C = X ∪ Y ∪ Z . Do ñó cho m. Hãy tính các bộ ba số nguyên dương ( x , y, z ) sao cho tổng x + y + z chia hết cho m, trong ñó mỗi số x, y, z ñều không lớn hơn C = X + Y + Z − X ∩Y − X ∩ Z − Y ∩ Z + X ∩Y ∩ Z Tương tự X = Y = Z = 2k 2 m , n. Giải. Đặt k = n+2 ∈ N * . Ta có n = km – 2. m X ∩ Y = X ∩ Z = Y ∩ Z = 4k, 24 −m khi m = 1, 2, 3 X ∩ Y ∩ Z = τ (m) =  khi m > 3 1 Xét các tập hợp: D = {km − 1, km} ; E = {1, 2,..., km} ; Do ñó C = 6 k 2 m − 12k + τ ( m ) . Thay k = A = {( x, y, z ) x, y, z ∈ E \ D; x + y + z M m} ; B = {( x , y, z ) x, y, z ∈ E; x + y + z M m} ; C = {( x , y, z ) x, y, z ∈ E; x ∈ D hoặc A = B − C = y∈D hoặc z ∈ D; ; x + y + z M m} . Ta có A = B − C • Tính B . Có km cách chọn x ∈ E. Với mỗi cách chọn x ∈ E, ta có km cách chọn y ∈ E. Với mỗi cách chọn x và y như trên, ta có k cách chọn z ∈ E sao cho x + y + z M m. Do ñó B = km.km.k = k 3 m2 . • Tính C . Đặt X = {( x, y, z ) x ∈ D , y ∈ E , z ∈ E , x + y + z M m} , ( ∗) n+2 ñược m n3 + 8 − τ ( m ) với τ ( m ) xác ñịnh bởi ( ∗) m Bài 3 (VMO-1995, Bảng B). Hỏi từ các số 1, 2, 3, 4, 5 có thể lập ñược bao nhiêu số có 10 chữ số thỏa mãn ñồng thời các ñiều kiện sau: 1) Trong mỗi số, mỗi chữ số có mặt ñúng hai lần; 2) Trong mỗi số, hai chữ số giống nhau không ñứng cạnh nhau ? Giải. Gọi s là số cần tìm và A là tập gồm tất cả các số có 10 chữ số, lập ñược từ các chữ số 1, 2, 3, 4, 5 thỏa mãn ñiều kiện 1 của ñề bài. Khi ñó, theo nguyên lý bao hàm và loại trừ ta tính ñược: A = s= 10! 25 10! 9! 8! 7! 6! 5! − C51 4 + C52 3 − C53 2 + C54 1 − 0 = 39480 5 2 2 2 2 2 2 24 23 167 Bài 4 Một cuộc hội thảo toán học quy tụ 1990 nhà toán học (1) ∑ | Ai | = 2004; trên toàn thế giới. Cho biết cứ mỗi nhà toán học ñều ñã có dịp làm i =1 chung với 1327 nhà toán học khác tham dự hội thảo. Chứng minh rằng ta có thể tìm ñược 4 nhà toán học từng ñôi một ñã làm việc (2) A j = Ai Ai ∩ A j với mọi i, j ∈ {1, 2, ....,167} và i Tính UA ≠ j chung với nhau. 167 Giải. Mỗi nhà toán học ñược xem như là một ñiểm. Hai nhà i =1 toán học ñã làm việc chung với nhau xem như 2 ñiểm ñược nối với i . nhau bởi một ñoạn thẳng. Lý luận tương tự như bài toán trên ñây, gọi Giải. v1 và v2 là 2 ñiểm ñược nối với nhau. Gọi A là tập hợp các ñiểm • Ta có Aj = Ai . A j ∩ Ai ; Ai = Aj . Ai ∩ Aj khác v 2 ñược nối với v 1 và B là tập hợp các ñiểm khác v 1 ñược nối Suy ra Ai = Ai . Ai ∩ A j với v 2 . Lúc ñó: Nếu Ai = 0 thì từ ( 2 ) suy ra A j = 0, ∀j ≠ i . Điều này A ∩ B = A + B − A ∪ B = 2 × 1326 − 1998 = 664 Nghĩa là ta có thể tìm ñược nhà toán học v3 ñã làm việc chung với v1 và v 2 . Gọi C là tập hợp các ñiểm ñược nối với v 3 nhưng không nối với v1 và v 2 . Ta có C ≥ 1325 , vậy 1998 ≥ ( A ∩ B ) ∪ C = A ∩ B + C − A ∩ B ∩ C Nghĩa là A ∩ B ∩ C ≥ A ∩ B + C − 1998 ≥ 664 + 1325 − 1988 = 1 > 0 Vậy A ∩ B ∩ C ≠ ∅ và ta tìm ñược v4 ∈ A ∩ B ∩ C . Tập hợp gồm 4 nhà toán học v1 , v2 , v3 , v4 ñã làm việc với nhau từng ñôi một và ñó là ñpcm. Bài 5 Cho 167 tập hợp A1 , A2 , ... A167 thỏa mãn các ñiều kiện sau: 2 mâu thuẫn với (1). Vậy Ai ≠ 0 . Do ñó Ai ∩ A j = 1 ( i ≠ j ) và Ai = Aj . Do ñó Ai = 12, ∀i • Xét tập A 1 . Mỗi tập A2 , ... , A167 ñều chứa và chỉ chứa 1 phần tử của A 1 . Không giảm tổng quát giả sử 14 tập A2 , ... , A15 cùng chứa phần tử a ∈ A1 . Ta sẽ chứng minh a ∈ Ai , ∀i . Thật vậy, giả sử tồn tại i > 15; a ∉ Ai . Đặt Bi = Ai \ {a} Khi ñó với mỗi A j ( j = 2, ... 15) ta có A j ∩ Ai = 1 do ñó Aj ∩ Bi = 1 . Giả sử A j ∩ Bi = bj . Ta có b j1 ≠ b j2 vì nếu 26 25 b j1 = b j2 thì hai tập hợp A j1 và A j2 có 2 phần tử chung là a và b j1 KẾT LUẬN trái với Ai ∩ A j = 1 . Đề tài nguyên lý bao hàm & loại trừ và ứng dụng bước ñầu ñã Như vậy b2 , ..., b15 là 14 phần tử thuộc Ai . Điều này không hệ thống hóa ñược một mảng kiến thức về giải các bài toán tổ hợp từ xảy ra vì Ai = 12. những dạng cơ bản ñến phức tạp hơn. Thông qua nghiên cứu lý Vậy với mọi i ≠ j ta có Ai ∩ A j = {a} . thuyết về nguyên lý bao hàm và loại trừ, ñề tài ñã ứng dụng trong Đặt Bi = Ai \ {a} với mọi i thì Bi ∩ B j = ∅ với mọi i, j mà việc giải các bài toán tổ hợp có liên quan. Đặc biệt là những bài toán i ≠ j . Do vậy: Từ nguyên lý bao hàm và loại trừ ta có thể giải ñược lớp các 167 UA i =1 ứng dụng phương pháp sử dụng nguyên lý bao hàm và loại trừ. i = 167 UB i =1 i ∩ {a} = 167 ∑B i =1 i + {a} = 167.11 + 1 = 1838 bài toán có nhiều ứng dụng trong thực tiễn, ñời sống. Bằng cách thay ñổi các tập hợp, số lượng tập hợp và quan hệ giữa các phần tử ta có thể tạo ra nhiều bài toán khác nhau về nguyên lý bao hàm và loại trừ mà việc giải chúng giúp học sinh rèn luyện việc sử dụng linh hoạt các cấu hình tổ hợp cơ bản và mở rộng. Hơn nữa ñề tài cũng có hướng mở ñể tiếp tục nghiên cứu ứng dụng trong giải các bài toán phức tạp và các bài toán ứng dụng trong lĩnh vực tin học. Đây là một vấn ñề nghiên cứu khá hay, trong thời gian ñến tôi sẽ tiếp tục dành thời gian cho việc nghiên cứu vấn ñề này.
- Xem thêm -