Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 5

Nội dung text: Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 5

1. Bài 1. Một hàng cây vải gồm 99 cây thẳng hàng được đánh số cây theo thứ tự từ 1 đến 99. Ban đầu mỗi cây có một con ong đậu trên đó để hút mật hoa. Sau đó, cứ mỗi giờ có hai con ong nào đó bay sang hai cây bên cạnh để tìm và hút mật nhưng theo hai chiều ngược nhau. Hỏi sau một số giờ, có hay không trường hợp mà a) Không có con ong ở cây có thứ tự chẵn. b) Có 50 con ong ở cây cuối cùng. Hướng dẫn giải Ta gán cho con ong đang ở cây nào thì có một thẻ ghi số thứ tự của cây đó. Gọi S n là tổng các số ghi trên thẻ của tất cả các con ong trong giờ thứ n. Vì mỗi giờ có hai con ong nào đó bay sang hai cây bên cạnh nhưng theo hai chiều ngược nhau nên S n không hề thay đổi. Vậy S n S 1 1 2 3  99 50.99. a) Vì có lẻ 99 con ong nên nếu không con ong nào ở cây có thứ tự chẵn thì S n là tổng của 99 số lẻ, tức là S n là số lẻ, mâu thuẫn. Vậy trường hợp này không xảy ra. b) Nếu có 50 con ong ở cây cuối cùng thì S n 99.50, mâu thuẫn. Vậy trường hợp này cũng không xảy ra. Bài 2. 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 a2 ta xét 100 số có dạng 0 a1,a2 ,a1 a2 ,a1 a2 a3 ,........,a1 a2 ... 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. Bài 3. Cho n là một số nguyên dương và giả sử a1;a2 ;...;a2016 là một hoán vị của tập hợp 2016 1 2 A 1;2;3;...;2016. Hỏi có bao nhiêu hoán vị a1;a2 ;...;a2016 thỏa mãn  ak k 2016 . k 1 2 Hướng dẫn giải Với mỗi k 1;2;3;...;2016 , kí hiệu bk max ak ;k;ck min ak ;k . 2016 2016 2016 2016 Khi đó  ak k  bk ck  bk  ck . k 1 k 1 k 1 k 1 2016 Chú ý rằng  bk 2 1009 1010 1011 ... 2016 1008.3025 k 1 2016  ck 2 1 2 3 ... 1008 1008.1009 k 1 2n 1 2 Suy ra  ak k 1008 3025 1009 2016 k 1 2 1
2. Đẳng thức xảy ra khi và chỉ khi 2 điều kiện sau được thỏa mãn: + Với mọi k 1;2;3;...;1008 thì ak 1009;1010;1011;...;2016 + Với mọi k 1009;1010;1011;...;2016 thì ak 1;2;3;...;1008 2 Vậy có tất cả 1008! hoán vị thỏa mãn. Bài 4. 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 Ta giải bài toán trong trường hợp lập bảng “ m hoàn thiện” kích thước 3x3. Gọi x, y, z,t lần lượt là các số điền được ở đường chéo chính và ô ở vị trí dòng 1 cột 2, khi đó các số còn lại ở các ô được xác định duy nhất như hình bên dưới. x t m x t m z x y t y x t z y t z m y t z Vì các số được điền là không âm và y là số nhỏ nhất trong các số ở đường chéo chính nên các điều kiện sau phải thỏa: x, y, z,t 0; x t m; x t z; z y t m; x y t m z; y min x, y, z Các điều kiện trên có thể rút gọn lại thành: 0 y min x, y, z; x t m; z y t * Khi đó 0 y 2y t z x y t z x t m . Ta thấy rằng bộ bốn số không âm y;2y t z; x y t z; x t sắp theo thứ tự tăng dần xác định duy nhất bộ các số x, y, z,t thỏa mãn * và tương ứng với một cách lập bảng “ m hoàn thiện”. Do vậy, số cách lập 4 được làCm 4. 4 Áp dụng với m 2015 được kết quả là C2019. Bài 5. Có n học sinh (n 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? Đá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 Pn là tập các hoán vị của 1;2;...;n. Hướng dẫn giải 2
3. Gọi 1 , 2 ,, n là một hoán vị của 1,2,,n. Cặp (i , j ) của gọi là 1 nghịch thế của nếu i j và i j . Xét ánh xạ fi : Pn Pn mà fi thu được từ bằng cách đổi chỗ hai vị trí kề nhau i , i 1 và giữ nguyên các vị trí còn lại. * Choi, j N , i j n . Xét ánh xạ fij : Pn Pn fij f j 1of j 2of j 3oofi 2ofi 1ofioof j 3of j 2of j 1 1 Là hợp thành của 2 j i 1 ánh xạ. Dễ thấy fij thu được từ bằng cách đổi vị trí của i , j và giữ nguyên các vị trí còn lại. Gọi T là số nghịch thế của hoán vị . ( ) ― 1 푛ế ( (푖); (푖 + 1)) 푙à 푛 ℎị ℎ 푡ℎế Ta có T f i ( ) + 1 푛ế ( (푖); (푖 + 1)) ℎô푛 푙à 푛 ℎị ℎ 푡ℎế Do vậy T fi  T 1 mod2 (2). Từ (1) và (2) suy ra T fij  T 1 mod2 (3). Giả sử k là thứ tự của n học sinh sau lần thổi còi thứ k của thầy giáo. Ta có k Pn và k 1 fij k với 1 i j n nào đó. Theo (3) ta có T k 1  T k 1 mod2 . Do đó T k  T 0 k  k mod2 (vìT 0 0). Nếu k lẻ thì ( ) ≢ 0( 표 2) do đó k 0 . Vậy sau 2015 lần thổi còi, tất cả các học sinh không thể đứng trở lại đúng vị trí ban đầu của mình. Bài 6. 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:  S ai 2013S là một số chẵn S là số chẵn. 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. 3
4. Vậy không tồn tại tập hợp với tính chất đã nêu. Bài 7. 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 a2 ta xét 100 số có dạng: 0 a1,a2 ,a1 a2 ,a1 a2 a3 ,........,a1 a2 ... 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. Bài 8. 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. 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 o m Ai Aj là số đo của cung đó. Một cung được gọi là tù nếu 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. Mỗi cung tù chứa s –1điểm thì có n – s –1tam 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  s 1 xn s xs n 1 2 ... nếu n lẻ 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 ... . nếu n chẵn. s 1 2 2 2 2 2 8 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à: 4
5. 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 Bài 9. 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. +) 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. Bài 10. 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 a1 b1 a2 b2 a3 b3 Xét phân tích 6 2 .3 2 .3 2 .3 với a1 a2 a3 9 b1 b2 b3 9 Với mỗi a1 ¥ , 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. +) 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 Bài 11. 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 5
6. Giả sử A1 A2...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. 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ì X i 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 X i hoặc Yi là số lẻ, còn số kia chẵn. Từ (1) suy ra số cặp X i ;Yi mà X i lẻ là một số chẵn.Từ (2) suy ra số các cặp X i ;Yi mà i lẻ là một số chẵn nên số cặp X i ;Yi là chẵn. Như vậy trong mọi trường hợp n đều chẵn. Bài 12. Cho k số nguyên dương a1,a2 ,...,ak đôi một nguyên tố cùng nhau và một số nguyên dương n . Tìm các số nguyên dương a n sao cho a chia hết ai với i 1,2,...,k . Hướng dẫn giải * Với mỗi i 1,2,...,k ta đặt Ai a ¥ | a n,aMai  . Suy ra số các số thỏa mãn yêu cầu bài toán là: k k k k 1  Ai Ai Ai  Ai Ai  Ai  Ai ... ( 1)  Ai i 1   1 2  1 2 3 i 1 i 1 1 i1 i2 k 1 i1 i2 i3 k * n Dễ thấy Ai ai ,2ai ,...,miai  với mi ¥ và thỏa mãn miai n mi 1 .ai Ai mi ai * n Ta có Ai  Aj a ¥ | a n,aM aia j  Ai  Aj (Do (ai ,a j ) 1) aia j Hoàn toàn tương tự ta cũng có: * n A1  A2 ... Ak a ¥ | a n,aM a1a2...ak  A1  A2 ... Ak a1a2...ak Vậy k k k k 1  Ai Ai Ai  Ai Ai  Ai  Ai ... ( 1)  Ai i 1   1 2  1 2 3 i 1 i 1 1 i1 i2 k 1 i1 i2 i3 k k n n n k 1 n    ... ( 1) i 1 a 1 i i k a a 1 i i i k a a a a a ...a i 1 2 i1 i2 1 2 3 i1 i2 i3 1 2 n Bài 13. Với mỗi số nguyên dương n có tồn tại hay không một hoán vị a1,a2 ,...,an của tập 1,2,...,n thỏa mãn: trong các số 0;a1;a1 a2 ;a1 a2 a3;...;a1 a2 ... an không có hai số nào có cùng số dư khi chia cho n 1. 6
7. Hướng dẫn giải n + Nếu n chẵn ta có a a ... a 1 2 ... n n 1 đồng dư với 0 modun n 1. Vậy với n chẵn thì 1 2 n 2 không tồn tại hoán vị nào thỏa mãn yêu cầu bài toán. + Với n lẻ ta đi xây dựng một hoán vị của 1;2;...;n thỏa mãn yêu cầu bài toán. Đặt n 2k 1, k ¥ . a2i 2i - Xét dãy 1;2k;3;2k 2;5;2k 3;...;2;2k 1hay ,i ¥ . (2) a2i 1 2k 1 2i Ta có k 1số lẻ 1,3,...,2k 1 và k số chẵn 2,4,...,2k được xếp xen kẽ với nhau trong đó các chữ số lẻ xếp theo thứ tự tăng dần các số chẵn xếp theo thứ tự giảm dần, do đó dễ thấy mỗi số trong tập 1,2,...,2k 1 xuất hiện trong dãy (2) đúng một lần. * - Tìm số dư của bm a1 a2 ... am ,m ¥ khi chia cho n 1 2k 2 . Với m lẻ ta có a1 1 mod 2k 2 , a2 a3 a4 a5 ... a2k a2k 1 2k 3 1 mod 2k 2 m 1 do đó b a a a ... a a  mod 2k 1 . m 1 2 3 m 1 m 2 b1,b3 ,...,b2k 1  1,2,...,k 1 mod 2k 2 Với m chẵn ta có a1 a2 a3 a4 ... a2k 1 a2k 2k 1  1 mod 2k 2 m do đó b  mod 2k 2 b ,b ,...,b   1, 2,..., k mod 2k 2 . m 2 2 4 2k Vậy với n lẻ luôn tồn tại một hoán vị của 1;2;...,n thỏa mãn yêu cầu bài toán. Bài 14. 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í dụ a và b, bởi a b a b và . Hỏi có thể nhận được bộ số 28;4;2014 sau khi thực hiện hữu hạn phép biến đổi từ bộ số 2 2 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 Trong mọi cấu hình ta luôn có: Tổng bình phương các số là không đổi Lại có: 12 22 32 282 42 20142 Vậy câu trả lời là phủ định. 7
8. Bài 15. 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. Bài 16. Cho m,n,k là các số nguyên dương thoả mãn m 1và 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: (i) A k ; (ii) 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 .■ Bài 17. Chứng minh rằng m là một số tự nhiên không chia hết cho 2 , cho 3 , cho 5 thì m sẽ là ước của một số có m chữ số dạng 11...1. Hướng dẫn giải m Vì m,2 m,5 1nên m,10 1. từ đó theo E ta có 10 1 9 9...9  0 mod m . Nhưng lại vì m cs 9 m m,3 1nên m,9 1, bởi vậy 10 1  1 1...1  0 mod m .■ m cs 1 8
9. Bài 18. Hội khỏe Phù Đổng năm 2014 có tổ chức thi đấu 4 môn thể thao chạy 100m, nhảy xa, nhảy cao, bắn cung và quy định điều kiện cho mỗi đội tham gia như sau: • Mỗi vận động viên của một đội chỉ thi đấu duy nhất một môn thể thao. • Mỗi đội có thể lựa chọn số vận động viên cho mỗi môn tùy ý (nhưng tổng số vận động viên đúng bằng 20 ). Tại lễ khai mạc, mỗi đội xếp thành một hàng dọc, các vận động viên chạy 100m cầm cờ đỏ đứng đầu, tiếp theo đến vận động viên nhảy xa cầm cờ vàng rồi đến vận động viên nhảy cao cầm cờ xanh và cuối cùng là vận động viên bắn cung cầm cờ tím. Giả sử số đội tham dự là đủ lớn, hỏi có thể có tối đa bao nhiêu loại hàng dọc (phân biệt theo độ dài mỗi màu của hàng). Hướng dẫn giải Bài này có thể giải theo phương pháp song ánh để tính số phần tử của tập hợp kết hợp với kỹ thuật dùng dãy nhị phân. 0 a,b,c,d 20 Ta thấy mỗi hàng sẽ tương ứng với một bộ 4 số (a, b, c, d) với để chỉ số lượng vận động a b c d 20 viên thi đấu mỗi môn chạy 100m, nhẩy xa, nhẩy cao, bắn cung tương ứng. Với mỗi bộ 4 số như thế ta đặt 23  3 tương ứng với dãy nhị phân 1...101...101...101...1. Dễ thấy tương ứng đó là một song ánh và có dãy nhị C 23 a b c d 3 phân khác nhau do đó có tối đa 1771 loại hàng dọc khác nhau. C 23 Bài 19. Lấy 5 điểm tùy ý sao cho không có 3 điểm nào thẳng hàng trong mặt phẳng. Khi đó vì chỉ dùng hai màu để tô các điểm nên theo nguyên lý Dirichlet phải tồn tại ba điểm trong số đó cùng màu. Giả sử đó là 3 điểm A, B,C màu đỏ. Gọi G là trọng tâm tam giác ABC. Hướng dẫn giải Nếu G có màu đỏ thì ta được tam giác có 3 đỉnh và trọng tâm màu đỏ. Nếu G có màu xanh. Kéo dài GA,GB,GC các đoạn AA', BB ',CC 'sao cho AA' 3GA, BB ' 3GB, CC ' 3GC. Gọi M , N, P tương ứng trung điểm BC,CA, AB thì AA' 3GA 6GM , suy ra AA' 2AM. Tương tự BB ' 2BN,CC ' 2CP.Do đó tam giác A' BC, B 'CA,C ' AB tương ứng nhận A, B,C làm trọng tâm. Mặt khác ta cũng có tam giác ABC, A' B 'C ' có cùng trọng tâm G.Có hai trường hợp có thể xảy ra a) Nếu A', B ',C 'có cùng màu xanh, khi đó tam giác A' B 'C ' và trọng tâm G có màu xanh. b) Nếu ít nhất một trong các điểm A', B ',C 'màu đỏ. Không giảm tổng quát, giả sử A' đỏ.Khi đó tam giác A' BC và trọng tâm A có màu đỏ. 9
10. A' A P N G C M B C' B' Bài 20. Có 1000 học sinh gồm 499 học sinh nam và 501 học sinh nữ được xếp thành 10 hàng dọc, mỗi hàng 100 học sinh. Người ta muốn chọn từ 1000 học sinh này ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 học sinh này được chọn từ 2 hàng khác nhau và có 2 cặp học sinh có cùng thứ tự đứng trong hàng (tính từ người đứng đầu tiên của hàng đó). Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ. Hướng dẫn giải Gọi mỗi nhóm 4 học sinh lấy từ hai hàng thỏa mãn yêu cầu bài toán là một đội. Đặt S { | là một đội}, O { S | có số lẻ học sinh nữ}, E { S | có số chẵn học sinh nữ}. Ta cần chứng minh rằng | O | là lẻ. Với mỗi tập con A của S, ta định nghĩa f (A)  g( ) , trong đó g( ) là số học sinh nữ của .  A Vì O  E  và O  E S nên f (S) f (O) f (E) . Hơn nữa f (E) là chẵn, suy ra f (S)  f (O) (mod 2) . Mặt khác, xét một học sinh nữ bất kì. Để tạo thành một đội, học sinh này có thể bắt cặp với một học sinh khác trong hàng bởi 99 cách, sau đó tìm 2 học sinh khác ở hàng khác bởi 9 cách. Suy ra, học sinh nữ này là thành viên của 99.9 891 đội. Có nghĩa là học sinh nữ này được tính 891 lần trong f (S) . Vì ta có 501 học sinh nữ nên f (S)  891.501 1(mod 2) Vì mỗi  O chứa một số số lẻ các học sinh nữ nên f (O) | O | (mod 2) . Suy ra | O | f (O)  f (S) 1(mod 2) . Như vậy số cách chọn những đội là một số lẻ. 10