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

1. Câu 1. Cho tập hợp A gồm n phần tử (n≥4). Biết rằng số tập con gồm 4 phần tử của A bằng 20 lần số tập con gồm 2 phần tử của A. Tìm K ∈ {1;2; ;n} sao cho số tập con gồm K phần tử của A là lớn nhất? Hướng dẫn giải 4 Số tập con gồm 4 phần tử từ n phần tử của A : Cn tập. 2 Số tập con gồm 2 phần tử từ n phần tử của A :Cn tập. Theo đề bài, ta có: 4 2 Cn 20Cn n! n! 20 (n 4)!4! (n 2)!2!  (n 3)(n 2) 240 n 18(n)  n 13(l) Gọi K là số phần tử có số tập con lớn nhất trong A( 0 K 18, K ¢ ). Khi đó : K K 1 C18 C18 K K 1 C18 C18 18! 18! (18 K)!K ! (18 K 1)!(K 1)! 18! 18! (18 K)!K ! (18 K 1)!(K 1)! 1 1 (18 K) (K 1) 1 1 K 19 K 17 19 K 2 2 K 9 Câu 2. Cho k là số tự nhiên thỏa mãn Chứng minh rằng: Hướng dẫn giải Ta có : (1 x)5 (1 x)2011 (1 x)2016 5 0 1 2 2 3 3 4 4 5 5 Đặt M (1 x) C5 C5 x C5 x C5 x C5 x C5 x . 2011 0 1 2 2 k k 2011 2011 N (1 x) C2011 C2011x C2011x C2011x C2011 x . 2016 0 1 2 2 k k 2016 2011 P (1 x) C2016 C2016 x C2016 x C2016 x C2016 x . mà P=M.N nên phần tử thứ k trong P có dạng: k k 0 k k 1 k 1 k 1 5 5 k 5 k 5 C2016 x C5 C2011x C5 xC2011x C5 x C2011x 0 k k 1 k 1 k 5 k 5 k C5 C2011x C5C2011x C5 C2011x . Chọn x=1 ta có điều phải chứng minh.
2. Câu 3. Gọi A là tập hợp các số tự nhiên có chín chữ số đôi một khác nhau.Chọn ngẫu nhiên một số tự nhiên thuộc vào tập A. Tính xác suất để chọn được một số thuộc A và số đó chia hết cho 3. Hướng dẫn giải Gọi phần tử của A có dạng : a1a2a3a4a5a6a7a8a9. a1 0 nên có 9 cách chọn. 8 Chọn 8 chữ số còn lại và xếp vào vị trí từ a2 a9 : A9 cách chọn. 8 Vậy n(A)= 9A9 . Giả sử gọi B 0;1;2; ;9 có tổng 10 phần tử là 453 . Nên nếu muốn tạo thành một số có 9 chữ số vả chia hết cho 3, ta cần loại đi phần tử là bội của 3. Như vậy, ta sẽ có các tập : B \{0}, B \{3}, B \{6}, B \{9} TH1: Chọn tập B \{0} để tạo số : Ta còn 9 chữ số để xếp vào 9 vị trí a1 a9 :9! cách. TH2: Chọn 1 trong ba tập : B \{3}, B \{6}, B \{9}: 3 cách. a1 0 : có 8 cách ( vì đã loại đi phần tử là bội của 3). Còn 8 chữ số xếp vào 8 vị trí còn lại : 8! cách. Số cách chọn phần tử thuộc A và chia hết cho 3 là: 9! 3.8.8!. 9! 3.8.8! 11 Vậy xác suất cần tỉm là : 8 . 9A9 27 Câu 4. Gọi A là tập hợp các số tự nhiên có tám chữ số đôi một khác nhau. Chọn ngẫu nhiên một số tự nhiên thuộc vào tập A. Tính xác suất để chọn được một số thuộc A và số đó chia hết cho 9. Hướng dẫn giải Gọi phần tử của A có dạng : a1a2a3a4a5a6a7a8. a1 0 nên có 9 cách chọn. 7 Chọn 7 chữ số còn lại và xếp vào vị trí từ a2 a8 : A9 cách chọn. 7 Vậy n(A)= 9A9 . Giả sử gọi B 0;1;2; ;9 có tổng 10 phần tử là 459 . Nên nếu muốn tạo thành một số có 9 chữ số vả chia hết cho 3, ta cần loại đi 2 phần tử có tổng là bội của 9. Như vậy, ta sẽ có các tập : B \{0;9}, B \{1;8}, B \{2;7}, B \{3;6}, B \{4;5} TH1: Chọn tập B \{0;3} để tạo số : Ta còn 8 chữ số để xếp vào 8 vị trí a1 a8 :8! cách. TH2: Chọn 1 trong bốn tập : B \{1;8}, B \{2;7}, B \{3;6}, B \{4;5}: 4 cách. a1 0 : có 7 cách ( vì đã loại đi 2 phần tử có tổng là bội của 9). Còn 7 chữ số xếp vào 7 vị trí còn lại : 7! cách. Số cách chọn phần tử thuộc A và chia hết cho 3 là: 8! 4.7.7!. 8! 4.7.7! 1 Vậy xác suất cần tỉm là : 7 . 9A9 9 Câu 5. Người ta dùng 18 cuốn sách bao gồm 7 cuốn sách Toán, 6 cuốn sách Lý và 5 cuốn sách Hóa (các cuốn sách cùng loại thì giống nhau) để làm phần thưởng cho 9 học sinh
3. A,B,C,D,E,F,G,H,I, mỗi học sinh nhận được 2 cuốn sách khác thể loại (không tính thứ tự các cuốn sách). Tính xác suất để hai học sinh A và B nhận được phần thưởng giống nhau. Hướng dẫn giải Để một học sinh nhận được 2 quyển sách thể loại khác nhau, ta chia phần thưởng thảnh ba loại : ( Toán-Lý) ; ( Toán- Hóa) ; ( Lý- Hóa). Gọi x,y,z (x, y, z ¢ ) lần lượt là số học sinh nhận được bộ giải thưởng ( Toán-Lý) ; ( Toán- Hóa) ; ( Lý- Hóa). Khi đó, ta có hệ sau : x y 7 x 4 x z 6 y 3 y z 5 z 2 Số cách phát thưởng ngẫu nhiên cho 9 học sinh : 4 Chọn 4 bạn bất kì trong 9 bạn để nhận bộ ( Toán-Lý) : C9 cách. 3 Chọn 3 bạn bất kì trong 5 bạn còn lại để nhận bộ (Toán-Hóa) : C5 cách. 2 bạn còn lại chỉ có 1 cách phát thưởng là bộ ( Lý-Hóa). 4 3 Vậy n() C9 .C5 . Gọi S là biến cố “ hai học sinh A và B có phần thưởng giống nhau” TH1 : A và B cùng nhận bộ ( Toán-Lý) Vì A và B đã nhận quà nên bộ ( Toán-Lý) còn lại 2 phần. Ta chọn 2 bạn trong 7 bạn để nhận : 2 C7 cách. 3 Chọn 3 bạn trong 5 bạn còn lại để nhận bộ ( Toán-Hóa) : C5 cách. 2 bạn còn lại chỉ có 1 cách phát thưởng là bộ ( Lý-Hóa). 2 3 Vậy có C7 .C5 cách để A và B củng nhận bộ ( Toán-Lý). TH2: A và B cùng nhận bộ ( Toán-Hóa) 1 4 Lập luận tượng tự, ta được : C7 .C6 cách. 4 TH3 : A và B cùng nhận bộ ( Lý-Hóa) có C7 cách. 2 3 1 4 4 Vậy có C7 .C5 + C7 .C6 + C7 2 3 1 4 4 C7 C5 C7C6 C7 5 P(S) 4 3 . C9 C5 18 Câu 6. Cho tập hợp A={1,2,3,4,.,20}. Tính xác suất để ba số được chọn không có 2 số tự nhiên liên tiếp. Hướng dẫn giải 3 Số cách chọn ba số đôi một khác nhau từ A : n() C20. TH1 : Ta chọn số có 3 chữ số tự nhiên liên tiếp : Chọn phần tử bất kì trong A \{19;20} : 18 cách chọn. Với mỗi phần tử được chọn, ta lấy hai phần tử liền kề bên phải : 1 cách chọn. Vậy có 18 cách chọn 3 phần tử liên tiếp nhau. TH2 : Chọn ba số có đúng hai chữ số liên tiếp : Chọn 1 trong hai phần tử {1;19}: 2 cách. Với mỗi cách chọn phần tử trên, ta có 1 cách chọn phần tử liền sau đó. Chọn phần tử thứ ba không liên tiếp với 2 phần tử đã chọn : 17 cách ( vì phải bỏ đi phần tử liển sau phần tử thứ 2 ). Chọn 1 phần tử trong tập {2;3;4;.;18} : 17 cách. Với mỗi cách chọn trên, ta có 1 cách chọn phần tử thứ hai liền sau nó.
4. Để chọn phần tử thứ 3 không liên tiếp, ta cần bỏ đi phần tử liền trước phần tử 1 và liền sau phần tử 2 : 16 cách. Vậy có 17.2+17.6 cách chọn 3 phần tử có đúng hai chữ số liên tiếp. 3 C20 18 17.2 17.16 68 P 3 C20 95 Câu 7. Có 1650 học sinh được sắp xếp thành 22 hàng và 75 cột. Biết rằng với hai cột bất kì, số cặp học sinh cùng hàng và cùng giới tính không vượt quá 11. Chứng minh rằng số học sinh nam không vượt quá 920 người Hướng dẫn giải Gọi ai là số học sinh nam hàng thứ i. Vì có 75 cột nên số học sinh nữ của hàng thứ i là 75 ai . Số cặp học sinh cùng hàng và củng giới tính : Chọn 2 nam trong số nam cùng hàng : C2 cách. ai Chọn 2 nữ trong số nữ cùng hàng : C2 cách. 75 ai 2 Chọn 2 bạn học sinh bất kì của một hàng : C75 . Theo đề bài, ta có : 22 C 2 C 2 11C 2  ai 75 ai 75 i 1 22 2  ai 75ai 30525 i 1 22 2  2ai 75 1650 i 1 Theo Cauchy-Swatch : 22 2 22 2 (2ai 75) 22(2ai 75) 36300 i 1 i 1 22 191 1650  ai 921 i 1 2 Câu 8. Trong một giải cờ vua gồm nam và nữ vận động viên. Mỗi vận động viên phải chơi hai ván với mỗi động viên còn lại. Cho biết có 2 vận động viên nữ và cho biết số ván các vận động viên chơi với nhau hơn số ván họ chơi với hai vận động viên nữ là 66. Hỏi có bao nhiêu vận động viên tham gia giải và số ván tất cả các vận động viên đã chơi? Hướng dẫn giải Gọi n là số vận động viên nam tham gia ( n 2,n ¢ ). 2 Chọn 2 trong số n VĐV nam để đấu 2 ván với nhau : 2Cn cách. Số ván VĐV nam đấu với VĐV nữ là : 4n. Theo đề bài, ta có : 2 2Cn 4n 66 2n! 4n 66 (n 2)!2! (n 1)n 4n 66 n 11(n) n 6(l) Vậy số VĐV tham gia giải là : 11+2=13 người. 2 Số ván các vận động viên chơi với nhau là : 2C11 4.11 2 156 ván.
5. Câu 9. Cho tập hợp A có 20 phần tử. Hỏi có bao nhiêu tập hợp con của A mà số phần tử là số chẵn ? Hướng dẫn giải Gọi S là số tập hợp có số phần tử là số chẵn. 2 4 6 20 S=C20 C20 C20 C20 Ta xét : 20 0 1 2 2 3 3 20 (1 x) C20 C20 x C20 x C20 x C20 . 20 0 1 2 2 3 3 20 (1 x) C20 C20 x C20 x C20 x C20 . Chọn x=1, ta được : 20 0 1 2 3 20 2 C20 C20 C20 C20 C20 . 0 1 2 3 20 0 C20 C20 C20 C20 C20 . 20 2 4 20 2 2 2C20 2C20 2C20 . 19 2 4 20 2 1 C20 C20 C20 Câu 10. Cho n điểm P1, P2 , P3 , , Pn (n 4) cùng nằm trên một đường tròn. Tìm số cách tô màu n điểm trên bằng 5 màu sao cho 2 điểm kề nhau tô bởi 2 màu khác nhau. Hướng dẫn giải Gọi an là số cách tô màu n điểm thỏa mãn. Giả sử có một vòng tròn n+1 điểm được tô màu theo yêu cầu. TH1 : Điểm 1 và điểm n khác màu nhau. ➢ Bỏ đi điểm n+1, ta có an cách. Ngược lại, nếu thêm điểm n+1, ta có 3 lựa chọn màu cho nó. Vậy có 3.an cách tô màu vòng tròn n+1 điểm theo TH1. TH2: điểm 1 và điểm n cùng màu : Bỏ đi điểm n+1 và hợp nhất hai điểm 1 và n : an 1 cách. Ngược lại, nếu có vòng tròn n-1 điểm đã được tô màu. Ta tách điểm 1 ra làm hai, và thêm điểm n+1 vào. Khi đó nó có 4 lựa chọn màu, vì vậy : 4an 1 cách. Từ hai TH nêu trên, ta có : an 1 3an 4an 1 ( với a5 5!). Câu 11. Một bảng ô vuông kích thước 3x3 được gọi là bảng “ 2015- hoàn thiện” nếu tất cả các ô của nó được điền bởi các số nguyên không âm ( không nhất thiết phân biệt ) sao cho tổng các số trên mỗi hàng và mỗi cột đều bằng 2015. Hỏi có tất cả bao nhiêu bảng “ 2015- hoàn thiện” sao cho số nhỏ nhất trong các số ở các ô trên đường chéo chính nằm ở vị trí tâm của bảng ? ( Đường chéo chính của bảng vuông là đường nối ô vuông ở góc trên cùng bên trái với ô vuông ở góc dưới cùng bên phải. ) Hướng dẫn giải Gọi số học sinh ban đầu là 2n và Un là số cách chọn ra một số bạn xếp thành 2 hàng ngang thỏa mãn yêu cầu bài tóan Ta bỏ đi một bạn học sinh ở đầu của một hàng, còn 2n-1 người. Gọi Vn là số cách chọn ra một số bạn từ 2n-1 người đó thỏa mãn yêu cầu bài tóan Xét số cách chọn từ 2n người 1 3 n 2 4 n TH1: Bạn ở vị trí 1 được chọn.Khi đó bạn ở vị trí 2,3 không được chọn Vậy có Vn -1+ 1 cách chọn ( Thêm 1 cách không chọn ai cả từ 2n-1 bạn)
6. TH2: Bạn ở vị trí 2 được chọn. Tương tự có Vn -1+ 1 cách chọn TH3:Cả 2 bạn ở vị trí 1 và 2 không được chọn. Khi đó có Un-1 cách Vậy ta có Un= Un-1+2 Vn -1+ 2 (1) Xét số cách chọn từ 2n-1 bạn 1 2 n × n TH1: Bạn ở vị trí 1 được chọn.khi đó bạn ở vị trí 2 không được chọn. Vậy có Vn-1 +1 cách TH2: Bạn ở vị trí 1 không được chọn. Có Un-1 cách Vậy ta có Vn = Vn-1 +1 + Un-1 (2) Từ (1) và (2) ta tìm được Un+1 = 2 Un+Un-1+2 Với n=50 ta có số cách chọn thỏa mãn yêu cầu bài toán là Câu 12. Cho tập X= {1,2,3,.2015}, xét tất cả các tập con của X, mỗi tập hợp có 3 phần tử. Trong mỗi tập hợp con ta chọn số bé nhất. Tính trung bình cộng của các số được chọn. Hướng dẫn giải • Xét X= {1,2,3.n} và các tập con gồm r phần tử của X Các tập hợp con của X có phần tử được chọn là 1,2.n– r + 1.Cách cấu tạo các tập hợp như sau: Lấy A X {1}, A có r – 1 phần tử ( vì đã bỏ đi 1 ), thì {1} A là tập hợp có r phần tử trong đó r 1 số 1 là phần tử bé nhất. Vậy có: Cn 1 tập con có phần tử có phần tử nhỏ nhất là 1. Tương tự ta có: r 1 + Cn 2 tập con có r phần tử có phần tử bé nhất là 2. . r 1 + Cn (n r 1) tập con có r phần tử có phần tử bé nhất là n – r + 1. Trung bình cộng các số được chọn : 1 P 1Cr 1 2Cr 1 (n r 1)Cr 1 . r n 1 n 2 n (n r 1) Cn Ta chứng minh: 1 n 1 1Cr 1 2Cr 1 (n r 1)Cr 1 . r n 1 n 2 n (n r 1) Cn r 1 n 1 1Cr 1 2Cr 1 (n r 1)Cr 1 C r C r 1 . n 1 n 2 n (n r 1) r 1 n n 1 r r r 1 mà Cn 1 Cn Cn ta được: r r r r r r r r r r r r 1 1 Cn Cn 1 2 Cn 1 Cn 2 (n r) Cr 1 Cr Cn Cn 1 Cn 2 Cr 1 Cr Cn 1 2015 1 2016 Vậy trung bình cộng của các số được chọn là : . 3 1 4 Câu 13. Có bao nhiêu số tự nhiên 7 chữ số khác nhau tửng đôi một, trong đó chữ số 2 đứng liền giữa hai số 1 và 3 ? Hướng dẫn giải Gọi số cần tìm có dạng : a1a2a3a4a5a6a7 . 4 Vì số cần tìm có 3 số {1;2;3} nên ta chỉ cần chọn 4 số nữa để điền vào vị trí: C7 cách.
7. Hoán đổi vị trí 4 số được chọn cùng với cụm { 1;2;3} : 5! cách. Hoán đổi vị trí số 3 và 1 trong cụm {1;2;3} : 2! cách. Trong các số tạo thành có TH số 0 đứng đầu : a1 0 có 1 cách. 3 Chọn 3 số nữa để điền vào vị trí : C6 cách. Hoán đổi vị trí của cụm{1;2;3} và 3 số vừa chọn : 4! cách. Hoán đổi vị trí của số 1 và số 3 trong cụm {1;2;3}: 2! cách. 4 3 Vậy số các chữ số thỏa mãn yêu cầu bài toán là : 2!5!C7 2!4!C6 =7440 số.