Phương pháp thiết lập quan hệ truy hồi trong các bài toán đếm

Nội dung tài liệu: Phương pháp thiết lập quan hệ truy hồi trong các bài toán đếm

1. PHẦN I: MỞ ĐẦU I. LÝ DO CHỌN ĐỀ TÀI Đối với người giáo viên, đặc biệt là giáo viên ở trường chuyên, ngoài nhiệm vụ trang bị cho các em học sinh những kiến thức nền tảng để giải quyết các bài toán cơ bản, chúng tôi còn tham gia giảng dạy, bồi dưỡng các đội tuyển học sinh giỏi. Vì vậy việc học tập, trau dồi các chuyên đề nâng cao cũng là một nhiệm vụ quan trọng. Chuyên đề tổ hợp là một chuyên đề khó đối với giáo viên và học sinh. Các bài toán tổ hợp thường đa dạng và có thể phải dùng nhiều kiến thức khác nhau trong một bài toán. Trong các bài toán tổ hợp có một lớp các bài toán đếm, đây cũng là một vấn đề hay và khá quan trọng trong toán tổ hợp. Các bài toán đếm thông thường yêu cầu tư duy tổng quát và phương pháp thiết lập hệ truy hồi là một phương pháp khó và khá hiệu quả khi giải các bài toán đếm. Trong nhiều kì thi học sinh giỏi quốc gia, thi oympic Toán quốc tế thì các bài toán liên quan đến tổ hợp cũng được đề cập nhiều và được xem là một loại toán khó ở bậc THPT. Lý thuyết và các bài toán về phương pháp thiết lập hệ thức truy hồi trong các bài toán đếm đã được đề cập ở nhiều tài liệu. Tuy nhiên các tài liệu viết riêng về phương pháp truy hồi như một chuyên đề riêng chưa có nhiều và chưa cập nhật được một số bài toán mới. Nhằm nâng cao hiệu quả giáo dục trong nhà trường phổ thông, và góp phần từng bước nâng cao chất lượng của công tác bồi dưỡng học sinh giỏi của trường chuyên, chúng tôi đưa ra chuyên đề ôn luyện học sinh giỏi: “Phương pháp thiết lập quan hệ truy hồi trong các bài toán đếm.” Chuyên đề gồm ba phần chính: – Cơ sở của phương pháp. – Một số bài toán vận dụng phương pháp thiết lập hệ truy hồi. – Bài tập luyện tập. 1
2. II. MỤC ĐÍCH NGHIÊN CỨU Cung cấp cho học sinh một hệ thống cơ sở lí thuyết và bài tập đa dạng từ đơn giản đến phức tạp về các bài toán đếm được xử lí bằng phương pháp thiết lập quan hệ truy hồi. Giúp học sinh biết nhìn nhận một vấn đề theo nhiều hướng khác nhau để rèn luyện tư duy, từ đó các em có thêm niềm tin trước các bài toán cũng khó cũng như các tình huống thực tế phức tạp. III. NHIỆM VỤ NGHIÊN CỨU Đưa ra hướng tiếp cận cho một số dạng bài toán đếm được xử lý bằng một số quy tắc đếm cơ bản, đặc biệt là phương pháp thiết lập quan hệ truy hồi với hệ thống lí thuyết và ví dụ minh họa phong phú. IV. ĐỐI TƢỢNG NGHIÊN CỨU Các bài toán cơ bản và nâng cao về tổ hợp trong các cuộc thi học sinh giỏi khu vực, trong nước và quốc tế. V. PHƢƠNG PHÁP NGHIÊN CỨU Thông qua thực tiễn dạy một số chuyên đề tổ hợp cho một lớp tại trường THPT Chuyên Bắc Giang và đội tuyển học sinh giỏi Quốc gia để tổng hợp, phân tích, đánh giá. VI. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI Đưa ra được hệ thống cơ sở lí thuyết cơ bản và nâng cao về phương pháp thiết lập quan hệ truy hồi sử dụng trong các bài toán đếm giúp ích cho việc tiếp cận lời giải các bài toán tổ hợp, ví dụ minh họa phong phú, từ đơn giản đến phức tạp khá đầy đủ. Tạo thêm niềm tin và một cách tiếp cận cho học sinh trước các bài toán tổ hợp. 2
3. PHẦN II: NỘI DUNG I. Cơ sở phƣơng pháp Phương pháp thiết lập hệ truy hồi là một phương pháp cơ bản và quan trọng đối với các bài toán đểm trong tổ hợp. Nội dung phương pháp là nếu ta thiết lập được mối quan hệ truy hồi giữa số lượng đối tượng cần đếm trong nhóm n đối tượng với số lượng đối tượng cần đếm trong các nhóm ít hơn đối tượng thì ta có thể đưa về đếm số đối tượng trong nhóm mới với số đối tượng ít hơn. Nói cách khác, thay vì đếm trực tiếp Sn(), ta thiết lập hệ thức liên hệ giữa với Sn( 1) , Sn( 2) , từ đó dùng kiến thức về dãy số để tìm được . Các bài toán sử dụng phương pháp thiết lập hệ truy hồi rất đa dạng, phong phú và mức độ khó dễ khác nhau. Để làm rõ được cách vận dụng phương pháp chúng tôi xin đưa ra một số bài toán sau đây. II. Một số bài toán vận dụng phƣơng pháp thiết lập hệ thức truy hồi Bài 1: Từ các chữ số 1, 2, 3 có thể lập được bao nhiêu số tự nhiên có 2017 chữ số sao cho mỗi chữ số 1, 2, 3 xuất hiện đúng lẻ lần. Lời giải: Gọi xn là số các số tự nhiên được lập thành từ các chữ số 1, 2, 3 có n chữ số, lẻ và các chữ số trên xuất hiện lẻ lần. (*) Xét một số bất kì có chữ số nk 21 TH1 : số đó thỏa mãn điều kiện (*), có 3 cách thêm hai chữ số giống nhau vào cuối số đó, để được một số cón 2 chữ số thỏa mãn điều kiện bài toán. TH2 : số đó không thỏa mãn (*). Vì n lẻ nên trong trường hợp này có đúng 2 chữ số xuất hiện chẵn lần (gọi là a, b) và 1 chữ số xuất hiện lẻ lần. Nên trong trường hợp này có đúng hai cách thêm hai chữ số đó (ab hoặc ba) vào cuối để được một số có chữ số thỏa mãn điều kiện bài toán. nn Vây có xn 2 3 x n 2(3 x n ) x n 2.3 3
4. 3(32016 1) Từ đó tìm được x . 2017 4 Bài 2( Đề nghị DHĐBB 2013). Với n là số nguyên dương, một tập con của tập 1,2,3,..., n được gọi là tốt nếu sau khi ta sắp xếp thứ tự tăng các phần tử của nó thì thu được các số lẻ, chẵn, lẻ, theo thứ tự. Ví dụ các tập con tốt là 1,4,5,6 , 3,4,7, tập . Tập 2,3,4,7không là tập con tốt do nó bắt đầu bởi số chẵn . Tính số tập con tốt của tập 1,2,3,...,n. Lời giải: Gọi fn là số tập con tốt của . Ta lập hệ thức truy hồi của . + Nếu tập con tốt của không lấy n thì ffnn 1 . + Nếu tập con tốt của lấy n thì ffnn 2 . Vậy ta có fn f n 12 f n . Hơn nữa ff12 2, 3 15 Phương trình đặc trưng x2 x 10 x 2 nn 1 5 1 5 Suy ra fn A B 22 1 5 1 5 2 2 5 1 AB 2 22 A 55 Thay 2 giá trị đầu ta được 22 1 5 1 5 AB 3 2 B 22 55 4
5. Suy ra n n n 11 n 2 2 5 1 15 215 25115 115 fn 5 5 2 5 5 2 5 2 5 2 Bài 3 ( Đề chọn ĐT Hà Tĩnh 2016 -2017) : Cho tập S 1,2,3,...,2016 . Hỏi có bao nhiêu hoán vị (a1 , a 2 , a 3 ,..., a 2016 ) của tập S sao cho 2(a12 a ... ak ) k với  k 1,2,3,...,2016. Lời giải: Ta xét trường hợp S 1,2,3,...,n Gọi Fn là số hoán vị thảo mãn tính chất Ta có FFF1 1; 2 2; 3 6. Xét một hoán vị (a1 , a 2 , a 3 ,..., an ) thỏa mãn yêu cầu, ta gọi đó là hoán vị đẹp Với mỗi hoán vị đẹp ta đều có 2(a1 a 2 ... ann 1 ) ( n 1) n ( n 1) 2 a ( n 1) ((n 1)( n 2) 2( an 1)) ( n 1) n 1 2(ann 1) 0; n 1;2( n 1) a  1; ; n 2 n 1 TH1: Nếu a ta có n 2 2(a1 a 2 ... ann 2 ) ( n 2) ( n ( n 1) 2 a 1 ( n 1)) ( n 2) ((n 2)( n 2) (2 an 1 3)) ( n 2) 3 n 11 2ann 11 3 0; n 2;2( n 2) a  ; ;n 2 22 Ta thấy cả 3 trường hợp này đều không thỏa mãn TH2: Nếu ann , ta có (a1 , a 2 , a 3 ,..., an 1 ) là một hoán vị đẹp của tập S1 1,2,3,...,n 1 . Có Fn 1 hoán vị của tập . 5
6. Bổ sung vào cuối mỗi hoán vị ta được một hoán vị đẹp của tập và ngược lại TH3 : Nếu an 1 ta thấy (a1 1, a 2 1,,..., an 1 1) là một hoán vị đẹp của tập Mỗi hoán vị đẹp (b1 ,b 2 ,b 3 ,...,bn 1 ) của tập cho ta một hoán vị đẹp (b1 1,b 2 1,b 3 1,...,bn 1 1;1) của tập và ngược lại Vì có hoán vị đSẹ p 1,2,3,...,n của tập nên có hoán vị đẹp của tập Suy ra FFnn 2 1 Từ giả thiết (a1 , a 2 , a 3 ,..., an ) F1 1 F2 2 n 2 Fn 3.2 F3 6 FFnn 2 1 2014 Vậy F2106 3.2 n Bài 4: Cho số nguyên dương n . Có bao nhiêu số tự nhiên chia hết cho 3, có n chữ số và các chữ số đều thuộc {3,4,5,6}? Lời giải: . Gọi xn là số các số có n chữ số lập từ {3,4,5,6} và chia hết cho 3, yn là số các số có n chữ số lập từ {3,4,5,6} và không chia hết cho 3. . Xét 1 số có n chữ số thoả mãn bài toán là x a12 a... an TH1: Nếu a1 a 2... an 1 3thì xa33 n , do đó có 2 cách chọn an . Như vậy S 1,2,3,...,n 1 F 1 trường hợp nàyn có 1 2 xn 1 cách chọn x . 6
7. TH2: a1 a 2... an 1 không chia hết cho 3. Khi đó ta chỉ chọn được 1 số thuộc {3,4,5,6} để x a12 a... an 3 . Như vậy trường hợp này có yn 1 cách chọn x . Như vậy ta có: xn 2. x n 11 y n Tương tự ta thu được: yn 2. x n 11 3. y n Biến đổi ta thu được xn 11 5 x n 4 x n 0. Giải phương trình sai phân này với chú ý rằng xx12 2; 6 ta tìm được 42n x n 3 Bài 5 ( THTT 5/2010).Từ các số 1,2,3,4,5 có thể lập được bao nhiêu số tự nhiên có n chữ số sao cho trong mỗi số đó đều chứa một số lẻ các chữ số 1 và một số chẵn các chữ số 2 ( n là một số nguyên dương cho trước)? Lời giải: Với mỗi số nguyên dương n , kí hiệu Mn là tập tất cả các số tự nhiên có n chữ số được lập từ các số 1,2,3,4,5,và ABCDn;;; n n n là tập các số tự nhiên có n chữ số được lập từ các số 1,2,3,4,5 theo tứ tự chứa một số lẻ các chữ số 1 và chẵn các chữ số 2, chứa một số lẻ các chữ số 1 và lẻ các chữ số 2, chứa một số chẵn các chữ số 1 và chẵn các chữ số 2, chứa một số chẵn các chữ số 1 và lẻ các chữ số 2. Dễ thấy ABCDn,,, n n n đôi một rời nhau và MABCDn n  n  n  n , 15n ABCDM . n n n n44 n Lấy một phần tử của Mn 1 , bỏ đi phần tử cuối ta được một phần tử của Mn , ngược lại lấy một phần tử x của Mn an -Nếu xA n thì có 3 cách thêm vào chữ số cuối để tạo ra một phần tử của . 7
8. -Nếu xB n thì có 1 cách thêm vào chữ số cuối để tạo ra một phần tử của An 1 . - Nếu xC n thì có 1 cách thêm vào chữ số cuối để tạo ra một phần tử của . - Nếu xD n thì không có cách thêm nào vào chữ số cuối để tạo ra một phần tử của . n Vậy AABCAABCDAn 1 35 n n n n n n n n n 5nn 1 1 5 1 Từ AAAAAA 1, 5nn 5 52 ... 5 1n 1 n n 1 1 44 n Bài 6: Cho số nguyên n 2. Hãy tìm số các hoán vị a12, a ,..., an của 1,2,...,n sao cho tồn tại duy nhất một chỉ số in {1,2,..., 1} thoả mãn aaii 1 . Lời giải: Gọi Sn là số các hoán vị thoả mãn điều kiện bài toán. . ann số các hoán vị có dạng a1, a 2 ,..., an 1 , n là Sn 1 n 2 . ann 1 số các hoán vị có dạng a1, a 2 ,..., ann 2 , n , a là Cn 1 i 1 . ani số các hoán vị a12, a ,..., an thoả mãn là Cn 1 với in 1; 1. n 1 in 11 Do vậy ta có SSCSn n 1  n 1 n 1 21 i 1 Lại có S 1nên Sn 2n 1. 2 n Bài 7: Cho tập Sn {1;2;...; } với n là số nguyên lớn hơn 2. Tìm số tập con của tập S sao cho trong mỗi tập con đều có ít nhất hai phần tử là hai số nguyên liên tiếp. Lời giải: 8
9. Gọi Sn là tập hợp các tập con khác  của tập {1;2;...;n } mà trong mỗi tập con không có hai phần tử nào là hai số nguyên liên tiếp. Chia các phần tử của thành hai nhóm: S . Nhóm không chứa phần tử n : Số các tập con như vậy là n 1 ; . Nhóm chứa phần tử n : {}n hoặc {a ; a ;...; a ; n } (1 k n 1) 12 k Rõ ràng ai n 1( i 1,2,..., k ) nên số các tập con như vậy là Sn 2 1 Do vậy SSSn n 12 n 1 Với chú ý SS23 2, 4 , ta có nn 22 1 1 5 1 5 Sn 1 5 22 Mặt khác, số tập con khác của tập là 21n . Vậy số tập con thoả mãn đề bài là nn 22 1 1 5 1 5 2n 5 22 Bài 8: Cho số nguyên n 1. Tìm số các bộ số nguyên a12, a ,..., an thoả mãn a 1với  in1,2,..., và aa 1 in 1,2,..., 1. i ii 1 Lời giải: .Trong tập Sn các bộ số nguyên thoả mãn bài toán, gọi ABCn,, n n lần lượt là tập hợp các bộ có an bằng 1,0,1 tương ứng. Ta có SABCn n n n . .Mặt khác, dễ thấy từ mỗi bộ thuộc An hoặc Bn , ta có thể bổ sung an 1 1 để được một bộ thuộc An 1 nên AABn 1 n n . .Tương tự ta có CCBn 1 n n và BABCSn 1 n n n n 9
10. Từ đó ta có: SABCn 1 n 1 n 1 n 1 ABCBBn n n n 1 n 2 SSnn 1 nn 11 1 2 1 2 Kết hợp với SS 7, 17 ta tính được S . 23 n 2 Bài 9: Cho số nguyên dương n . Có bao nhiêu số tự nhiên có chữ số, trong mỗi số các chữ số đều lớn hơn 1 và không có hai chữ số khác nhau cùng nhỏ hơn 7 đứng cạnh nhau? Lời giải: Kí hiệu X n là tập tất cả các số tự nhiên có chữ số thoả mãn đề bài, ABnn, là các tập con của theo thứ tự gồm các số có tận cùng nhỏ hơn 7; các số có tận cùng lớn hơn 6. Ta có = ABABXABn n, n  n  n n n Lấy một phần tử của X n 1 bỏ đi chữ số tận cùng ta được một phần tử của X n . Nếu chữ số tận cùng nhỏ hơn 7 (thuộc An ) thì chỉ có 1 cách thêm vào chữ số cuối để được 1 phần tử của An 1 và có đúng 3 cách thêm vào chữ số cuối để được 1 phần tử của Bn 1 . Nếu chữ số tận cùng lớn hơn 6 (thuộc Bn ) thì có 5 cách thêm vào chữ số cuối để được 1 phần tử của và có đúng 3 cách thêm vào chữ số cuối để được 1 phần tử của . Từ các lập luận trên ta có: AABn 1 n5 n (1) BABn 1 3 n 3 n (2) Từ (1) và (2) suy ra ABABABBn 11 n 4 n 8 n 4 n n 4 n 10
11. 4 An B n 12 A n 11 B n ( n 2) Kí hiệu xXnn , ta có xn 21 x n 12 x n , n N *. Từ đó ta có: n xn 2 6 x n 1 2 x n 1 6 x n xnn 2 6 x 1 ( 2) x 2 6 x 1 x 2 x 6 x 2 x n n 2 n 1 n 1 n xnn 2 2 x 1 (6) x 2 2 x 1 1 x [( x 2 x ).6nn ( x 6 x ).( 2) ] n 18 2 1 2 1 Dễ thấy x1 8, ta tìm x2 . Xét u X2 u ab; a , b {2,3,4,5,6,7,8,9} . Nếu a {2,3,4,5,6} thì có 4 cách chọn b . Nếu a {7,8,9} thì có 8 cách chọn 1 Vậy x 5.4 3.8 44 . Do đó x [15.6nn 11 ( 2) ]. 2 n 2 Bài 10: Kí hiệu fn là số hoán vị a12, a ,..., an của 1,2,...,n thoã mãn đồng thời các điều kiện: 1)a1 1 2)aii a 1 2,  i 1,2,..., n 1 Hỏi f 2013 có chia hết cho 3 không? Lời giải: Ta xét với n 5. Do a1 1 và aa12 2 nên a2 2 hoặc a2 3. +) Nếu a2 2 thì a23, a ,..., an là hoán vị của 2,3,...,n thoả mãn i. a2 2 ii. aii a 1 2,  i 2,3,..., n 1 Số các hoán vị như vậy chính là fn 1 11
12. +) Nếu thì a3 {2,4,5} Giả sử có ak 2(3 k n ) thì do aakk 1 2, aakk 1 2 và aakk 1, khác 1, 2, 3 nên aakk 11 4 vô lí. Vậy a3 2 hoặc an 2 . Nếu thì a4 4 , do đó a45, a ,..., an là hoán vị của 4,5,...,n thoả mãn i. a4 4 ii. aii a 1 2,  i 4,5,..., n 1 Số các hoán vị như vậy chính là fn 3 Nếu thì an 1 4 nên a3 5, kết hợp với giả thiết suy ra ann 2 6, a 4 7, a 3 8,... Cứ như thế chỉ có một hoán vị thoả mãn. Dễ dàng tính được f 2 1, f 3 2, f 4 4 Tóm lại, ta có hệ thức truy hồi: f n f n 1 f n 3 ,  n 5 Khi đó ta chứng minh được dãy {fn ( )(mod3)}n 2 là dãy tuần hoàn chu kì 2, do đó: ff 2013  3 2(mod3) f 2013 Vậy không chia hết cho 3. Bài 11: Cho tập hợp S = {1, 2, 3, , n}. Tìm số cách chia tập S thành 3 tập con a 3 khác rỗng sao cho mỗi tập con không chứa hai số nguyên liên2 tiếp. Lời giải: Kí hiệu S(n) là số cách chia tập S thành 3 tập con không chứa khác rỗng mà bất kì tập con nào cũng không chứa 2 phần tử liên tiếp nhau . Ta sẽ tìm cách tính S(n+1) theo S(n) 12
13. Giả sử ta đã chia được 3 tập con và tổng số phần tử của chúng là n. Bổ sung thêm phần tử n+1. Sẽ có 2 khả năng xảy ra: - Khả năng 1: n+1 không tạo thành 1 tập con mới (tức tập chứa n + 1 có ít nhất 1 phần tử khác) Khi đó, rõ ràng ta có 2 cách bổ sung n+1 (vào 1 trong 2 tập không chứa n). Vậy số cách xây dựng tập con trong trường hợp này là 2S(n) - Khả năng 2: n+1 tạo thành 1 tập con mới. Khi đó, n số từ 1 đến n phải nằm trong hai tập hợp còn lại. Có thể thấy ngay chỉ có 1 cách chia thỏa mãn (1 tập chứa các số chẵn và tập còn lại chứa các số lẻ). Do đó, số cách trong trường hợp này là 1 cách Vậy ta thu được công thức truy hồi S(n+1)=2S(n)+1 Mặt khác, kiểm tra trực tiếp ta có S(3)=1, nên : S n12 S n 1 S n 112 S n 1 S n 112.n 1 Như vậy, sô cách chia tập hợp thỏa mãn đề bài là S(n) 2n2 1, S(1) S(2) 0 Bài 12. Một con xe được đặt trên bàn cờ kích thước 3 n , với nN *. Con xe đi từ vị trí (1,1) đến vị trí (3,1) bằng một đường đi không tự cắt. Hỏi có bao nhiêu đường đi như thế trên bàn cờ ? Giải Gọi số đường đi là rn . Có 6 cách đi như các hình vẽ sau : 1) Đường đi qua các ô (1,1), (2,1), (3,1). Có 1 đường đi loại này. 2) Đường đi không qua ô (2,1) . Mỗi đường đi loại này bắt đầu là (1,1) (1,2) và 13
14. kết thúc là (3,2) (3,1). Có rn 1 đường đi loại này. 3) Đường đi bắt đầu là (1,1) (2,1) (2,2) và không trở lại hàng 1. Mỗi đường đi như vậy đến hàng 3 từ ô (2,k ) , với 2 kn và di dọc theo hàng 3 đến ô (3,1) . Có n 1 đường đi loại này. 4) Đường đi bắt đầu là (1,1) (2,1) (2,kkk ) (1, ) (1, 1) , kết thúc là (3,kk 1) (3, ) (3,1), với 21 kn . Có rnn 2 r 3 r 1 đường đi loại này. 5) Đường đi bắt đầu là (1,1) (1,2) và kết thúc là (2,1) (3,1). Có n 1 đường đi loại này. 6) Đường đi là (1,1) (1,2) (1,k ) (1, k 1) (2, k 1) (3, k 1) (3, k ) (2,k ) (2,1) (3,1) . Có rnn 3 r 2 r 1 đường đi loại này. ậy rrnn 1 n 1 2( 1) 2( rr n 2 n 3 rnrrr 1 ) 2 1 n 1 2( n 2 n 3 r 1 ). Suy ra rn 1 2 n 1 r n 2( r n 1 r n 2 r 1 ) . Do đó rn 1 r n2 r n r n 1 r n 1 2 2 r n r n 1 r n 1 1 2( r n 1) r n 1 1. Dễ thấy r1 1, r2 4. Sử dụng phương trình đặc trưng tìm được 1 nn 11 r 1 2 1 2 1 n 22 Bài 13. Cho một bảng hình vuông gồm nn ô vuông. Hỏi có bao nhiêu cách tô hai màu xanh hoặc đỏ vào các ô vuông trong bảng sao cho mỗi hình vuông 22 có số ô được tô bởi hai màu bằng nhau. ( Hai cách tô được gọi là khác nhau nếu có một ô vuông nào đó mà trong cách này thì được tô màu đỏ còn cách kia thì được tô màu xanh). Lời giải: Gọi Sn là số cách tô trong bảng n n,  n 1. Xét tập Tn gồm các ô vuông nằm trong cột n (tính từ trái sang) và hàng n (tính từ trên xuống). Ta gọi An là số các 14
15. cách tô sao cho hai ô kề nhau trong Tn có cùng màu và Bn là số các cách tô sao cho các ô trong có màu xen kẽ. Nhận xét 1: mỗi cách tô thuộc sẽ ứng với một cách tô thuộc Bn 1 , còn mỗi cách tô thuộc sẽ ứng với một cách tô thuộc An 1 và một cách tô thuộc . ( Điều này suy ra khi xét bảng ô vuông nn 11 có được từ bảng nn sau khi bỏ ) Nhận xét 2: Mỗi cách tô thuộc sẽ ứng với một cách tô thuộc Tn 1 , Mỗi cách tô thuộc Tn 1 sẽ ứng với một cách tô thuộc Tn 2 , Từ đó ta có: Bn B n 1, A n A n 1 B n 1 ,  n 2 Sn A n B n A n 11 B n B n ,  n 2 Suy ra: Sn 2( A n 1 B n 1 ) ( A n 2 B n 2 ),  n 3 = 2Snn 12 S ,  n 3 (1) Nhận xét 3: S2 6 và S3 14 Đ X X Đ X X Đ Đ X Đ Đ X X Đ Đ X Đ Đ X X X Đ Đ X X Đ X Đ X Đ X Đ Đ Đ Đ X Đ X Đ X Đ X X X X X Đ X X Đ X Đ X X X X Đ X Đ X X Đ X Đ Đ Đ Đ X Đ X Đ X X Đ Đ Đ Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ SSSSSS = . . . = 8 An TĐừ (1)X Đta suy Đ raX Đ n X n 1Đ Đ n 1 Đ n Đ 2 X Đ 3 X 2Đ Đ X Đ X X X X Đ X Đ X Đ Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ 15
16. Sn 8 S n 12 S n S ( n 2)8 8 n 10 Từ (1) ta suy ra Bài 14: Xếp 10 học sinh ngồi quanh một bàn tròn. Ngân hàng đề có tất cả 5 loại đề thi. Hỏi có bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi? Lời giải Gọi Sn là số cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi Cố định một học sinh làm vị trí đầu tiên và các học sinh bên tay phải của học sinh đó là vị trí thứ 2, thứ 3, , thứ n.( học sinh ở vị trí thứ n ngồi cạnh học sinh ở vị trí thứ nhất) Ta thấy: Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi khác nhau thì sẽ có 3 cách phát đề cho học sinh ở vị trí thứ n. Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi giống nhau thì có 4 cách phát đề cho học sinh ở vị trí thứ n. Do đó ta có hệ thức: S 3S 4 n 4 n n 1 Sử dụng phương pháp sai phân để tính . Xét phương trình đặc trưng: x2 3x 4 0 x 1 x 4 nn Sn a( 1) b 4 Do SS23 5.4 20, 5.4.3 60 Ta có: a 16 b 20 a 4 a 64 b 60 b 1 n n 10 Vậy Sn 4 1 4 S 10 4 4 SSSSSSn n 1 = n 1 n 2 . . . = 3 2 8 16
17. Bài 15 (IMO 2011). Giả sử n 0 là một số nguyên. Cho một cái cân đĩa và n quả cân có khối lượng lần lượt là 20 ,2 1 ,2 2 ,...,2n 1 . Ta muốn đặt lên cái cân mỗi một trong quả cân, lần lượt từng quả một, theo cách để đảm bảo đĩa cân bên phải không bao giờ nặng hơn đĩa cân bên trái. Ở mỗi bước ta chọn một trong các quả cân chưa được đặt lên rồi đặt nó lên đĩa bên phải, hoặc đĩa bên trái, cho đến khi tất cả các quả cân đều được đặt lên đĩa. Hỏi có bao nhiêu cách để thực hiện việc đặt cân theo đúng mục đích đặt ra? Lời giải: Gọi sn là số cách để thực hiện việc đặt cân theo đúng mục đích đặt ra. Xét cách đặt n 1 quả cân có khối lượng 20 ,2 1 ,2 2 ,...,2n . Do 20 2 1 2 2 ... 2n 1 2 n 1 2 n nên trong mọi cách đặt cân thoả mãn bài toán thì quả cân có khối lượng 2n luôn được đặt ở đĩa cân bên trái. Nếu quả cân được chọn cuối cùng: chỉ có một cách đặt ( vì quả chỉ đặt lên đĩa bên trái ) và số cách đặt n quả cân còn lại là . Nếu quả cân được đặt ở bước thứ i( i 1,2,..., n ) . Khi đó có cách chọn i và trong trường hợp này quả cân 2n 1 có 2 cách đặt ( đĩa bên phải hay bên trái đều thoả mãn ), do đó số cách đặt n 1 quả cân trong trường hợp này là 2.nsn . Vậy ta có hệ thức truy hồi: sn 1 2 n . s n s n 2 n 1 s n Ta có s1 1 nên sn 2 n 1 2 n 3 ...3.1. Bài 16 (VMO 2009): Cho số nguyên dương n . Kí hiệu T là tập hợp gồm 2n số nguyên dương đầu tiên. Hỏi có tất cả bao nhiêu tập con S của T có tính chất: trong không tồn tại các số ab, mà a b{1; n }? Lời giải: * Với mỗi nN , kí hiệu dn là số cần tìm theo yêu cầu đề bài. Xét bảng ô vuông kích thước 2 n. Điền vào các ô vuông con của bảng, lần lượt từ trái qua phải, từ trên xuống dưới, các số từ 1 đến 2n. 17
18. 1 2 n 1 n n 1 n 2 21n 2n Gọi ô thứ n của hàng 1 và ô thứ 1 của hàng 2 là hai ô đặc biệt. Khi đó hai số ab, T thoả a b{1; n } khi và chỉ khi chúng nằm ở 2 ô kề nhau hoặc ở 2 ô đặc biệt. Vì thế chính bằng số cách chọn 1 số ô của bảng (kể cả số ô được chọn bằng 0) mà ở mỗi cách không có 2 ô kề nhau hoặc 2 ô đặc biệt được chọn. Với mỗi nN * , kí hiệu +/ kn là số cách chọn mà ở mỗi cách không có 2 ô kề nhau được chọn (*) +/ sn là số cách chọn mà trong các ô được chọn ở mỗi cách có 2 ô đặc biệt và không có 2 ô kề nhau. Ta có: d k s n n n Tính kn Dễ thấy, tất cả các cách chọn ô thoả mãn điều kiện (*) bao gồm : +/kn 1 cách chọn mà ở mỗi cách không có ô nào thuộc cột 1 của bảng được chọn +/2tn 1 cách chọn mà ở mỗi cách đều có ô thuộc cột 1 của bảng được chọn; trong đó tn là số cách chọn ô thoả mãn điều kiện (*) của bảng khuyết đơn 2 n (h.2) x (h.2) Do đó kn k n 112 t n (1) d Lại có, tất cả các cách chọnn ô thoả mãn điều kiện (*) từ bảng khuyết đơn 2 n bao gồm: 18
19. +/ cách chọn mà ở mỗi cách ô đánh dấu “x” không được chọn; +/t cách chọn mà ở mỗi cách ô đánh dấu “x” đều được chọn. n 1 Vì thế tn k n 11 t n Từ đó và (1) suy ra kn k n 1 2( k n 2 t n 2 ) 2 k n 1 k n 2 (2) Bằng cách đếm trực tiếp, ta có kk12 3, 7 . Do đó ta tìm được nn 11 1 2 1 2 k (3) n 2 Tính sn Dễ thấy s1 0, s 2 s 3 1 và với n 4 ta có: shnn 2 , trong đó hn là số cách chọn ô thoả mãn điều kiện (*) từ bảng khuyết kép 2 n (h.3) A B (h.3) Do s3 1, đặt h1 1. Bằng cách đếm trực tiếp, ta có h2 4 . kn 1 Xét n 3. Dễ thấy, tất cả các cách chọn ô thoả mãn điều kiện (*) từ bảng khuyết kép 2 n bao gồm: +/kn 2 cách chọn mà ở mỗi cách cả 2 ô A và B đều không được chọn; +/2tn 2 cách chọn mà ở mỗi cách có đúng 1 trong 2 ô A, B được chọn; +/th 2 cách chọn mà ở mỗi cách cả 2 ô A, B cùng được chọn. Do đó hn k n 2 2 t n 2 h n 2 k n 1 h n 2 (4) Từ (2) và (4) suy ra 2hn k n 2 h n 22 k n ,  n 3 19
20. n Dẫn tới 2hnn k 1 ,  n 1. k ( 1)n 2 Vì thế s h n 2 ,  n 3. nn 2 2 Vậy dd 3, 6 12 2kk ( 1)n 3 d nn 2 ,  n 3 k theo (3) nn2 Bài 17: Có n quả bóng b12, b ,..., bn và 2n hộp h1, h 2 ,..., h 2n . Biết rằng quả bóng bi i 1,2,..., n chỉ bỏ được vào các hộp h1, h 2 ,..., h 2i . Hỏi có bao nhiêu cách bỏ k 1 k n quả bóng vào các hộp, biết rằng mỗi hộp chứa nhiều nhất một quả bóng? (Hai cách bỏ bóng được gọi là khác nhau khi có ít nhất một quả bóng được bỏ vào hai hộp khác nhau trong hai cách đó) Lời giải: Đặt Snk, là số cách bỏ k quả bóng vào các hộp. Giả sử 2 kn. Nếu một trong quả bóng được chọn là bn thì k 1 quả bóng còn lại có thể bỏ vào các hộp bằng Snk 1, 1 cách. Đồng thời, có 2n ( k 1) 2 n k 1 cách chọn một hộp trong các hộp còn lại để bỏ. Do đó số cách bỏ bóng trong trường hợp này là: 2n k 1 . Snk 1, 1 Trường hợp quả bóng không được chọn, lưu ý rằng kn 1. Mọi quả bóng trong các quả bóng b1, b 2 ,..., bn 1 đều có thể bỏ vào các hộp bằng Snk 1, cách, suy ra Sn, k S n 1, k 2 n k 1 S n 1, k 1 n 3, 2 k n Nhận thấy Sn, n n 1 S n 1, n 1 ; S n ,1 n n 1 ; S 1,1 2 k 2 n 1! k Cn Từ đó bằng quy nạp ta chứng minh được S . nk, nk 1 20