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

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 Thay k = 1, 2, 3, ta được:
2. 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
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 2thì a1a2a3a4a5 có C7 cách chọn. 5 TH3: a6 4thì 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
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 cả m(X) 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 ). Hãy |T | 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 cả m(X) 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 ). Hãy |T | tính giá trị của m. 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 .
5. 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 hoá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: 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 hoán số vị a1, a2, ,a24 thì sau lần vượt đó sẽ có hoán vị a2,a3, ,a24,a1. Từ hoán vị trên có thể chuyển xuống hoán vị dưới bằng 23 phép chuyển vị, tức là
6. 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ừ hoán vị a 1,a2, ,a24 ta có hoá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 . Hơn nữa f1 2, f2 3 1 5 Phương trình đặc trưng x2 x 1 0 x 2
7. 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 hoá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 hoán vị p thỏa mãn s p m. Tính m n . Hướng dẫn giải Với mỗi hoá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 hoán vị p thỏa mãn s p m. Tính m n . Với mỗi hoá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 hoá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, 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
8. 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 hoán vị p thỏa mãn yêu cầu bài toá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 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
9. Đá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 hoán vị của {1,2, ,푛}. Gọi = ( (1), (2), , (푛)) là một hoá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 hoá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. 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
10. 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. Khoâng gian maãu : C9 36 1 1 1 1 1 1 * Keát quaû thuaän lôïi cuûa bieán coá laáy 2 bi khaùc maøu : C4.C3 C3.C2 C4.C2 26 26 * Xaùc suaát ñeå choïn ñöôïc 2 bi khaùc maøu : P 0,72 ( 72% ) 36 Câu 16. Có bao nhiêu cách chọn ra k người từ n người xếp hàng dọc sao cho không có 2 người liên tiếp được chọn. Hướng dẫn giải Giả sử k người được chọn là: a1;a 2 ; ;a k Gọi x1 là số người đứng trước a1 Gọi x 2 là số người đứng giữa a1 và a 2
11. Gọi xk là số người đứng giữa a k 1 và a k Và x k 1 là số người đứng bên phải a k Mỗi cách chọn bộ a1;a 2 ; ;a k bằng số cách chọn bộ x1;x2 ; ;xk ;xk 1 thỏa mãn k 1 +)  xi n k i 1 +) x1 0; x k 1 0 +) x j 0 i 2;3; ;k 1 Hàm sinh cho cách chọn x và x giống nhau là: 1 t t2 1 k 1 1 t t Hàm sinh cho số cách chon mỗi x i 2;k giống nhau là: t t2 t3 i 1 t k 1 1 1 t tk 1 Hàm sinh cho số cách chọn bộ x1;x2 ; ;xk ;xk 1 là: f t . . k 1 1 t 1 t 1 t 1 k f n k 0 Số cách chọn bộ số: a ;a ; ;a bằng số cách chọn bộ số x ;x ; ;x ;x là: 1 2 k 1 2 k k 1 n k ! Câu 17. Các số nguyên được viết vào 441 ô của bảng vuông 21´ 21. Mỗi hàng và mỗi cột có nhiều nhất 6 giá trị khác nhau. Chứng minh rằng tồn tại một số nguyên có mặt ở ít nhất 3 cột và ít nhất 3 hàng. Hướng dẫn giải Giả sử các giá trị được ghi vào bảng là 1,2, ,n. Gọi ai là số cột khác nhau mà i (i Î 1,n)có mặt và bi là số hàng khác nhau mà i có mặt. Gọi Ti là số ô được đánh số i , ta có T i Ti £ aibi Þ 441= å Ti = å aibi. Mỗi cột và mỗi hàng có không quá 6 giá trị khác nhau, nên å ai £ 6.21,å bi £ 6.21. Giả sử với mọi i , ta có ai £ 2,bi £ 2 . Khi đó: (ai - 2)(bi - 2)£ 1Þ å aibi £ 2å ai + 2å bi - 3n £ 21.24- 3n
12. Vậy n£ 21. Mặt khác nếu đặt A = {i | ai £ 2,bi ³ 3},B = {i | bi £ 2,ai ³ 3} thì với mỗi cột có 21 ô và mỗi hàng có không quá 6 giá trị khác nhau nên tồn tại giá trị xuất hiện ở 4 hàng, giá trị này thuộc A nên xuất hiện nhiều nhất là ở hai cột. Do có tất cả 21 cột nên số giá trị như thế không ít hơn é21+ 2- 1ù ê ú= 11Þ A ³ 11. ëê 2 ûú Tương tự B ³ 11,nên n ³ A + B ³ 22 . Mâu thuẫn nhận được suy ra điều phải chứng minh.