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

1. Câu 1. Có 2012 con thỏ nhốt trong 1006 chuồng, mỗi chuồng có đúng hai con. Sau mỗi ngày người ta lại thay đổi vị trí của thỏ sao cho không có hai con thỏ nào đã nằm chung chuồng những ngày trước đó lại nằm chung chuồng thêm một lần nữa. Hỏi có tối đa bao nhiêu ngày làm được như vậy? Câu 2. Cho n điểm trong mặt phẳng, với n > 4, trong số đó không có ba điểm nào thẳng hàng. chứng (n 3)(n 4) minh rằng có ít nhất tứ gác lồi tạo thành có đỉnh nằm trong số n điểm đã cho. 2 n 1 2 n 20 Câu 3. Cho nhị thức (1 2x) , biết rằng C2n 1 C2n 1  C2n 1 2 1, (n nguyên dương). Tìm số hạng có hệ số lớn nhất trong nhị thức? Câu 4. Tìm hệ số của x 7 trong khai triển đa thức 2 3x 2n trong đó n là số nguyên dương thỏa mãn: 1 3 5 2n 1 k C2n 1 C2n 1 C2n 1 C2n 1 1024 ( Cn là số các tổ hợp chập k của n phần tử). Câu 5. Từ các số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên có 5 chữ số, trong đó chữ số 3 có mặt đúng 3 lần, các chữ số còn lại có mặt không quá một lần. Trong các số tự nhiên nói trên, chọn ngẫu nhiên một số, tìm xác suất để số được chọn chia hết cho 3. Câu 6. Trên bảng ô vuông 3x3, người ta đặt một số viên sỏi sao cho mỗi ô vuông có không quá một viên sỏi. Với mỗi cách đặt ta cho tương ứng với số điểm bằng tổng số : các hàng, các cột, các đường chéo chứa số lẻ các viên sỏi trên đó. Bảng không có sỏi ứng với 0 điểm. a) Tồn tại hay không cách đặt sỏi sao cho ô chính giữa bảng không có sỏi và số điểm tương ứng với cách đặt đó là 8. b) Chứng minh rằng số cách đặt sỏi với điểm số là một số chẵn bằng số cách đặt sỏi với điểm số là một số lẻ. Hướng dẫn giải a) Giả sử ô chính giữa không có sỏi và điểm số của cách đặt là 8. Như vậy 3 hàng, 3 cột và hai đường chéo đều có một số lẻ viên sỏi. Gọi a, b, c, d là số sỏi trong các ô như hình vẽ, a,b,c,d 0,1. Khi đó các ô đối xứng với a, b, c, d qua tâm sẽ có số sỏi tương ứng là a ',b',c ',d' sao cho a a ' b b' c c' d d' 1 a b c 0 d Từ đó a b c a ' b' c ' 3 suy ra một trong hai tổng a b c hoặc a ' b' c ' là một số chẵn. Khi đó dòng thứ nhất hoặc dòng thứ ba có tổng số sỏi là một số chẵn, mâu thuẫn với giả thiết ban đầu. Vậy không tồn tại cách đặt sỏi thỏa mãn điều kiện bài toán. b) Ta gọi hai cách đặt sỏi là liên hợp với nhau nếu ô trên cùng bên trái của chúng có số sỏi khác nhau và các ô còn lại tương ứng có số sỏi như nhau. a b c a’ b c f e d f 0 d g h i g h i ( B) (B’) Như vậy, các cách đặt sỏi chia thành từng cặp đôi một liên hợp với nhau.
2. Xét hai cách đặt liên hợp với nhau (B) và (B’). Tổng số sỏi ở dòng 1, cột 1 và 1 đường chéo cả hai bảng đôi một khác nhau về tính chẵn lẻ. Các dòng, cột và đường chéo còn lại của hai bảng có số sỏi như nhau. Do đó điểm số của ( B) và (B’) khác nhau 3 đơn vị, suy ra số điểm của ( B) và (B’) có tính chẵn lẻ khác nhau. Vậy hai cách đặt liên hợp với nhau, một cách xếp có điểm số chẵn, cách đặt còn lại có điểm số là một số lẻ suy ra điều phải chứng minh. Câu 7. Cho các chữ số 0, 1, 2, 3, 4, 5. Có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau từ các chữ số trên. Tính tổng các chữ số lập được. k k 2 k 1 Câu 8. Giải phương trình: C14 C14 2C14 . Câu 9. Cho tập hợp X có 2016 phần tử. Chọn ra 64 tập con X1 , X 2 ,., X 64 của tập X (mỗi tập con đều chứa nhiều hơn 1008 phần tử). Chứng minh tồn tại tập con A của X có số phần tử không vượt quá 6 mà A  X i  , với i 1,64 . Câu 10. Những ô của hình vuông kích thước 7 ´ 7 được tô bằng hai màu. Chứng minh rằng tồn tại ít nhất 21 hình chữ nhật với đỉnh cùng màu và các cạnh song song với các cạnh của hình vuông. Hướng dẫn giải Ta cho màu được tô là trắng và đen. Lấy một hàng bất kỳ, ta giả sử tồn tại k ô đen và 7 – k ô 2 2 2 trắng. Khi đó tồn tại Ck + C7- k = k - 7k + 21³ 9 Cặp ô cùng màu. Vậy tồn tại ít nhất 7.9 = 63 cặp ô cùng màu trên cùng hàng. 2 Tiếp theo tồn tại C7 = 21 cặp cột. Suy ra tồn tại 21.2 = 42 tổ hợp của màu và cặp cột. Với tổ hợp i = 1;24, giả sử tồn tại ji cặp trong cùng một tổ hợp, thì tồn tại ít nhất ji – 1 hình chữ nhật cho tổ hợp này. Vì tổng của ji ít nhất là 63 nên tồn tại ít nhất 42 å ( ji - 1) ³ 63- 42 = 21 i=1 Vậy tồn tại ít nhất 21 hình chữ nhật thỏa mãn yêu cầu của bài toán Câu 11. Cho tập hợp A 1;2; ;2013. Cần phải loại khỏi A ít nhất bao nhiêu phần tử để tập hợp còn lại có tính chất: Không phần tử nào bằng tích của hai phần tử khác. Hướng dẫn giải Loại khỏi A tập hợp {2;3; ;44}, tập này có 43 phần tử. Khi đó tập còn lại là {1;45;46; ;2012;2013}. Rõ ràng tập này thỏa mãn yêu cầu: Không có phần tử nào là tích của hai phần tử khác. Ta sẽ chứng minh mọi cách tách khỏi A một tập hợp có nhiều nhất 42 phần tử đều không thỏa mãn yêu cầu đề bài. 0.5 đ Thật vậy xét các bộ ba sau (43 bộ ba): 2, 87, 2.87 3, 86, 3.86
3. 4, 85, 4.85 44, 45, 44.45 Xét hàm số f (x) x(89 x) với 2 x 44 . Ta có f '(x) 89 2x 0,2 x 44 . Vậy f là hàm đồng biến khi 2 x 44 . Suy ra f (2) f (3) f (44) 2.87 3.86 44.45. Dễ thấy 2 3 44 45 46 87 2.87 3.86 44.45 . Vì 44.45 1980 2013 nên toàn bộ các phần tử của 43 bộ ba đều là khác nhau và đều nằm trong tập hợp A . Vì ta tách ra khỏi A tối đa 42 phần tử, nên phần còn lại của A (sau khi tách) phải có ít nhất một bộ ba nói trên. Vậy mọi cách tách như thế không thỏa mãn yêu cầu đầu bài. 2.0 đ Kết luận: Số phần tử ít nhất cần tách khỏi A là 43 phần tử. Câu 12. Cho 51 điểm bất kì phân biệt nằm trong hình vuông ABCD có cạnh bằng 5, trong đó không có không có 3 điểm nào thẳng hàng. Vẽ các đường tròn có bán kính bằng 2 và có tâm lần lượt là 51 điểm trên. Chứng minh rằng tồn tại 3 điểm trong số 51 điểm nói trên sao cho chúng đều thuộc phần giao của 3 hình tròn có tâm cũng chính là 3 điểm đó. Hướng dẫn giải * Chia hình vuông ABCD thành 25 hình vuông đơn vị ( có cạnh bằng 1) Theo nguyên lý Dirichlet, có ít nhất 1 hình vuông đơn vị chứa không ít hơn 3 điểm. * Mặt khác, khoảng cách giữa hai điểm bất kì trong một hình vuông đơn vị không vượt quá 2 * Gọi I1, I2, I3 là 3 điểm nằm trong hình vuông đợ vị nào đó. Vẽ 3 đường tròn có tâm lần lượt là I1, I2, I3 và có bán kính bằng 2 thì 3 điểm I1, I2, I3 đều thuộc giao của cả 3 hình tròn này ( Đpcm) Câu 13. Cho 2013 điểm trên đường thẳng, tô các điểm bằng một trong 3 màu màu xanh, đỏ, vàng (mỗi viên bi 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 2013 ). Ta sẽ tính Sn 1 theo Sn , xét hai bi cuối cùng của Sn có hai trường hợp xảy ra: +Nếu hai bi cuối cùng màu thế thì bi thứ n 1khác màu 2 bi cuối. +Nếu hai bi cuối khác màu thì bi thứ n 1tô bất kì. Từ đó sinh ra hai số đặc trưng M n là số cách tô n bi mà hai bi cuối cùng màu, Pn là số cách tô màu n bi mà hai bi cuối khác màu và cả hai cùng thỏa mãn 3 bi liên tiếp khác màu. Ta có: Sn 1 2M n 2Pn , Pn 1 2Sn ;M n 1 Pn .
4. Thế thì Sn 1 2Pn 1 6Sn 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,bthỏa mãn: a(3 13)4 b(3 13)4 49 24 13 23 b 3 2 13(3 13) Sau đó cho n 2013 ta được kết quả bài toán. Câu 14. Đối với mỗi giá trị của n ¥ , tìm số k lớn nhất thỏa mãn trong tập hợp gồm n phần tử có thể chọn ra k tập con khác nhau sao cho hai tập con bất kỳ đều có giao khác rỗng. Hướng dẫn giải Số tập con của X là 2n . Giả sử chọn được 2n 1 1 tập con của X có giao khác rỗng. Ta chia các tập con của X thành 2n 1 cặp được tạo bởi một tập con của X và phần bù của tập con đó trong X. Có 2n 1 cặp, chọn ra 2n 1 1tập từ 2n 1 cặp nên theo nguyên lý Dirichlet phải có ít nhất 2 tập thuộc cùng một cặp, và do đó giao của nó bằng rỗng. Điều này chứng tỏ không thể chọn được lớn hơn hoặc bằng 2n 1 1 tập sao cho giao của hai tập bất kỳ trong chúng khác rỗng. n 1 n n 1 n 1 Số tập con của X không chứa phần tử ai là 2 . Số tập con của X chứa ai là 2 2 2 . n 1 n 1 Do đó có 2 tập con của X có giao là phần tử ai nên số k lớn nhất cần tìm là 2 .