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

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 Đẳng thức xảy ra khi và chỉ khi 2 điều kiện sau được thỏa mãn:
2. + 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 Vậy có tất cả 1008! 2 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. 2, 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 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 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 .
3. 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. 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
4. 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í o hiệu 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 –1 tam 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à: 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
5. 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 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ó
6. 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. 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 1 2 n 2 thì 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 ¥ .
7. a2i 2i - Xét dãy 1;2k;3;2k 2;5;2k 3; ;2;2k 1 hay ,i ¥ . (2) a2i 1 2k 1 2i Ta có k 1 số 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. 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.
8. 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 1 và 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 1 nê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 1 nên m,9 1, bởi vậy 10 1  1 1 1  0 mod m .■ m cs 1 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).
9. 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  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ó 3 dãy nhị C 23 a b c d phân khác nhau do đó có tối đa 3 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 đỏ.
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ẻ.
11. Bài 21. Trên bảng có một số nguyên. Người ta ghi nhớ chữ số cuối cùng của số này, sau đó xoá đi và cộng thêm vào với số còn lại trên bảng 5 lần chữ số vừa xoá. Ban đầu có số 72014 . Hỏi có thể hay không sau một số lần thực hiện như thế thế ta thu được số 20147 ? Hướng dẫn giải Giả sử số đang có trên bảng là N 10a b 0 b 9 . Khi đó số nhận được sau một phép biến đổi là N a 5b Ta thấy 5N N 49a . Như vậy nếu NM7 thì N M7 . Do 72014 M7 , còn 20147 không chia hết cho 7 nên qua các phép biến đổi đã cho từ 72014 không thể thu được 20147 . Bài 22. Các số nguyên dương 1,2,3, ,2014 được sắp xếp trên một hàng theo một thứ tự nào đó. Ta thực hiện quy tắc đổi chỗ các số như sau: nếu số đầu tiên là k thì ta đổi k số đầu tiên theo thứ tự ngược lại. Chứng minh rằng sau một số hữu hạn lần thực hiện quy tắc trên thì số 1 sẽ xuất hiện ở vị trí đầu tiên. Hướng dẫn giải Giả sử k,1 k 2014 là số lớn nhất xuất hiện ở vị trí đầu tiên trong tất cả các quá trình đổi chỗ. Giả sử số k xuất hiện ở lần thứ h. Khi đó ở lần thực hiện sau lần thứ h thì số k sẽ giữ nguyên vị trí. Trong các quá trình đổi chỗ sau đó ta gọi k1 là số lớn nhất xuất hiện ở vị trí đầu tiên. Giả sử số k1 xuất hiện ở lần thứ h1 . Khi đó sau lần thứ h1 thì số k1 sẽ giữ nguyên vị trí, cứ tiếp tục như vậy thì sau một số hữu hạn bước phải dừng lại. Khi không thực hiện việc thực hiện quy tắc đổi chỗ của bài toán tức là số ở vị trí đầu tiên sẽ là số 1. Bài toán được chứng minh. Bài 23. Cho p là số nguyên tố lẻ. Tìm số tập con X của tập {1;2; ;2p}biết rằng X chứa đúng p phần tử và tổng tất cả các phẩn tử của X chia hết cho p. Hướng dẫn giải p Đặt A {c  {1;2; ;2 p}: x p} A C2 p Và Aj {x  A: S(x)  j(mod p)}với j 0,1,2, , p 1 Vì A A0  A1   Ap 1 và Ai  Aj  i j nên: A A0 A1 Ap 1 Xét đa thức: P(x) x p 1 x p 2 x 1, đa thức này có p 1 nghiệm phức { , 2 , , p 1} và p 1 Và x p 1 có p nghiệm phức phân biệt: , ,2 , , p 1, p 1, nên ta có: p x p 1 (x k ) k 1 Suy ra: 2 2 p p p p p p k k p k k k k p 2 (x ) (x ).(x ) (x )(x ) (x ) (x 1) k 1 k 1 k 1 k 1 k 1 k 1 So sánh hệ số x p của 2 vế đẳng thức: p (x k ) (x p 1)2 k 1 ta có: ( 1) p  S (x) 2 x A S (x) k Do p lẻ và nếu x Ak ta có: p 1 k  Ak . 2 0 k 0
12. p 1 k Do vậy x là nghiệm của đa thức: Q(x)  Ak x A0 2 k 1 Vì x là 1 nghiệm bất kì của đa thức: P(x) x p 1 x p 2 x 1 nên A1 A2 Ap 1 A0 2 A A A A 2 A 2 A 2 1 2 p 1 0 0 p p C p 2 A 2 p 2 là số tập con thỏa mãn bài toán. 0 p Bài 24. Trên mặt phẳng cho 2015 điểm tô màu đỏ, 2016 điểm tô màu xanh và không có ba điểm nào thẳng hàng. Ta sử dụng k đường thẳng phân biệt không đi qua các điểm đã cho để chia mặt phẳng thành nhiều phần sao cho trong mỗi phần không chứa các điểm có cả hai màu. Tìm giá trị nhỏ nhất của k. Trên mặt phẳng cho 2015 điểm tô màu đỏ, 2016 điểm tô màu xanh và không có ba điểm nào thẳng hàng. Ta sử dụng k đường thẳng phân biệt không đi qua các điểm đã cho để chia mặt phẳng thành nhiều phần sao cho trong mỗi phần không chứa các điểm có cả hai màu. Tìm giá trị nhỏ nhất của k. Hướng dẫn giải Trước hết ta sẽ trình bày một ví dụ để thấy rằng k 2015 . Đánh dấu 2015 điểm màu đỏ và 2015 điểm màu xanh xen kẽ nhau lên một đường tròn  và đánh dấu điểm màu xanh còn lại tại một vị trí bất kì của mặt phẳng. Khi đó đường tròn  được phân chia thành 4030 cung tròn với điểm đầu và điểm cuối của mỗi cung có màu sắc khác nhau. Như vậy nếu yêu cầu của bài toán được thực hiện thì mỗi cung phải giao với một số đường thẳng. Mỗi đường thẳng bất kì phải có hai 4030 điểm chung với cung tròn. Do đó cần ít nhất 2015 đường thẳng. 2 Ta còn cần phải chứng minh rằng chỉ cần 2015 đường thẳng là chia được mặt phẳng chứa 2015 điểm tô màu đỏ và 2016 điểm tô màu xanh thành các phần sao cho trong mỗi phần không chứa các điểm có cả hai màu. Trước hết ta thấy với hai điểm A, B cùng màu ta luôn có thể dùng hai đường thẳng phân biệt để tách hai điểm này khỏi các điểm còn lại. Cụ thể ta sẽ lấy hai đường thẳng song song với AB, nằm khác phía so với AB và đủ gần nhau để giữa hai đường thẳng này chỉ có hai điểm A và B. Gọi là một đường thẳng đi qua hai điểm A, B trong 4031 điểm đã cho sao cho các điểm còn lại nằm về một phía so với đường thẳng Trường hợp 1: Hai điểm A, B khác màu và giả sử A có màu đỏ. Ta dùng một đường thẳng để tách điểm A ra khỏi các điểm còn lại. Sau đó với 2014 điểm màu đỏ còn lại ta ghép thành 1007 cặp và tách riêng từng cặp điểm với các điểm khác bằng hai đường thẳng song song. Do đó ta chỉ dùng hết 1007.2 1 2015 đường thẳng để thực hiện yêu cầu bài toán. Trường hợp 2 : Hai điểm A, B cùng màu xanh Ta dùng một đường thẳng song song với AB để tách hai điểm A, B khỏi các điểm còn lại. Sau đó với 2014 điểm màu xanh còn lại ta ghép thành 1007 cặp và tách riêng từng cặp điểm với các điểm khác bằng hai đường thẳng song song. Do đó ta chỉ dùng hết 1007.2 1 2015 đường thẳng để thực hiện yêu cầu bài toán. Trường hợp 3 : Hai điểm A, B cùng màu đỏ Ta dùng một đường thẳng song song với AB để tách hai điểm A, B khỏi các điểm còn lại.
13. Sau đó với 2012 điểm màu đỏ trong 2013 điểm màu đỏ còn lại ghép thành 1006 cặp và tách riêng từng cặp điểm với các điểm khác bằng hai đường thẳng song song. Điểm màu đỏ còn lại ta ghép với điểm A và dùng hai đường thẳng song song để tách rời hai điểm đó với các điểm còn lại Do đó ta chỉ dùng hết 1006.2 1 2 2015 đường thẳng để thực hiện yêu cầu bài toán. Vậy ta có giá trị nhỏ nhất của k là 2015. Bài 25. Các số nguyên dương 1,2,3, ,2014 được sắp xếp trên một hàng theo một thứ tự nào đó. Ta thực hiện quy tắc đổi chỗ các số như sau: nếu số đầu tiên là k thì ta đổi k số đầu tiên theo thứ tự ngược lại. Chứng minh rằng sau một số hữu hạn lần thực hiện quy tắc trên thì số 1 sẽ xuất hiện ở vị trí đầu tiên. Hướng dẫn giải Giả sử k,1 k 2014 là số lớn nhất xuất hiện ở vị trí đầu tiên trong tất cả các quá trình đổi chỗ. Giả sử số k xuất hiện ở lần thứ h. Khi đó ở lần thực hiện sau lần thứ h thì số k sẽ giữ nguyên vị trí. Trong các quá trình đổi chỗ sau đó ta gọi k1 là số lớn nhất xuất hiện ở vị trí đầu tiên. Giả sử số k1 xuất hiện ở lần thứ h1 . Khi đó sau lần thứ h1 thì số k1 sẽ giữ nguyên vị trí, cứ tiếp tục như vậy thì sau một số hữu hạn bước phải dừng lại. Khi không thực hiện việc thực hiện quy tắc đổi chỗ của bài toán tức là số ở vị trí đầu tiên sẽ là số 1. Bài toán được chứng minh. Bài 26. Trong mặt phẳng cho 6 điểm tùy ý sao cho không có ba điểm nào thẳng hàng. Người ta tô mỗi đoạn thẳng tạo ra từ 6 điểm này bằng một trong hai màu đen hoặc trắng. Chứng minh tồn tại một tam giác có các cạnh được tô cùng màu. Hướng dẫn giải Từ điểm A ta tạo với 5 điểm B,C, D, E , F được 5 đoạn thẳng AB, AC, AD, AE, AF. Vì chỉ tô màu đen hoặc trắng nên trong 5 đoạn thẳng trên phải tồn tại 3 đọan thẳng tô cùng màu. Không mất tính tổng quát, ta giả sử AB, AC, AD được tô màu đen. Nếu có ít nhất môt trong ba đọan thằng BC,CD, DB được tô màu đen. Không mất tính tổng quát giả sử BC tô màu đen thì ABC là tam giác thỏa yêu cầu đề bài. Nếu BC,CD, DB đều tô màu trắng thì BCD là tam giác thỏa yêu cầu đề bài. Vậy ta giải quyết được bài toán Bài 27. Cho 17 điểm trong đó 3 điểm bất kì không thẳng hàng. Mỗi đoạn thẳng nối 2 điểm giữa chúng được tô một màu trong ba loại màu: đỏ, xanh hoặc vàng. Chứng minh rằng: tồn tại ít nhất một tam giác đồng màu (tam giác có ba cạnh được tô cùng một màu). Hướng dẫn giải Từ điểm A thuộc 17 điểm đã cho, ta vẽ được 16 đoạn thẳng và mỗi đoạn thẳng được đem tô 1 trong 3 màu => có ít nhất 6 đoạn thẳng có cùng màu. Giả sử 6 đoạn thẳng có cùng màu đỏ là AA1, AA2 , AA3 , AA4 , AA5, AA6. Từ 6 điểm A1, A2 , A3 , A4 , A5 , A6 nếu có 1 đoạn thẳng được tô màu đỏ thì có 1 tam giác đồng màu đỏ. Ngược lại: nếu các đoạn thẳng được tô màu xanh hoặc vàng Từ đỉnh A1, ta vẽ được 5 đoạn thẳng do được tô bằng 1 trong hai màu xanh hoặc vàng => có ít nhất 3 đoạn thẳng cùng màu Giả sử 3 đoạn thẳng cùng màu xanh là A1B1, A1B2 và A1B3. Nếu ba điểm B1, B2 , B3 có một đoạn thẳng được tô màu xanh là thì có được một tam giác đồng màu. Nếu các đoạn thẳng từ ba điểm B1, B2 , B3 được tô màu vàng thì ta có được một tam giác đồng màu. Bài 28. Cho đa giác đều H có n đỉnh ( n 6 ) nội tiếp trong đường tròn tâm O. Xét các tam giác có 3 đỉnh lấy từ n đỉnh của đa giác đều H . Tìm n biết rằng trong số tam giác đó, số tam giác mà ba cạnh
14. không là cạnh của đa giác đều H bằng 5 lần số hình chữ nhật có bốn đỉnh trong n đỉnh của đa giác đều H . Hướng dẫn giải Số tam giác có 1 cạnh là cạnh của hình H là n n – 4 Số tam giác có 2 cạnh là cạnh của hình H là n Số tam giác có ba cạnh không là cạnh của đa giác đều H và có ba đỉnh trong n đỉnh của đa giác đều H 3 4 2 là Cn n(n 4) n Cn n 3n Một hình chữ nhật nội tiếp trong đường tròn có hai đường chéo cắt nhau tại tâm O Hai đường chéo qua 2 tâm O của hình H tạo thành một hình chữ nhật n là số chẵn và số hình chữ nhật là Cn 2 3 2 2 2 Ta có: Cn n 3n 5Cn 4n 51n 110 0 n 10 2 Vậy n 10. Bài 29. Trên mỗi ô vuông của một bảng 7 7 ô, ta đặt một con châu chấu. Giả sử cứ sau một tiếng gõ, mỗi con châu chấu nhảy sang ô bên cạnh cùng một hàng hoặc một cột. Chứng minh rằng sau một tiếng gõ có ít nhất hai con ở cùng một ô. Hướng dẫn giải Ta tô màu trắng, đen cho mỗi ô của bảng như bàn cờ vua (tức là hai ô gần nhau cùng nằm trên một hàng hoặc một cột thì khác màu nhau). Do bàn cờ có số ô là lẻ ( 49 ô) nên số ô trắng và đen khác nhau. Ta giả sử có 25 ô trắng và 24 đen. Ban đầu có 49 con châu chấu ở 25 ô trắng và 24 đen. Sau một tiếng gõ, con châu chấu sẽ ở ô bên cạnh tức là ô có màu ngược với ô ban đầu nên 25 con châu chấu đứng ở ô trắng sẽ nhảy qua 24 ô đen. Do đó phải có 2 con châu chấu nào đó cùng đậu vào một ô. Bài 30. Trên mặt phẳng toạ độ Đêcác Oxy, có một con châu chấu ở toạ độ x; y trong đó x, y ¢ . Với N là một số nguyên dương cho trước, con châu chấu có thể nhảy từ điểm nguyên A đến điểm nguyên B nếu độ dài AB bằng N. Hỏi rằng con châu chấu có thể nhảy đến bất kì điểm nguyên nào sau hữu hạn các bước nhảy không nếu N 2025? Vì sao? Hướng dẫn giải Ta chứng minh với N 2025 thì câu trả lời là không thể Giả sử con châu chấu ở điểm A x; y và nó nhảy đến điểm B z;t . Do yêu cầu đề bài nên x z 2 y t 2 2025 Ta thấy 2025 chia hết 3, mà 1 số chính phương chia cho 3 thì dư 1 hoặc 0 nên x z M 3 và y t M 3 Khi đó x  z mod 3 ; y  t mod 3 Trường hợp 1. x, yM3 Do ban đầu con châu chấu đứng ở ô có tọa độ chia hết cho 3 nên sau mỗi bước nhảy, nó sẽ nhảy đến ô có hoành độ và tung độ đều chia hết cho 3. Như vậy, con châu chấu không thể nhảy đến các điểm nguyên mà có hoành độ hoặc tung độ không chia hết cho 3. Trường hợp 2. x M 3, yM3 hoặc xM3, y M 3 hoặc x M 3, y M 3 Do ban đầu con châu chấu đứng ở ô có hoành độ hoặc tung độ không chia hết cho 3 nên sau mỗi bước nhảy, nó sẽ nhảy đến ô có hoành độ hoặc tung độ không chia hết cho 3. Như vậy, con châu chấu không thể nhảy đến các điểm nguyên mà có hoành độ và tung độ chia hết cho 3. Bài 31. Cho số nguyên dương R và một bảng hình chữ nhật chia thành 20 15 ô vuông. Những nước đi được thực hiện trên bảng như sau: ta chuyển từ một ô vuông này đến một ô vuông kia khi khoảng cách giữa hai tâm của hai ô vuông đó bằng R . Bài toán đặt ra là làm sao có thể tìm được một dãy các nước đi để
15. chuyển từ ô này sang ô kia, mà hai ô đó nằm ở hai góc kề nhau của bảng, hai góc đó nằm trên cùng một chiều dài của bảng hình chữ nhật nói trên. a) Bài toán có giải quyết được không khi R chia hết cho 2 hoặc chia hết cho 3? Tại sao? b) Bài toán có giải quyết được không khi R 73? Tại sao? Hãy tìm dãy các nước đi nếu bài toán giải được. Hướng dẫn giải a) Giả sử cứ mỗi lần di chuyển là một hình chữ nhật có hai cạnh là m,n . Do đó m2 n2 R Nếu R chia hết cho 2 thì m,n cùng chẵn hoặc cùng lẻ. Tô màu các ô vuông như bàn cờ sau: (0;0) (19;0) Như vậy, nếu ở ô trắng thì sẽ di chuyển đến ô trắng, nếu ở ô đen thì sẽ di chuyển đến ô đen. Nhưng hai ô ở hai góc kề nhau( dọc theo chiều dài của bảng hình chữ nhật) khác màu nhau nên bài toán không giải quyết được khi R chia hết cho 2 Nếu R chia hết cho 3 thì cả m,n đều chia hết cho 3. Như vậy nếu ô đầu tiên có tọa độ 0;0 , thì bước tiếp theo sẽ chuyển đến ô có tọa độ là số chia hết cho 3. Nhưng ô cuối cùng cần đến là ô 19;0 nên bài toán không giải quyết được. a) Nếu R 73 thì ta có m 8;n 3 hoặc m 3;n 8 . Từ ô bắt đầu, ta có 4 nước đi: A: x; y đến x 8; y 3 B: x; y đến x 3; y 8 C: x; y đến x 8; y 3 D: x; y đến x 3; y 8 Và ta xem như nước đi x 8; y 3 là nước đi âm theo dạng A; x 3; y 8 là nước đi âm theo dạng B; x 8; y 3 là nước đi âm theo dạng C; x 3; y 8 là nước đi âm theo dạng D. Giả sử ta thực hiện dãy các nước đi gồm a nước dạng A , b nước dạng B , c nước dạng C , d nước dạng D . Bài toán giải được, nếu hệ phương trình sau có nghiệm: 8 a c 3 b d 19 3 a c 8 b d 0 Ta thấy một nghiệm của hệ trên là a 5;b 1;c 3;d 2 Như vậy, bài toán giải được và dãy các nước đi được thực hiện như sau: a a c d a a c 0;0 8;3 16;6 8;9 11;1 19;4 27;7 19;10 b c a d 16;2 8;5 16;8 19;0