Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Tổ hợp (Phần 5) - Ngô Tùng Hiếu

Nội dung text: Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Tổ hợp (Phần 5) - Ngô Tùng Hiếu

1. Câu 1. Cho 100 số tự nhiên không lớn hơn 100 có tổng bằng 200. Chứng minh rằng từ các số đó có thể chọn được một số số có tổng bằng 100. Hướng dẫn giải Nếu tất cả các số bằng nhau thì tất cả các số là 2. Khi đó ta lấy 50 số 2 sẽ có tổng là 100. Giả sử a1 a 2 ta xét 100 số có dạng 0 a1,a 2 ,a1 a 2 ,a1 a 2 a3 , ,a1 a 2 a99 200 . Nếu có một số chia hết cho 100 thì số đó bằng 100 vì số đó bé hơn 200. Nếu không có số nào chia hết cho 100 thì trong 100 số phải có hai số đồng dư trong phép chia cho 100 (vì các số dư nhận giá trị từ 1 đến 99) suy ra hiệu của chúng chia hết cho 100 và hiệu hai số đó chính là tổng cần tìm. 1 Câu 2. Cho hình vuông có cạnh 6cm và 2014 đường tròn bán kính cm. Đặt tất cả các đường tròn 38 vào trong hình vuông. Chứng minh rằng tồn tại một đường thẳng cắt 18 đường tròn đã cho. Hướng dẫn giải +) Chia hình vuông bởi 117 đường thẳng song song cách đều nhau và song song với một cạnh 6 của hình vuông, cách nhau một khoảng cm. Khi đó hình vuông được chia thành 118 dải 118 6 hình chữ nhật có chiều rộng bằng cm, chiều dài bằng chiều dài hình vuông. 118 1 1 6 +) Hình tròn có đường kính cm, > nên mỗi đường tròn đều bị cắt bởi ít nhất một 19 19 118 đường thẳng trên. +) Vì 2014 = 118. 17 + 8 nên theo nguyên lí Dirichlet tồn tại một đường thẳng cắt 18 đường tròn. 0 .30 2 .32 4 .34 2n.32n 22n 1 22n 1 Câu 3. Chứng minh: C 2n C 2n C 2n C 2n Câu 4. Cho đa giác đều A1 A2 A2n , ( n 2 , n nguyên) nội tiếp đường tròn (O). Biết rằng số tam giác có các đỉnh là 3 trong 2n điểm A1, A2 , , A2n nhiều gấp 20 lần số hình chữ nhật có các đỉnh là 4 trong 2n điểm A1, A2 , , A2n . Tìm n. 20 C0 21C1 22 C 2 23 C 3 22010 C 2010 A 2010 2010 2010 2010 2010 Câu 5. Tính 1 2 3 4 2011 . Hướng dẫn giải k k k k k 2 C 2 2010! 2 2010! 1 2010 k 1 k ! 2010 k ! k 1 2010 k ! k 1 ! k 1 2 2011! 1 k 1 . . 2 C k 1 2011 k 1 ! 2011 k 1 ! 4022 2011 1 1 2 2011 A 2 C1 2 C 2 2 C 2011 4022 2011 2011 2011 1 2011 0 1 2 1 2 C0 . 4022 2011 2011
2. Câu 6. a) Tìm hệ số của số hạng chứa x4 trong khai triển: (1 + 2x + 3x2)10. 0 1 2 k n Cn Cn Cn Cn Cn * b) Tính tổng: S = 1 2 3 k 1 n 1 (với n N ). Cn 2 Cn 3 Cn 4 Cn k 2 C2n 2 10 2 2 14 Câu 7. Cho khai triển S 1 2x x x 1 a0 a1 .x a14 .x . Tính a6 . Câu 8. Chọn ngẫu nhiên ba số đôi một khác nhau từ tập hợp A 1; 2;3;; 20 . Tính xác suất để trong ba số được chọn không có hai số tự nhiên liên tiếp. Câu 9. 1. Cho 6 chữ số 1,2,3,4,5,6 . Hỏi có bao nhiêu cách viết số có 3 chữ số khác nhau và không nhỏ hơn 243 . 2. Hai hộp có chứa các quả cầu. Hộp thứ nhất 3 quả cầu đỏ và 2 quả cầu xanh, hộp thứ hai chứa 4 quả cầu đỏ và 6 quả cầu xanh. Lấy ngẫu nhiên từ mỗi hộp một quả. Tính xác suất sao cho: a. Cả 2 quả đều đỏ. b. Hai quả cùng màu. c. Hai quả khác màu. Câu 10. Cho các số 1, 2, 3, 4 . 1) Hỏi lập được bao nhiêu số có 5 chữ số trong đó có hai chữ số 1 và ba chữ số còn lại khác nhau và khác số 1 . 2) Tính tổng các số lập được ở câu 1). Hướng dẫn giải 1) Mỗi số có 5 chữ số gồm 2 số 1 và 3 số khác là hoán vị 5 phần tử 1,1,2,3,4 ; do 2 chữ số P 1 khi hoán vị vẫn được 1 số. Vậy các số cần lập là 5 60. P2 2) Số có 5 chữ số dạng abcde . S abcde 104.a 103.b 102.c 10.d e Mỗi số a có 4! cách chọn bcde Mỗi số a 1,1,2,3,4 xuất hiện 4! lần. a (1 1 2 3 4).24 264 Tương tự b c d e 264 264.11111 Vậy S 1466652. 2! Câu 11. Một đội thanh niên tình nguyện có 15 người gồm 10 nam và 5 nữ. Hỏi có bao nhiêu cách phân công đội thanh niên đó về 3 tỉnh công tác sao cho mỗi tỉnh có 5 người và có ít nhất một nữ. 2 10 2 12 Câu 12. Cho khai triển 1 x 1 3x a0 a1 x a2 x a12 x . Hãy xác định a5. Câu 13. Cho tập A = {0;1;2;3;4;5;6;7}. 1. Có bao nhiêu cách chia tập A thành hai tập con khác rỗng. 2. Lập được bao nhiêu số tự nhiên gồm 5 chữ số khác nhau từ tập A. Lấy ngẫu nhiên một số trong các số vừa lập, tính xác suất để số chọn được là số chia hết cho 4. n 2 Câu 14. Tìm số hạng không chứa x của khai triển nhị thức x2 . Biết rằng: x3
3. 320 1 C0 22 C2 24 C4 22(n 1) C2(n 1) 22n C2n . 2n 2n 2n 2n 2n 2 Câu 15. Có bao nhiêu số tự nhiên gồm 6 chữ số khác nhau trong đó có 3 số chẵn và 3 số lẻ ? Câu 16. Cho k là số tự nhiên thỏa mãn 5 k 2011. 0 k 1 k 1 5 k 5 k Chứng minh rằng: C5.C2011 C5.C2011 C5.C2011 C2016 Câu 17. Giả sử có 20 người, xếp ngồi vào 4 bàn riêng biệt. Cách xếp tốt là những người ngồi cùng bàn đều quen nhau. Giả sử tồn tại cách xếp tốt, đồng thời đối với mọi cách xếp tốt, ta đều có đúng 5 người ngồi mỗi bàn. Hỏi có nhiều nhất bao nhiêu cặp quen nhau ? Hướng dẫn giải Xét nhân vật A thuộc bàn 1, suy ra trong mỗi bàn 2, 3, 4 đều có ít nhất một người không quen A. Vì nếu quen hết 5 người trong 1 trong các bàn 2, 3, 4 thì A phải sang bàn đó, nhưng lại là 6 người (trái với giả thiết là 5 người). Suy ra số người mà A không quen lớn hơn hoặc bằng 3 người. Do đó mỗi người quen nhiều nhất là 16 người. 20.16 Mà số cặp quen nhau nhỏ hơn hoặc bằng 160. 2 3.20 Giả sử có đúng 160 cặp quen nhau thì có đúng 30 cặp không quen nhau. 2 Suy ra có thể xếp thành 5 nhóm, mỗi nhóm 4 người không quen nhau. Mỗi người đều quen với những người thuộc 4 nhóm còn lại. Ghép người đó với mỗi nhóm 1 người vào một bàn, ta được cách xếp tốt. Câu 18. Cho trước số nguyên dương n 2 . Trong một giải đấu cờ vua có 2n vận động viên tham gia, mỗi người đấu với người khác đúng một ván. Tại một thời điểm trong giải, người ta thấy có n2+1 ván đấu đã diễn ra. Chứng minh rằng khi đó có thể chọn ra ba vận động viên sao cho hai người bất kỳ đều đã thi đấu với nhau. Hướng dẫn giải Ta chứng minh bằng quy nạp theo n. Với n = 2: Giả sử có bốn vận động viên theo dự là A, B, C, D và có 5 ván đấu đã diến ra. Nếu hai trong ba người B, C, D đều đã đấu với nhau một ván thì ta có điều phải chứng minh. Nếu có hai trong ba người B, C, D chưa đấu với nhau thì mỗi người B, C, D đều đã đấu với A một ván. (Nếu không thì số ván sẽ ít hơn 5). Khi đó ba người A, B, C thỏa mãn yêu cầu bài toán. Giả sử bài toán đúng với n = k (k N*,k 2) Ta chứng minh bài toán đúng với n = k + 1. Giả sử E và F là hai vận động viên đã đấu với nhau. Nếu tổng ván đấu giữa 2k vận động viên còn lại không ít hơn k2+1 thì theo giả thiết quy nạp ta có điều phải chứng minh. Nếu tổng số ván đấu giữa 2k vận động viên không vượt quá k2 tổng số ván mà E và F đã đấu không ít hơn 2k+1(không kể ván đấu giữa E và F). Do đó trong số 2k vận động viên còn lại, phải có một người G đã đấu với cả E và F. Khi đó ta có ba vận động viên E, F, G thỏa yêu cầu bài toán. Vậy bài toán được chứng minh. 1 2 Câu 19. Tìm số hạng không chứa x của khai triển: A ( 3x )13 . x x3 Hướng dẫn giải
4. Số hạng tổng quát thứ k+1 trong khai triển của A có dạng: 1 2 T C k ( 3x )13 k ( )k k 1 13 x x3 k 13 k k 10 2k =2C13 3 ( 1) x Số hạng Tk+1 không chứa x thì 10-2k=0 k=5 5 8 5 Vậy số hạng không chứa x của khai triển là: T6 =2C133 ( 1) 16888014 . Câu 20. Từ các chữ số 1, 2, 3 có thể lập được bao nhiêu số tự nhiên có 2013 chữ số sao cho mỗi chữ số 1, 2, 3 xuất hiện đúng lẻ lần. Câu 21. Trong mặt phẳng cho 2n 1 (n ¥ *) đường thẳng phân biệt sao cho không có hai đường nào song song hoặc vuông góc và không có ba đường nào đồng quy. Chúng cắt nhau tạo thành các tam giác. Chứng minh rằng số các tam giác nhọn tạo thành không vượt quá n n 1 2n 1 . 6 Hướng dẫn giải Gọi số tam giác tạo thành là f n . Ta phải chứng minh n n 1 2n 1 f n 1 ,n ¥ * 6 Với ba đường thẳng bất kỳ trong số các đường thẳng đã cho luôn cắt nhau tạo thành một tam giác hoặc nhọn hoặc tù. Gọi g n là số các tam giác tù. Ta gọi một tam giác tạo bởi ba đường thẳng a,b,c nào đó là: "giả nhọn cạnh a " nếu các góc chung cạnh a của tam giác đó là các góc nhọn. Chọn một đường thẳng d nào đó và coi nó là trục hoành, các đường thẳng còn lại được chia làm hai tập: Tập T là các đường thẳng với hệ số góc dương, Tập T là tập các đường thẳng với hệ số góc âm. Hai đường thẳng tạo với d một tam giác "giả nhọn" nếu một đường thẳng thuộc tập T và một đường thẳng thuộc tập T . Gọi p là số đường thẳng thuộc T và q là số các đường thẳng thuộc tập T . Khi đó p q 2 p q 2n và số tam giác "giả nhọn cạnh d " là pq . Ta có pq n 2 Nhưng do d có thể là đường thẳng bất kỳ trong số 2n 1 đường thẳng đã cho nên ta có số cặp (đường thẳng d ; tam giác "giả nhọn cạnh d") sẽ nhỏ hơn hoặc bằng n2 2n 1 . Trong cách tính trên mỗi tam giác nhọn được tính 3 lần (theo 3 cạnh) còn mỗi tam giác tù được tính 1 lần nên 3 f n g n n2 2n 1 (1) Thế nhưng tổng số các tam giác là: 2n 1 2n 2n 1 C3 f n g n (2) 2n 1 6 Từ (1) và (2) suy ra (2n 1)2n 2n 1 2 f n n2 2n 1 f n g n n2(2n 1) 6
5. n(n 1)(2n 1) n n 1 2n 1 hay f n 3 6 . Câu 22. Cho đa giác đều 2n cạnh (n 4) nội tiếp đường tròn tâm O. Gọi x là số tứ giác lồi có 4 cạnh là 4 đường chéo của đa giác đã cho và y là số hình chữ nhật có 4 đỉnh là các đỉnh của đa giác đã cho. Tìm n để: x – y = 3n. (Đường chéo của đa giác là đoạn thẳng nối hai đỉnh không liên tiếp) Hướng dẫn giải Gọi các đỉnh của đa giác đều 2n cạnh là: A1; A2 ; ; A2n . Trước hết ta tìm x Ta đếm số các tứ giác thoả mãn yêu cầu bài toán có 1 đỉnh là A1 Khi đó A2 ; A2n không phải là đỉnh của tứ giác vì A1 A2 ; A1 A2n là các cạnh của đa giác. Ta cần chọn thêm các đỉnh: Ai ; AJ ; Ak thoả mãn 5 i 2 j 1 k 2n 1(Vì giữa 2 đỉnh của tứ giác phải có ít nhất 1 đỉnh của đa giác). Mỗi cách chọn bộ 3 đỉnh trên là 1 cách chọn bộ 3 số phân biệt trong 2n-5 số tự nhiên từ 5 đến 2n-1. 3 Vậy có C2n 5 tứ giác có đỉnh A1 thoả mãn yêu cầu bài toán. Vì đa giác có 2n đỉnh và mỗi tứ giác được đếm lặp lại 4 lần theo 4 đỉnh nên số tứ giác cần tìm 2nC3 2nC3 là: 2n 5 , do đó x= 2n 5 4 4 Tìm y: do đa giác đều đã cho có 2n đỉnh nên nó có n đường chéo đi qua tâm O Ta thấy cứ hai đường chéo bất kì qua O lập thành một hình chữ nhật, nên số hình chữ nhật có 4 2 2 đỉnh là 4 đỉnh của đa giác đều đã cho là Cn , do đó y = Cn . 2nC3 Từ giả thiết ta có phương trình: 2n 5 - C 2 = 3n (1) 4 n n (2n 5)! n! 1 (2n 7)(2n 6)(2n 5) n 1 (1) . 3n . 3 2 (2n 8)!3! (n 2)!2! 2 6 2 (n 5)(n2 4n 6) 0 n 5 Vậy n=5 thỏa mãn điều kiện bài toán. Câu 23. Cho n là số nguyên dương không nhỏ hơn 3. Các điểm A1; A2; ; An cùng thuộc một đường tròn. Có tối đa bao nhiêu tam giác nhọn có đỉnh là 3 trong số các đỉnh trên. Hướng dẫn giải Với hai điểm Ai ; Aj ta kí hiệu Ai Aj là cung bắt đầu từ Ai và kết thúc là Aj theo chiều kim đồng hồ và kí hiệu m Ai Aj là số đo của cung đó. Một cung được gọi là tù nếu o m Ai Aj 180 . o Nhận thấy m Ai Aj m Aj Ai 360 nên có ít nhất 1 trong hai cung này tù. Kí hiệu xs là số cung tù mà giữa hai đầu mút có đúng s – 1 điểm n Nếu s thì mỗi i có ít nhất một cung A A ; A A là tù, tổng theo i ta được 2 i i s i s i xs xn s n Đẳng thức trên xảy ra khi không có đường kính Ai Ai s . Nhận thấy số tam giác không nhọn (tù hoặc vuông) bằng số góc không nhọn.
6. Mỗi cung tù chứa s – 1 điểm thì có n – s – 1 tam giác không nhọn. (Dùng hai điểm đầu mút của cung kết hợp với 1 điểm ngoài cung) Số lượng các tam giác không nhọn là N x1 n 2 x2 n 3 xn 1.2 xn 2 Theo bất đẳng thức trên ta đánh giá được: n 1 2 n 3 n n 1 n 3 nếu n lẻ N  s 1 xn s xs n 1 2 s 1 2 8 n 1 2 2 n 2 n 4 n 2 n n n 2 N  s 1 xn s xs xn n 1 2 . s 1 2 2 2 2 2 8 Nếu n chẵn. Dấu bằng xảy ra ở các BĐT trên là không tồn tại 2 điểm đối xứng nhau qua tâm đường tròn. n n 1 n 2 Số lượng các tam giác có đỉnh là 3 trong các điểm trên là C3 . n 6 Vậy số tam giác nhọn là n n 1 n 2 n n 1 n 3 n 1 n n 1 nếu n lẻ 6 8 24 n n 1 n 2 n n 2 2 n 2 n n 2 Và nếu n chẵn. 6 8 24 Câu 24. Cho 2015 điểm trên đường thẳng, tô các điểm bằng một trong 3 màu xanh, đỏ, vàng (mỗi điểm chỉ tô một màu). Có bao nhiêu cách tô khác nhau sao cho không có 3 điểm liên tiếp nào cùng màu. Hướng dẫn giải Gọi Sn là số cách tô màu thỏa mãn cho n ( n 3 ) điểm (bài toán của ta là n 2015 ). Ta sẽ tính Sn 1 theo Sn , xét hai điểm cuối cùng của Sn có hai trường hợp xảy ra: +Nếu hai điểm cuối cùng màu thế thì điểm thứ n 1khác màu 2 điểm cuối. +Nếu hai điểm cuối khác màu thì điểm thứ n 1 tô bất kì. Từ đó sinh ra hai số đặc trưng M n là số cách tô n điểm mà hai điểm cuối cùng màu, Pn là số cách tô màu n điểm mà hai điểm cuối khác màu và cả hai cùng thỏa mãn 3 điểm liên tiếp khác màu. Ta có: Sn 1 2M n 3Pn , Pn 1 2Sn ;M n 1 Pn . Thế thì Sn 1 2Pn 1 6Sn 1 4Sn 2 6Sn 1 . Vậy ta có hệ thức truy hồi: Sn 1 6Sn 1 4Sn 2 0 . Bây giờ ta tính S3 , S4 thấy ngay S3 27 3 24 , S4 4! 3 12 49 . Phương trình đặc trưng 2 n n X 6X 4 0 có nghiệm là: x1 3 13, x2 3 13 . Công thức xác định Sn ax1 bx2 24 13 23 a a(3 13)3 b(3 13)3 24 2 13(3 13)3 với a,b thỏa mãn: a(3 13)4 b(3 13)4 49 24 13 23 b 3 2 13(3 13) Sau đó cho n 2015 ta được kết quả bài toán.
7. Câu 25. Một khu rừng có dạng hình vuông với chiều dài là 1km. Trong khu rừng có 4000 cây thông, cây to nhất có đường kính 0,5 m. Chứng minh rằng trong khu rừng đó có ít nhât 560 mảnh đất , diện tích mỗi mảnh 200m2 không có cây thông nào. Hướng dẫn giải +) Vì 1km = 1000m = 48.20 + 47.0,6 + 2 . 5,9 1000m = 95.10 + 94.0,52 + 2.0,56 +) Chia một cạnh hình vuông thành 48 đoạn, mỗi đoạn dài 20m , khoảng cách giữa các đoạn là 0,6m, ở hai đầu là hai đoạn mỗi đoạn dài 5,9m. Chia cạnh còn lại thành 95 đoạn, mỗi đoạn dài 10m, khoảng cách giữa các đoạn là 0,52m, ở hai đầu là hai đoạn mỗi đoạn dài 0,56m. Như vậy có tất cả 48.95 = 4560 mảnh có diện tích 200m2. Vì chỉ có 4000 cây và do đường kính của cây không quá 0,5m nên còn ít nhất 560 mảnh (mỗi mảnh có diện tích 200m2). Câu 26. Sắp xếp chín học sinh lớp 11 (hoặc giới Nam hoặc giới Nữ) đứng cách đều nhau trên một đường tròn. Chứng minh rằng tồn tại sáu học sinh cùng giới đứng tại sáu đỉnh của hai tam giác bằng nhau. Hướng dẫn giải Gọi 9 học sinh là H1, H2, H9 đứng tại chín đỉnh của đa giác đều chín cạnh. Vì có 9 học sinh đứng tại 9 đỉnh nên có ít nhất 5 đỉnh có học sinh cùng giới (hoặc là Nam hoặc là Nữ). Để cho tiện, ta giả sử 5 đỉnh này có 5 học sinh Nam đứng (tương tự nếu là 5 học sinh Nữ). Gọi một tam giác có 3 đỉnh mà 3 học sinh Nam đứng là tam giác Nam, như vậy có ít nhất 3 C5 10 tam giác Nam. Bây giờ ta sẽ chứng minh có hai tam giác Nam bằng nhau: Chín đỉnh của đa giác chia đường tròn ngoại tiếp nó thành 9 cung bằng nhau Hi Hi 1, i =1,8 và cung H9 H1; , ta gọi mỗi cung này là một “mảnh”. Không mất tính tổng quát, gọi Hi H j Hk là tam giác có Hi H j H j Hk Hk Hi . Hơn nữa số hij là số mảnh của cung Hij không chứa điểm Hk (i j k i ); tương tự ta định nghĩa như thế cho số hjk , hki . Tương ứng với mỗi tam giác Hi H j Hk với một bộ ba (hij; hjk ; hki ) . Ta nhận thấy rằng: 1 hij hjk hki 7 và hij + hjk + hki 9 . Chẳng hạn với tam giác với 3 đỉnh H1, H3 , H7 ta gọi là tam giác H3H1H7 tương ứng với một bộ ba (2;3;4) theo thứ tự đó. Như vậy, các tam giác bằng nhau ứng với cùng một bộ ba số như định nghĩa, trong khi các tam giác không bằng nhau ứng với các bộ ba khác nhau. Từ đó, ta xây dựng một song ánh giữa các lớp tam giác bằng nhau với tập hợp các bộ ba số nguyên dương có thứ tự (a, b, c) với a b c; a+b+c = 9 . Có tất thảy bẩy bộ ba số thỏa mãn là: (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4) và (3,3,3). Tức là có 7 lớp tam giác bằng nhau. Vì có ít nhất 10 tam giác Nam (Ba đỉnh tam giác là 3 học sinh Nam), nên có một lớp có ít nhất hai tam giác Nam; do đó có ít nhất sáu học sinh cùng giới, đứng tại sáu đỉnh của hai tam giác bằng nhau. Câu 27. Một cửa hàng có 4 loại kem: Kem sữa, kem xoài, kem dứa, kem sô cô la. Một nhóm có 9 người vào ăn kem và gọi 9 cốc kem. Hỏi có tất cả bao nhiêu sự lựa chọn ? Hướng dẫn giải Gọi số cốc kem Kem sữa, kem xoài, kem dứa, kem sô cola lần lượt là a, b, c, d ( a,b,c,d ¥ ), theo đầu bài ta có a + b + c + d = 9. Như vậy mỗi sự lựa chọn là một bộ (a;b;c;d) các số nguyên không âm sao cho a + b + c + d = 9; với mỗi bộ số này ta đặt tương ứng với một dãy nhị phân theo quy tắc sau: Viết từ trái sang
8. phải a chữ số 1 liên tiếp, 1 chữ số 0, b chữ số 1 liên tiếp, chữ số 0, c chữ số 1 liên tiếp, chữ số 0, rồi d chữ số 1 liên tiếp: 1 1 101 1 101 1 101 1 1 a chu so b chu so c chu so d chu so Như vậy mỗi bộ (a;b;c;d) được tương ứng với một dãy nhị phân có dộ dài 12 ký tự trong đó có 9 ký tự 1 và 3 ký tự 0. hiển nhiên tương ứng này là một song ánh vậy số cách chọn bằng số 3 cách chọn 3 vị trí trong 12 vị trí cho 3 chữ số 0.Thành thử có tất cả là C12 sự lựa chọn. Câu 28. Có bao nhiêu cách phân tích 69 thành tích của 3 số nguyên dương, biêt các cách phân tích mà các nhân tử chỉ khác nhau về thứ tự thì chỉ được tính 1 lần? Hướng dẫn giải ai , bi ∈ N 9 a b a b a b Xét phân tích 6 = (2 1.3 1)(2 2.3 2)(2 3.3 3) với a1 + a2 + a3 = 9 b1 + b2 + b3 = 9 Với mỗi a1 ∈ N, 0 ≤ a1 ≤ 9, có 10 ― a1 cách chọn số a2, để a1 + a2 ≤ 9 từ đó chọn a3 = 9 ― a1 ― a2. Vậy số cách chọn các bộ (a1, a2, a3) là 10+9+ +1 = 55 cách số cách chọn các bộ (a1, a2, a3) và (b1, b2, b3) là 55.55 cách. Bây giờ, ta sẽ tính số các cách phân tích bị trùng nhau. +) TH1: 3 thừa số bằng nhau: 69 = (23.33)(23.33)(23.33) +) TH2: 2 thừa số bằng nhau: 69 = (2a.3b)(2a.3b)(29―2a.39―2b) và (a ; b) # (3 ; 3). Khi đó a ∈ {0; 1; 2; 3; 4} ; b ∈ {0; 1; 2; 3; 4 } và (a ; b) # (3 ; 3) → số cặp (a; b) là 5.5 – 1 =24, và 24 cặp này cho ta 24 cách phân tích thỏa mãn yêu cầu. Tuy nhiên, mỗi cặp sẽ cho 3 lần đếm trong quá trình đếm mà ta vừa nêu ở trên. (1 điểm) +) TH3: nếu cả 3 thừa số khác nhau, thì mỗi phân tích bị đếm trùng 3!=6 lần. Vậy số cách phân tích là: 1 + 24 + (55 × 55 ― 24 × 3 ― 1):6 = 517 cách Câu 29. Trên tờ giấy có kẻ một lưới các ô vuông, người ta vẽ một đường gấp khúc khép kín với các đỉnh tại các mút của lưới và tất cả các đoạn của nó có độ dài bằng nhau. Chứng minh rằng, số các đoạn của đường gấp khúc khép kín như vậy là một số chẵn. Hướng dẫn giải Giả sử A1A2 An A1 là đường gấp khúc đã cho . Ta lấy hệ trục tọa độ vuông góc là các đường biên của lưới và chiều rộng của một ô làm đơn vị. Khi đó tọa độ xi , yi của đỉnh Ai là nguyên với i 1,2, ,n Đặt X i xi 1 xi ;Yi yi 1 yi ; X n x1 xn ;Yn y1 yn Ta có X1 X 2 X n 0 1 Y1 Y2 Yn 0 2 2 2 2 2 2 2 X1 Y1 X 2 Y2 X n Yn C 3 Để ý là X 2 Y 2 chia cho 4 dư 0 nếu X ,Y đều chẵn, dư 1 nếu có một số lẻ và dư 2 nếu hai số đều lẻ. Có thể giả thiết rằng trong X1, X 2 , , X n , Y1,Y2 , ,Yn có ít nhất một số lẻ, nói cách khác là ta chia tất cả các số này cho ước chung của chúng và xét bộ số nhận được.
9. Như vậy ta chỉ có hai trường hợp xảy ra: 1) C chia cho 4 dư 2, khi đó với mỗi i thì Xi và Yi đều lẻ nên từ điều kiện (1) suy ra n chẵn. 2) C chia 4 dư 1, khi đó với mỗi i thì hoặc Xi hoặc Yi là số lẻ, còn số kia chẵn. Từ (1) suy ra số cặp (Xi;Yi) mà Xi lẻ là một số chẵn. Từ (2) suy ra số các cặp (Xi;Yi) mà i lẻ là một số chẵn nên số cặp (Xi;Yi) là chẵn. Như vậy trong mọi trường hợp n đều chẵn. Câu 30. Cho S 1,2, ,2014, với mỗi tập tập con khác rỗng T  S , ta chọn một phần tử của nó làm phần tử đại diện. Tìm số cách ký hiệu phần tử đại diện cho mọi tập con khác rỗng của S thỏa mãn với mỗi tập khác rỗng T  S là hợp của các tập khác rỗng không giao nhau A,B,C  S , thì phần tử đại diện của D cũng là phần tử đại diện của một trong ba tập A, B, C. Hướng dẫn giải + Với mỗi tập X  S , ký hiệu r X là phần tử đại diện của X. Giả sử x1 r S . Trước hết ta chứng minh khẳng định sau: Nếu x1 X và X  S thì x1 r X . - Nếu X 2012, ta viết S thành hợp của ba tập không giao nhau gồm X và hai tập con khác nữa của S. Từ giải thiết suy ra x1 r X . - Nếu X 2013, xét phần tử y S, y x1 . Coi S là giao của ba tập không giao nhau gồm x1, y và hai tập khác nữa, áp dụng trường hợp X 2012, ta suy ra r x1, y x1 , nên y r X (vì theo giả thiết phần tử đại diện của một trong ba tập cũng là phần tử đại diện của X, mà r x1, y y và hai tập còn lại đều không chứa y). Do y lấy tùy ý nên r X y,y X , y x1 . Từ đó ta có r X x1 . - Chú ý rằng khẳng định trên vẫn còn đúng với mọi tập con của S có từ 5 phần tử trở lên. + Ta có 2014 cách chọn x1 r S , với mọi x1 X  S thì r X x1 . Xét S2 S \ x1. Tương tự ta có 2013 cách chọn x2 r S2 , với mọi x2 X  S2 thì r X x2 . Lặp lại tương tự quá trình này ta có 2014.2013 .5 cách chọn x1, x2 , , x2010 S với mỗi i 1,2, ,2010, r X xi , xi X  S \ x1, x2 , , xi 1 . Bây giờ còn lại 4 phần tử của S ký hiệu là Y y1, y2 , y3, y4. Ta có 4 cách chọn r Y , giả sử y1 r Y , chứng minh tương tự trên ta có r y1, y2 r y1, y3  r y1, y4  y1 Còn 7 tập chưa có phần tử đại diện là y1, y2 , y3, y1, y3, y4, y1, y2 , y4, y2 , y3, y4, 4 3 y2 , y3, y2 , y4, y3, y4 , phần tử đại diện của các tập này được chọn tùy ý nên có 3 .2 cách chọn. + Vậy tổng cộng có 2014.2013 .4.34.23 = 2014!.108 cách xếp phần tử đại diện cho các tập con. Câu 31. Trên một mặt phẳng có tất cả các điểm được tô bởi 3 màu đỏ, trắng, vàng. Chứng minh rằng tồn tại một tam giác cân có 3 đỉnh cùng màu. Hướng dẫn giải
10. Nhận xét: Trong một ngũ giác đều, tam giác có 3 đỉnh thuôc 6 điểm gồm 5 đỉnh của ngũ giác và tâm ngũ giác đều là tam giác cân. Trở lại bài toán: Xét ngũ giác đều ABCDE có tâm O khi đó : TH1: nếu tồn tại 3 trong 6 điểm A,B,C,D,E,O cùng màu ví dụ như A,B,C thì ta được tam giác A,B,C có 3 đỉnh cùng màu đpcm. TH2:không có 3 điểm trong 6 điểm A,B,C,D,E,O cùng màu. Khi đó một màu được tô cho 2 điểm. Giả sử A và O cùng màu khi đó xét đường tròn (O;OA) : + nếu tồn tại một điểm F thuộc (O) mà F cùng màu với O và A thì ta có tam giác AOF cân đpcm. +không tồn tại điểm nào trên (O) cùng màu với A và O, khi đó xét ngũ giác đều A’B’C’D’E’ (A A’,B’,C’,D’,E’) khi đó 5 đỉnh của ngũ giác trên chỉ được tô bởi 2 màu nên theo nguyên lí Đirich lê tồn tại 3 đỉnh cùng một màu, ví dụ A’,B’,C’ khi đó ta được tam giác cân có 3 đỉnh cùng màu đpcm. Vậy luôn tồn tại 1 tam giác cân trong mặt phẳng có 3 đỉnh cùng màu(đpcm). Câu 32. Cho bộ số 1;2;3 . 1) Chúng ta thực hiện phép biến đổi trên các bộ 3 số như sau: thay hai số trong chúng, ví dụ a và b, bởi a b và a b . Hỏi có thể nhận được bộ số sau: a1;b1;c1 thỏa mãn a1 b1 c1 10 sau khi thực hiện hữu hạn phép biến đổi từ bộ số ban đầu 1;2;3 ? 2) Nếu chúng ta thực hiện phép biến đổi trên các bộ 3 số như sau: thay hai số trong chúng, ví a b a b dụ a và b, bởi và . Hỏi có thể nhận được bộ số 28;4;2014 sau khi thực hiện 2 2 hữu hạn phép biến đổi từ bộ số ban đầu 1;2;3 Hướng dẫn giải Ta thực hiện theo cấu hình sau 1;2;3 3; 1;3 3;2; 4 3;2; 4 7;2; 1 a1;b1;c1 Dễ thấy: a1 b1 c1 10 . Câu 33. Tồn tại hay không một tập hợp gồm 2014 số nguyên dương với tính chất: loại bất cứ số nào ra khỏi tập hợp đó thì tập hợp 2013 số còn lại có thể chia thành hai tập con với tổng các số (thuộc mỗi tập con đó) là bằng nhau? Hướng dẫn giải Giả sử tồn tại một tập F với tính chất đã cho. a  Nếu mọi số a F đều chẵn, ta xét tập F’ = | a F  . 2  Hiển nhiên tập F’ cũng có tính chất nêu trong bài toán. Do đó ta có thể coi rằng tồn tại một tập F thoả mãn bài toán và F chứa ít nhất một số lẻ a. Gọi a1, a2, a2014 là các phần tử của tập F. Đặt S = a1 + a2 + + a2014 Theo giả thiết, i (1 i 2014) tập F\{ai} được chia thành hai tập con với tổng các số là bằng nhau nên tổng S – ai của tập F\{ai} là một số chẵn với i = 1, ,2014. 2014 Từ đó suy ra: là một số chẵn S là số chẵn.  S ai 2013S i 1 Khi đó S – a là một số lẻ mâu thuẫn với S – ai là một số chẵn với i = 1, ,2014.
11. Vậy không tồn tại tập hợp với tính chất đã nêu. Câu 34. Một lớp học có 17 học sinh nam và 20 học sinh nữ. Hỏi có tất cả bao nhiêu cách xếp 37 học sinh đó thành một hàng dọc sao cho xuất hiện đúng một cặp nam - nữ thỏa mãn nam đứng trước nữ? Hướng dẫn giải Xét dãy nhị phân sau: 1 10 0011 10 0 trong đó: có duy nhất một cặp (0;1), 17 chữ số 1 và x1 so1 x2 so0 x3 so1 x4 so0 20 chữ số 0.Số các dãy nhị phân thỏa mãn là số nghiệm nguyên của hệ phương trình: x1 x2 x3 x4 35 x1 x3 16 xi 0, i 1,2,3,4 1 1 Số nghiệm nguyên không âm của hệ phương trình là: C17 .C20 340 . Trở lại bài toán: Coi mỗi chữ số 0 là một học sinh nam, mỗi chữ số 1 là một học sinh nữ. Do vậy: số cách xếp 37 học sinh thành một hàng dọc sao cho xuất hiện đúng một cặp nam - nữ 1 1 thỏa mãn nam đứng trước nữ là C17 .C20.17!.20!. Câu 35. Lấy ngẫu nhiên 498 số nguyên dương không vượt quá 1000. Chứng minh rằng trong đó có 2 số có tổng chia hết cho 111. Hướng dẫn giải Xét tập S={1,2, ,1000} ta phân hoạch S như sau: A={1000}, B={111;222; ;999} Và chia tập T=S\(AUB) thành các tập con có 2 phần tử mà tổng bằng 999 như sau: T1={1;998}, T2={2;997}, T3={3;996}, , T495={499;500}. Như vậy S được chia thành 497 tập con, vậy 498 số được chọn ngẫu nhiên phải có 2 số rơi vào cùng một tập hợp. Hai số đó hoặc cùng chia hết cho 111 hoặc có tổng bằng 999 nên tổng của chúng chia hết cho 111 Câu 36. Cho tập hợp S = {1,2, ,2016}. a) Hỏi có bao nhiêu tập con 3 phần tử của S mà chúng là độ dài 3 cạnh của một tam giác có cạnh lớn nhất có độ dài bằng 1000? b) Chọn ngẫu nhiên 3 phần tử của S, tính xác suất để 3 số được chọn là độ dài 3 cạnh của một tam giác có cạnh lớn nhất có độ dài là một số chẵn. Hướng dẫn giải a) Đặt 1000 = 2k và gọi T là tập chứa các tập con thỏa mãn đề bài, theo BĐT tam giác và không mất tính tổng quát, ta có T = {{x,y,2k} ⊂ S| x 2k}. Rõ ràng T = {{x,y} ⊂ S| x 2k}. Từ điều kiện của x và y ta có x + y > 2k và x + y > 2x. Ta xét hai trường hợp, đó là trường hợp 2x < 2k và trường hợp 2x ≥ 2k. Trường hợp 1, 2x < 2k. Ta cũng có x ≥ 2 (do y ≤ 2k ― 1), suy ra x ∈ {2,3, ,k ― 1}. Lúc này, với mỗi giá trị của x, ta có thể chọn y tùy ý thuộc tập {2k ― x + 1,2k ― x + 2, ,2k ― 1} (tập này có x ― 1 phần tử). Dẫn đến số cách chọn các tập {x,y} thỏa mãn là k―1 k―2 (x ― 1) = x x=2 x=1
12. Trường hợp 2, 2x ≥ 2k. Hiển nhiên ta cũng phải có x ≤ 2k ― 2, suy ra k ≤ x ≤ 2k ― 2. Khi đó, với mỗi x thuộc tập {k,k + 1, ,2k ― 2}, ta có thể chọn y tùy ý thuộc tập {x + 1,x + 2, ,2k ― 1} (tập này có 2k ― 1 ― x phần tử). Do đó, số cách chọn các tập {x,y} thỏa mãn là 2k―2 k―1 (2k ― 1 ― x) = x x=k x=1 Vậy k―2 k―1 |T| = x + x = (k ― 1)2 = 4992 = 249001. x=1 x=1 b) Với mỗi số nguyên dương chẵn z = 2k, kí hiệu Tk = {{x,y,z} ⊂ S| x z}. Khi đó, số cách chọn 3 phần tử thỏa mãn yêu cầu đề bài là 1008 |T2k| . k=1 2 Theo câu a), ta có |T2k| = (k ― 1) . Suy ra 1008 1008 1007 1007 ⋅ 1008 ⋅ (2 ⋅ 1007 + 1) |T | = (k ― 1)2 = k2 = . 2k 6 k=1 z=1 k=0 3 Và do số cách chọn 3 phần tử bất kì thuộc S là C2016, suy ra xác suất cần tính là 1007 ⋅ 1008 ⋅ (2 ⋅ 1007 + 1) 1 3 = = 0,25. 6C2016 4 Câu 37. Cho 10 người ngồi thành một hàng ngang. Có bao nhiêu cách chia những người này thành 3 nhóm sao cho không có 2 người ngồi cạnh nhau thuộc cùng một nhóm. Hướng dẫn giải Đặt S n,k là số cách chia nhóm n người thành k nhóm mà trong mỗi nhóm không có 2 người liên tiếp. Sử dụng truy hồi ta được: S n,k S n 1,k 1 k 1 S n 1,k * . (Xét nhóm có n – 1 người trước đó, với S n 1,k và S n 1,k 1 tương ứng là số cách phân chia thành k và k – 1 nhóm thỏa mãn, ta thêm 1 người, sẽ được nhóm n người. Xét cách chia nhóm này thành k nhóm thỏa mãn. Người này có thể đứng 1 mình 1 nhóm, số cách là S n 1,k 1 Người này có thể thêm vào nhóm không có người thứ n – 1, có k – 1 nhóm như vậy, trong trường hợp này có k 1 S n 1,k cách) Áp dụng (*) với n 10,k 3 ,vào bài toán ta được: S 10,3 S 9,2 2S 9,3 1 2 S 8,2 2S 8,3 1 2 4 S 7,2 2S 7,3 =1 2 4 8S 7,3 1 2 4 8 16S 6,3 1 2 4 8 16 32S 5,3 1 2 4 8 16 32 64S 4,3 1 2 4 8 16 32 64 128S 3,3 1 2 4 8 16 32 64 128 28 1 (Chú ý rằng: S n,2 1 , do chỉ có 1 cách chia 2 nhóm xen kẽ nhau)
13. Câu 38. Cho m,n,k là các số nguyên dương thoả mãn m 1,1 k n k 1 m . Xét tập hợp S 1,2, ,n. Gọi X là tập hợp tất cả các tập con A của S thoả mãn đồng thời hai tính chất sau: A k ; ai a j m,ai ,a j A,i j;i, j 1,k . Hãy xác định số phần tử của tập hợp X . Hướng dẫn giải Giả sử A X , A a1,a2 , ,ak  với 1 a1 a2 ak n;ai a j m,1 j i k . Đặt b1 a1,b2 a2 m, ,bi ai i 1 m, ,bk ak k 1 m . Vì 1 a1 a2 ak n;ai a j m,1 j i k nên 1 b1 b2 bk n k 1 m Suy ra tập B b1,b2 , ,bk  là một tập con có k phần tử của tập 1,2, ,n k 1 m. Gọi Y là tập tất cả các tập con có k phần tử của tập hợp 1,2, ,n k 1 m. Khi đó ánh xạ f : X Y A B Khi đó f là một song ánh. Thật vậy ● f là đơn ánh: Vì với A1, A2 X , A1 A2 B1, B2 Y, B1 B2 f A1 f A2 ● f là toàn ánh: Giả sử B b1,b2 , ,bk  Y . Đặt A b1,b2 m, ,bk k 1 m a1,a2 , ,ak . Ta có ai 1 ai bi 1 im bi i 1 m m 1 nên A X và f A B . k Vì vậy ta có X Y Cn k 1 m . Câu 39. Cho tập hợp A 0, 1, 2, , 2006. Một tập con T của A được gọi là tập con “ ngoan ngoãn” nếu với bất kì x, y T (có thể x y ) thì x y T . Tìm tập con “ ngoan ngoãn” lớn nhất và khác A . Tìm tập con “ ngoan ngoãn” bé nhất rằng 2002 T và 2005 T .