Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Tổ hợp - Phần 3

Nội dung text: Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Tổ hợp - Phần 3

1. 2k Câu 1. Với mỗi số tự nhiên k 0, số 2 5 luơn được viết dưới dạng ak bk 5 với ak ,bk là các số nguyên dương. a) Tìm hệ thức xác định dãy ak , bk . b) Chứng minh: 20bkbk 1 16 là số chính phương. 2 c) Chứng minh: ak 2 1 chia hết cho 5. Hướng dẫn giải 2 k 1 2k 2 2k 2 5 2 5 2 5 2 5 9 4 5 9ak 20bk 4ak 9bk 5 ak 1 bk 1 5 ak 1 9ak 20bk Suy ra bk 1 4ak 9bk ak 2 9ak 1 20bk 1 9ak 1 20 4ak 9bk 9ak 1 20.4ak 20.9bk 9ak 1 20.4ak 9 ak 1 9ak 18ak 1 ak a1 9,a2 161 Vậy dãy ak được xác định: ak 2 18ak 1 ak ,k ¥ * b1 4,b2 72 Tương tự ta được dãy bk : bk 2 18bk 1 bk ,k ¥ * 2 2 2 2 b) bk 1 bk 2bk bk 1 18bk 1 bk bk bk bk 1 18bk bk 1 bk bk 1bk 1 2 ... b2 b3b1 16 2 2 2 2 Mặt khác: 16 bk 1 bkbk 2 bk 1 bk bk 18bk 1 bk 1 bk 18bkbk 1 2 2 2 Suy ra 20bk 1bk 16 bk 1 bk 2bk 1bk bk 1 bk Do các số hạng của dãy bk là số nguyên nên 20bkbk 1 16 là số chính phương. c) ak 2 18ak 1 ak ak 2 9ak 1 9ak 1 ak 2 2 2 2 Suy ra ak 2 9ak 1 9ak 1 ak hay ak 2 18ak 2ak 1 ak 18ak 1ak 1
2. Thay k = 1, 2, 3, ta được: 2 2 a3 18a3a2 a1 18a2a1 2 2 a4 18a4a3 a2 18a3a2 ... 2 2 ak 1 18ak 1ak ak 1 18ak ak 1 2 2 ak 2 18ak 2ak 1 ak 18ak 1ak Cộng vế theo vế, ta cĩ: 2 2 2 2 ak 2 ak 1 18ak 2ak 1 a1 18a1a2 a2 80 2 9a a Khi đĩ: a2 1 k 2 k 1 k 2 80 2 2 Do ak ¢ nên 9ak 2 ak 1 chia hết cho 80 4 .5 nên 9ak 2 ak 1 chia hết cho 20 20m 2 Từ đĩ, ta được: 9a a 20m,m ¢ hay a2 1 5m2 k 2 k 1 k 2 80 2 Vậy ak 2 1 chia hết cho 5. Câu 2. 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 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 . +) Trước hết ta tính n(A). Với số tự nhiên cĩ tám chữ số đơi một khác nhau thì chữ số đầu tiên 7 7 cĩ 9 cách chọn và cĩ A9 cho 7 vị trí cịn lại. Vậy n A 9A9 . +) Giả sử B 0;1;2;...;9 ta thấy tổng các phần tử của B bằng 459 nên số cĩ chín chữ số đơi một khác nhau và chia hết cho 9 sẽ được tạo thành từ 8 chữ số đơi một khác nhau của các tập B \ 0; 9;B \ 1; 8;B \ 2; 7;B \ 3; 6;B \ 4; 5 8 7 Nên số các số loại này là A8 4.7.A7 . 8 7 A8 4.7.A7 1 Vậy xác suất cần tìm là 7 . 9.A9 9 2
3. Câu 3. a) Gọi M là tập tất cả các số tự nhiên cĩ sáu chữ số đơi một khác nhau và cĩ dạng a1a2a3a4a5a6. Chọn ngẫu nhiên một số từ tập M. Tính xác suất để số được chọn là một số chẵn, đồng thời thỏa mãn a1 a2 a3 a4 a5 a6 . n C1 2C 2 3C3 1 nC n Tính tổng: S n n n ... n . 2.3 3.4 4.5 n 1 n 2 Hướng dẫn giải Gọi M là tập tất cả các số tự nhiên cĩ sáu chữ số đơi 5 Ta cĩ: n M 9.A9 (số cĩ sáu chữ số đơi một khác nhau thì a1 cĩ chín cách chọn, a2a3a4a5a6 5 là chỉnh hợp chập 5 của 9 phần tử nên cĩ A9 ). +) Gọi A là biến cố “chọn ra được một số tự nhiên chẵn từ tập M đồng thời thỏa mãn a1 a2 a3 a4 a5 a6 ”. 5 TH1: a6 0 thì a1a2a3a4a5 cĩ C9 cách chọn. 5 TH2: a6 2 thì a1a2a3a4a5 cĩ C7 cách chọn. 5 TH3: a6 4 thì a1a2a3a4a5 cĩ C5 cách chọn. 5 5 5 n A C9 C7 C5 148 n A 148 37 Do đĩ P A 5 . n  9.A9 34020 n C1 2C 2 3C3 1 nC n Tính tổng: S n n n ... n . 2.3 3.4 4.5 n 1 n 2 Ta cĩ: C k n! 1 n 1 ! C k 1 n . n 1 (3) k 1 k! k 1 n k ! n 1 k 1 ! n 1 k 1 ! n 1 1 k kC k 1 k kC k 2 Áp dụng 2 lần cơng thức (3) ta được: n n 2 k 1 k 2 n 1 n 2 Cho k chạy từ 1 đến n rồi cộng vế các đẳng thức trên ta cĩ 3 4 5 n n 2 n 1 n 2 S Cn 2 2Cn 2 3Cn 2 ... 1 nCn 2 3
4. 2 3 3 4 4 5 n n 1 Cn 1 Cn 1 2 Cn 1 Cn 1 3 Cn 1 Cn 1 ... 1 nCn 1 2 3 4 n n 1 Cn 1 Cn 1 Cn 1 ... 1 Cn 1 C 0 C1 C 0 C1 C 2 C3 C 4 C5 ... 1 n 1 C n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 1 n 1 1 1 n 1 n n Vậy S n 1 n 2 Câu 4. Trong 1 cái hộp cĩ 3 bi đỏ, 4 bi vàng, 5 bi xanh cùng chất, cùng kích thước.Một người lấy ngẫu nhiên cùng lúc 4 viên bi. Tính xác suất để số bi đỏ mà người đĩ lấy được khơng lớn hơn 2. Hướng dẫn giải Lấy ngẫu nhiên, cùng lúc 4 viên bi trong hộp cĩ 3 bi đỏ, 4 bi vàng và 5 bi xanh nên cĩ số phần 4 tử của khơng gian mẫu là: n() C12 . Gọi A: “Biến cố trong 4 bi lẫy ngẫu nhiên cĩ 3 bi màu đỏ”. 3 1 n(A) C3 .C9 3 1 C3 .C9 1 Xác suất của biến cố A là: P(A) 4 C12 55 1 54 Vậy xác suất để số bi đỏ mà người đĩ lấy được khơng lớn hơn 2 là 1 P(A) 1 55 55 Câu 5. Cho tập S gồm tất cả các số nguyên trên trong đoạn [1;2014]. Gọi T là tập hợp gồm tất cả các tập con khơng rỗng của S. Với mỗi tập hợp X T , ký hiệu m(X ) là trung bình cộng của tất m(X) cả các số thuộc X . Đặt m  (ở đây tổng được lấy theo tất cả các tập hợp X T ). |T | Hãy tính giá trị của m. Hướng dẫn giải Cho tập S gồm tất cả các số nguyên trên trong đoạn [1;2014]. Gọi T là tập hợp gồm tất cả các tập con khơng rỗng của S. Với mỗi tập hợp X T , ký hiệu m(X ) là trung bình cộng của tất m(X) cả các số thuộc X . Đặt m  (ở đây tổng được lấy theo tất cả các tập hợp X T ). |T | Hãy tính giá trị của m. 4
5. Với mỗi x [1,2, ..., 2014], đặt mk m(X) ở đây tổng được lấy theo tất cả các tập hợp X T mà | X | k . k 1 Xét số a bất kỳ thuộc S, suy ra a cĩ mặt trong C2013 tập X T mà | X | k . k 1 k 1 Suy ra kmk (1 2 ... 2014)C2013 1007.2015.C2013 2014 2014 k 1 2014 2014 C2013 2015 k 2015 k Do đĩ m(X) mk 1007.2015 C2014 C2014 k 1 k 1 k 2 k 1 2 k 1 2015 (22014 1) 2 2015 Mà |T | (22015 1) m 2 Cách 2. Xây dựng song ánh từ T vào T như sau X T f (X ) {2015- x / x X} m(X ) m( f (X )) 2015 Suy ra 2m(X) m(X) m(f(X)) | T|.2015 m(X) 2015 Suy ra m  | T| 2 Câu 6.Ở các vị trí khác nhau của một đường đua ơ tơ vịng trịn cùng một thời gian cĩ 25 ơ tơ xuất phát theo cùng một hướng. Theo thể lệ cuộc đua, các ơ tơ cĩ thể vượt lẫn nhau, nhưng cấm khơng được vượt đồng thời hai xe một lúc. Các ơ tơ đến đích là các điểm mà chúng xuất phát ban đầu cùng một lúc. Chứng minh rằng trong suốt cuộc đua cĩ một số chẵn lần vượt nhau của các ơ tơ. Hướng dẫn giải Ở Ta sơn 1 trong 25 ơ tơ thành màu vàng, cịn các oto khác đánh số từ 1 đến 24 theo thứ tự mà chúng ở thời điểm ban đầu sau ơ tơ màu vàng ( theo chiều chuyển động của các ơ tơ). Ở tâm của đường đua ta đặt một bảng để ghi số thứ tự của các ơ tơ sắp xếp sau ơ tơ vàng sau mỗi lần các ơ tơ vượt nhau, tức là ta được một hốn vị của {1,2, ,24}. Trường hợp 1: Mỗi lần 2 ơ tơ trong các ơ tơ từ 1 đến 24 vượt nhau thì trên bảng 2 số liền nhau đổi chỗ cho cĩ nhau. Trường hợp 2: 5
6. Nếu trước khi cĩ lần vượt của một ơ tơ nào với ơ tơ vàng, các trên bảng lập thành một hốn số vị a1, a2, ,a24 thì sau lần vượt đĩ sẽ cĩ hốn vị a2,a3, ,a24,a1. Từ hốn vị trên cĩ thể chuyển xuống hốn vị dưới bằng 23 phép chuyển vị, tức là phép đổi chỗ 2 số liền nhau. Trường hợp 3: Nếu ơ tơ vàng vượt một ơ tơ nào đĩ thì từ hốn vị a 1,a2, ,a24 ta cĩ hốn vị a24,a1,a2, a23. Lần di chuyển này cũng cĩ thể thay bằng 23 phép chuyển vị như trường hợp 2. Như vậy mỗi lần các ơ tơ vượt nhau đều dẫn đến việc thực hiện một số lẻ lần phép chuyển vị. Ta sẽ chứng minh nếu số lần vượt nhau là số lẻ thì khi về đích các ơ tơ khơng được sắp xếp như cũ. Thật vậy gs a1,a2 ,a24 là một cách sắp xếp tùy ý của các số1,2, 24. Ta sẽ nĩi rằng các số ai,aj lập thành một nghịch thế nếu i aj. Khi đổi vị trí 2 số đứng liền nhau, tức là thực hiện một phép chuyển vị thì sẽ tăng hay giảm số nghịch thế đi 1. Do đĩ nếu các oto vượt nhau một số lẻ lần thì từ cách sắp xếp thứ tự của các oto ban đầu, đến cuối cùng ta đã thực hiện một số lẻ các phép chuyển vị, tức là số nghich thế của lần sắp xếp cuối cùng là số lẻ, nghĩa là các ơ tơ khơng thể sắp xếp như cũ. Mâu thuẫn. Vậy các ơ tơ vượt nhau một số chẵn lần. Câu 7. 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. Hướng dẫn giải Gọi fn là số tập con tốt của 1,2,3,...,n. Ta lập hệ thức truy hồi của fn . + Nếu tập con tốt của 1,2,3,...,n khơng lấy n thì fn fn 1 . + Nếu tập con tốt của 1,2,3,...,n lấy n thì fn fn 2 . Vậy ta cĩ fn fn 1 fn 2 . 6
7. Hơn nữa f1 2, f2 3 1 5 Phương trình đặc trưng x2 x 1 0 x 2 n n 1 5 1 5 Suy ra fn A B 2 2 1 5 1 5 2 2 5 1 A B 2 2 2 A 5 5 Thay 2 giá trị đầu ta được 2 2 1 5 1 5 A B 3 2 B 2 2 5 5 Suy ra n n n 1 n 1 2 2 5 1 1 5 2 1 5 2 5 1 1 5 1 1 5 fn 5 5 2 5 5 2 5 2 5 2 Câu 8. Với mỗi hốn vị p a1,a2 ,...,a9 của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số cĩ 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p cĩ hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nĩ và n là số các hốn vị p thỏa mãn s p m. Tính m n . Hướng dẫn giải Với mỗi hốn vị p a ,a ,...,a của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số 1 2 9 cĩ 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p cĩ hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nĩ và n là số các hốn vị p thỏa mãn s p m. Tính m n . Với mỗi hốn vị p a ,a ,...,a của các chữ số 1, 2, , 9, kí hiệu s p là tổng của ba số 1 2 9 cĩ 3 chữ số a1a2a3 , a4a5a6 , a7a8a9 . Trong các s p cĩ hàng đơn vị bằng 0, gọi m là giá trị nhỏ nhất của nĩ và n là số các hốn vị p thỏa mãn s p m. Tính m n . Để s p đạt giá trị nhỏ nhất thì 3 chữ số hàng trăm là 1, 2, 3, s p cĩ chữ số tận cùng bằng 0 các chữ số hàng đơn vị cĩ tổng là bội của 10. Và từ các chữ số 4, 5, 6, 7, 8, 9 khơng cĩ ba thì số nào cĩ tổng bằng 10 và vì 7 8 9 24 30 nên 3 chữ số hàng đơn vị phải cĩ tổng bằng 20, 7
8. ta thấy 5 6 9 4 7 9 5 7 8 20 , cĩ ba bộ số cĩ thể xếp vào 3 chữ số ở hàng đơn vị, tương ứng các chữ số cịn lại sẽ là hàng chục. Do đĩ giá trị nhỏ nhất của s p là m 1 2 3 100 19 10 20 810 Như vậy cĩ 3 trường hợp, trong mỗi trường hợp cĩ 6 cách chọn 3 chữ số hàng trăm, 6 cách chọn 3 chữ số hàng chục và 6 cách chọn 3 chữ số hàng đơn vị. Vậy số các hốn vị p thỏa mãn yêu cầu bài tốn là n 3 6 6 6 648. Vậy m n 162 . Câu 9. 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 ( Khơng cĩ giải) Câu 10. Một số điện thoại di động là một dãy số gồm 10 chữ số được chọn từ 0,1,2,3,4,5,6,7,8,9, nhưng chữ số đầu tiên phải là 0. Mr. Fat cĩ số điện thoại 0912364587 là một dãy số gồm 10 chữ số cĩ tính chất 9 chữ số sau (khơng kể chữ số 0 đầu tiên) là phân biệt, khác 0; đồng thời các chữ số từ 1 đến 5 xuất hiện trong dãy từ trái qua phải theo đúng thứ tự tự nhiên của chúng, cịn các chữ số từ 1 đến 6 thì khơng. Mrs. Fat cũng muốn chọn được một số điện thoại cĩ cùng tính chất như vậy. Hỏi bà ta cĩ bao nhiêu cách chọn (sự lựa chọn)? Hướng dẫn giải ( Khơng cĩ giải) Câu 11. 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 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 . +) Trước hết ta tính n(A). Với số tự nhiên cĩ tám chữ số đơi một khác nhau thì chữ số đầu tiên 7 7 cĩ 9 cách chọn và cĩ A9 cho 7 vị trí cịn lại. Vậy n A 9A9 +) Giả sử B 0;1;2;...;9 ta thấy tổng các phần tử của B bằng 459 nên số cĩ chín chữ số đơi một khác nhau và chia hết cho 9 sẽ được tạo thành từ 8 chữ số đơi một khác nhau của tập các 8 7 B \ 0; 9;B \ 1; 8;B \ 2; 7;B \ 3; 6;B \ 4; 5 nên số các số loại này là A8 4.7.A7 . 8
9. 8 7 A8 4.7.A7 1 Vậy xác suất cần tìm là 7 . 9.A9 9 Câu 12. Cĩ 푛 học sinh (푛 ≥ 2) đứng thành hàng dọc, cứ mỗi lần thầy giáo thổi cịi thì cĩ đúng 2 học sinh đổi chỗ cho nhau. Hỏi sau 2015 lần thầy giáo thổi cịi, ta cĩ thể thấy tất cả các học sinh đều đứng trở lại đúng vị trí ban đầu của mình hay khơng ? Hướng dẫn giải Đánh số từ 1 đến n cho các bạn học sinh trong hàng dọc lúc đầu. Ký hiệu 푃푛 là tập các hốn vị của {1,2, ,푛}. Gọi = ( (1), (2), , (푛)) là một hốn vị của {1,2, ,푛}. Cặp ( (푖), (푗)) của gọi là 1 nghịch thế của nếu 푖 (푗). Xét ánh xạ 푖: 푃푛→푃푛 mà 푖( ) thu được từ bằng cách đổi chỗ hai vị trí kề nhau ( (푖), (푖 + 1)) và giữ nguyên các vị trí cịn lại. ∗ Cho 푖, 푗 ∈ ℕ , 푖 < 푗 ≤ 푛. Xét ánh xạ 푖푗: 푃푛→푃푛 푖푗 = 푗―1표 푗―2표 푗―3표 표 푖+2표 푖+1표 푖표 표 푗―3표 푗―2표 푗―1(1) Là hợp thành của 2(푗 ― 푖) ―1 ánh xạ. Dễ thấy ( ) thu được từ bằng cách đổi vị của ( 푖푗 trí (푖), (푗)) và giữ nguyên các vị trí cịn lại . Gọi ( ) là số nghịch thế của hốn vị . ( ) ― 1 푛ế ( (푖); (푖 + 1)) 푙à 푛 ℎị ℎ 푡ℎế Ta cĩ ( 푖( )) = ( ) + 1 푛ế ( (푖); (푖 + 1)) ℎơ푛 푙à 푛 ℎị ℎ 푡ℎế Do vậy ( 푖( )) ≡ ( ) +1 ( 표 2) (2). Từ (1) và (2) suy ra 푖푗( ) ≡ ( ) +1 (mod2) (3). Giả sử là thứ tự của 푛 học sinh sau lần thổi cịi thứ k của thầy giáo. Ta cĩ ∈ 푃푛 và +1 = 푖푗 ( ) với 1 ≤ 푖 < 푗 ≤ 푛 nào đĩ. Theo (3) ta cĩ ( +1) ≡ ( ) +1 (mod2). Do đĩ ( ) ≡ ( 0) + ≡ ( 표 2)(vì ( 0) = 0). Nếu k lẻ thì ( ) ≢ 0( 표 2) do đĩ ≠ . Vậy sau 2015 lần thổi cịi, tất các học sinh 0 cả khơng thể đứng trở lại đúng vị trí ban đầu của mình. Câu 13. Lấy ngẫu nhiên 7 số tự nhiên cĩ 7 chữ số khác nhau. Tìm xác xuất để trong đĩ cĩ đúng 4 số chẵn. 9
10. Hướng dẫn giải 6 Số các stn cĩ 7 chữ số khác nhau là: 9A9 544320 số. Trong đĩ cĩ số các số lẻ là: 5 5.8.A8 268800 số, vậy cĩ 275520 số chẵn. 7 KGM cĩ số phần tử là: C544320 . 4 3 Số cách lấy 7 stn trong đĩ cĩ đúng 4 số chẵn là C275520 C268800 =74059776000 P 0.27668828 Câu 14. 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 0 1 2 2 n n n * Câu 15. 1 . Chứng minh rằng : Cn 2Cn 2 Cn ... 2 Cn 3 n ¥ 2 . Một bình chứa 9 viên bi chỉ khác nhau về màu gồm 4 bi xanh , 3 bi đỏ , 2 bi vàng . Lấy ngẫu nhiên 2 bi . Tính xác suất để được 2 bi khác màu . Hướng dẫn giải n 0 1 2 2 3 3 n n 1. 1 x Cn Cn x Cn x Cn x ... Cn x 0 1 2 2 n n n * * Cho x = 2 : Cn 2Cn 2 Cn ... 2 Cn 3 n ¥ 2 2. Không gian mẫu : C9 36 1 1 1 1 1 1 * Kết quả thuận lợi của biến cố lấy 2 bi khác màu : C4.C3 C3.C2 C4.C2 26 26 * Xác suất để chọn được 2 bi khác màu : P 0,72 ( 72% ) 36 10