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 4) - 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 4) - Ngô Tùng Hiếu

1. TOÁN TÔ HỢP – RỜI RẠC (Phần 4) Bài 1. Cho S là một tập hợp có tính chất: i) Một phần tử là một dãy 15 kí tự viết liền nhau, mà chỉ gồm hai kí tự a và b ii) Hai phần tử phân biệt của S là hai dãy khác nhau tại ít nhất 3 vị trí. Chứng minh rằng số phần tử của S không vượt quá 211 . Hướng dẫn giải: Để cho đơn giản ta mã hóa a là 0, b là 1. Thế thì S đơn giản là tập các dãy nhị phân có độ dài 15 sao cho hai dãy bất kì có ít nhất ba vị trí khác nhau. Với mỗi phần tử s S, có đúng 15+1=16 dãy nhị phân độ dài 15 (bao gồm cả s ) khác s tại nhiều nhất một vị trí. Ta kí hiệu Bs là tập các dãy như vậy (các phần tử của Bs ngoại trừ s đều không nằm trong S ). Với s, t S phân biệt ta có Bs  Bt  vì một dãy thuộc Bs khác s tại nhiều nhất một vị trí do vậy khác t tại ít nhất 2 vị trí và như thế không thể thuộc Bt . 15 11 Do đó, S .16  Bs U Bs 2 cho nên S 2 . s S s S Bài 2. Cho một bảng hình vuông gồm 2013 2013ô vuông. Hỏi có bao nhiêu cách tô hai màu xanh hoặc đỏ vào các ô vuông trong bảng sao cho mỗi hình vuông 2 2 có số ô được tô bởi hai màu bằng nhau. ( Hai cách tô được gọi là khác nhau nếu có một ô vuông nào đó mà trong cách này thì được tô màu đỏ còn cách kia thì được tô màu xanh). Hướng dẫn giải: Gọi Sn là số cách tô trong bảng n n, n 1. Xét tập Tn gồm các ô vuông nằm trong cột n (tính từ trái sang) và hàng n (tính từ trên xuống). Ta gọi An là số các cách tô sao cho hai ô kề nhau trong Tn có cùng màu và Bn là số các cách tô sao cho các ô trong Tn có màu xen kẽ. Nhận xét 1: mỗi cách tô thuộc Bn sẽ ứng với một cách tô thuộc Bn 1 , còn mỗi cách tô thuộc An sẽ ứng với một cách tô thuộc An 1 và một cách tô thuộc Bn 1 . ( Điều này suy ra khi xét bảng ô vuông n 1 n 1 có được từ bảng n n sau khi bỏ Tn ) Nhận xét 2: Mỗi cách tô thuộc Tn sẽ ứng với một cách tô thuộc Tn 1 , Mỗi cách tô thuộc Tn 1 sẽ ứng với một cách tô thuộc Tn 2 , Từ đó ta có: Bn Bn 1 , An An 1 Bn 1 , n 2 Sn An Bn An 1 Bn 1 Bn , n 2 Suy ra: Sn 2( An 1 Bn 1 ) ( An 2 Bn 2 ), n 3 = 2Sn 1 Sn 2 , n 3 (1) Nhận xét 3: S2 6 và S3 14 Đ X X Đ X X Đ Đ X Đ Đ X X Đ Đ X Đ Đ X X X Đ Đ X
2. X Đ X Đ X Đ X Đ Đ Đ Đ X Đ X Đ X Đ X X X X X Đ X X Đ X Đ X X X X Đ X Đ X X Đ X Đ Đ Đ Đ X Đ X Đ X X Đ Đ Đ Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ Từ (1) ta suy ra Sn Sn 1 = Sn 1 Sn 2 . . . =S3 S2 8 Đ X Đ Đ X Đ X Đ Đ Đ Đ X Đ X Đ Đ X Đ X X X Sn 8 Sn 1 Sn S2 (n 2)8 8n 10 X Đ X Đ X Đ Đ X X X X Đ X Đ X Đ X Đ Đ Đ Đ Vậy có S2013 8 2013 10 16094 cách tô màu thỏa yêu cầu bài toán. Bài 3. Trong mặt phẳng tọa độ Oxy, xét tập hợp S x, y | 1 x, y 12;x, y ¥  . Mỗi điểm của S được tô bởi một trong ba màu xanh, đỏ, vàng. Chứng minh rằng tồn tại hình chữ nhật có các cạnh song song với hai trục tọa độ, cố bốn đỉnh thuộc S và được tô cùng một màu. Hướng dẫn giải: Từ giả thiết suy ra số phần tử của S là 144. Không giảm tính tổng quát, giả sử tô các điểm được tô đỏ của S là nhiều nhất. Theo nguyên llý Dirichlet, số các điểm đỏ trong S ít nhất là 48. 12 Ký hiệu các điểm màu đỏ có tung độ i là mi , i 1,2, ,12 ta có  mi 48. i 1 m m 1 Số các cặp điểm màu đỏ có tung độ i là C2 i i . mi 2 Sô có cặp điểm màu đỏ có cùng tung độ trong S là : 12 12 m m 1 1 12 1 12 C2 i i m2 m  mi   mi  i i 1 i 1 2 2 i 1 2 i 1 2 1 12 1 12 1 12 12 1  mi  mi  mi  mi 12 .48 48 12 72 24 i 1 2 i 1 24 i 1 i 1 24 Vậy số các cặp điểm màu đỏ có cùng tung độ trong S ít nhất là 72 cặp. 2 Mặt khác số cặp điểm trên trục hoành có tung độ là các số nguyên từ 1 đến 12 là C12 66 . Do đó khi chiếu các cặp điểm màu đỏ lên trục hoành có ít nhất 2 cặp hình có chiều trùng nhau, hai cặp điểm này xác định hình chữ nhật thỏa mãn yêu cầu. Bài 4. Cho n là một số nguyên dương chẵn lớn hơn hoặc bằng 4. Ta tô màu mỗi
3. n n số trong các số nguyên dương từ 1 đến n sao cho số trong chúng được tô màu xanh và số còn lại 2 2 được tô màu đỏ. Với mỗi cách tô như vậy, kí hiệu fn là số các số nguyên dương bất kì mà nó có thể viết được dưới dạng tổng hai số khác màu. a. Tìm tất cả các giá trị của f4. b. Khi n 8, chứng minh rằng fn 2n 3. Hãy chỉ ra một cách tô màu thỏa mãn fn 2n 5. Hướng dẫn giải: +) Không mất tổng quát, coi 1 được tô xanh. Ta có các trường hợp sau: 1X 2X (suy ra 3Đ 4Đ) : f4 3 (các số viết dưới dạng tổng của hai số khác màu là 4; 5; 6); 1X 2Đ 3X (suy ra 4Đ) : f4 3 (các số viết dưới dạng tổng của hai số khác màu là 3; 5; 7); 1X 2Đ 3Đ (suy ra 4X) : f4 4 (các số viết dưới dạng tổng của hai số khác màu là 3; 4; 6; 7); Vậy f4 3;4. +) Ta xét với n 8. Rõ ràng fn 2n 3,do các số có thể viết dưới dạng tổng của hai số khác màu luôn lớn hơn hoặc bằng 3 và nhỏ hơn hoặc bằng 2n 1. Nếu fn 2n 3 thì từ 3 đến (n 1) đều viết được dưới dạng tổng của hai số khác màu. Và do đó, ta có thể coi 1X, 2Đ. Lại vì các số từ 4 đến (n 1) cũng viết được dưới dạng tổng của hai số khác màu nên n 3Đ, 4Đ, , (n 2) Đ. Lúc này, các số được tô Đ vượt quá , vô lý. Vậy f 2n 3. 2 n Ta chỉ ra cách tô màu thỏa mãn fn 2n 5 . Thật vậy, giả sử n 2k, ta tô X các số 1; 2; 4; ; 2k 2, tô Đ các số 3; 5; ; 2k 1; 2k. Khi đó, các số viết được dưới dạng tổng của hai số khác màu là tất cả các số từ 4 đến 4k 2, tức có 4k 5 số mà nó có thể viết được dưới dạng tổng của hai số khác màu. Bài 5. Cho tập hợp gồm 2014 phần tử sau: 1; 2; 3; ; 2014 . Cần loại bỏ ít nhất bao nhiêu phần tử khỏi tập hợp trên, sao cho tập hợp còn lại có tính chất: không có phần tử nào bằng tích hai phần tử còn lại khác. Hướng dẫn giải: Trước hết, ta loại bỏ các số 2, 3, 4, 5, , 44, và chứng minh tập các số còn lại là {1;45;46; ;2014} thỏa mãn đề bài. Thật vậy, nếu trong 2 số có một số bằng 1 thì hiển nhiên 1.x x y luôn đúng với mọi x {45; 46; ; 2014} và y {45; 46; ; 2014}\{x}. Nếu không số nào bằng 1, tức là x, y {45; 46; ; 2014} và x y , thì xy 452 2025 2014 sẽ không thuộc tập đã cho.
4. Như vậy, ta đã chỉ ra một cách loại bỏ 43 phần tử thỏa mãn đề bài. Bây giờ, ta xét một cách loại bỏ bất kỳ ít hơn 43 phần tử. Xét 43 bộ số: (2; 87; 2 87) (3; 86; 3 86) (4; 85; 4 85) . (44; 45; 44 45) Do tất cả các số trong các bộ trên đôi một khác nhau, và ta chỉ loại bỏ ít hơn 43 phần tử, nên trong tập còn lại sẽ chứa ít nhất một trong số các bộ trên. Bộ ba số ấy sẽ không thỏa mãn đề bài, nên cách loại bỏ đang xét cũng không thỏa mãn bài toán. Vậy ta cần loại bỏ ít nhất 43 phần tử. Bài 6. Trong một lớp học có 30 học sinh gồm 15 học sinh nam và 15 học sinh nữ. Các học sinh này được đánh số thứ tự từ 1 đến 30 (mỗi học sinh chỉ được đánh một số và mỗi số chỉ được đánh cho đúng một học sinh) theo nguyên tắc: Các học sinh nam được đánh số lẻ, các học sinh nữ được đánh số chẵn. Từ 30 học sinh trên có bao nhiêu cách chọn ra một nhóm học sinh mà tổng số thứ tự của các học sinh trong nhóm không nhỏ hơn 233 đồng thời số học sinh nam và số học sinh nữ trong nhóm bằng nhau. Hướng dẫn giải: Cho tương ứng mỗi nhóm học sinh được chọn với một tập con M của tập hợp A {1,2,3., ,30} thỏa mãn: “S(M)  a 233 và trong M thì số lượng các số chẵn bằng số lượng các số lẻ” (*). Ta sẽ đếm a M số các tập con M như vậy. Trước hết ta xét các tập con M của A có số lượng các số chẵn bằng số lượng các số lẻ. Số cách chọn ra k k k phần tử chẵn là C15 và số cách chọn ra k phần tử lẻ là C15 , với k {0,1, ,15}. Do đó, số cách chọn ra 15 15 k k k 2 tập con M có số lượng các số chẵn bằng số lượng các số lẻ là C15.C15 (C15 ) . k 0 k 0 15 k 2 15 Chứng minh được: (C15 ) C30 . k 0 Gọi (A) là tập các tập con của A có số lượng các số chẵn bằng số lượng các số lẻ (coi  là một tập như vậy). Ta thấy, nếu M (A) thì A \ M (A) . Bởi vậy xét ánh xạ f : (A) (A),M f (M) A \ M . Dễ thấy f là một song ánh. Vì a 465 nên nếu S(M) 233 thì S(A \ M) 232 . Suy ra, nếu M (A) thỏa mãn (*) thì a A A \ M (A) và không thỏa mãn (*), do đó số cách chọn ra nhóm học sinh thỏa mãn bài toán là | (A) | C15 30 . 2 2 Bài 7. Giả sử có sự phân hoạch ¥ thành hai tập hợp A, B. Chứng minh rằng n ¥ tồn tại a,b ¥ phân biệt lớn hơn n sao cho { a, b, a + b } là tập con của A hoặc B. Hướng dẫn giải:
5. Do ¥ A U B. - Nếu B là tập hữu hạn tồn tại m là phần tử lớn nhất của B. Với mọi n ¥ lấy a, b > max{n, m } thì a, b, a + b > m a,b,a b  A . - Nếu B là tập vô hạn n ¥ lấy b, c B phân biệt sao cho b, c > n. Lấy a B sao cho a – b > n, a > c a > n. Giả sử không tồn tại a, b phân biệt sao cho a,b,a b  A a c,b c A a,b,a b  B Do a – b > n, a, b B mà a – b+ b = a a b A . Mà ( a – b) + (b + c) = a + c A a b,b c,a c  A ( mâu thuẫn ). a, b, a+b  A Vậy a,b ¥ ,a,b n sao cho a, b, a+b  B. Bài 8. Xếp 10 học sinh ngồi quanh một bàn tròn. Ngân hàng đề có tất cả 5 loại đề thi. Hỏi có bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi? Hướng dẫn giải: Gọi Sn là số cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau có cùng đề thi Cố định một học sinh làm vị trí đầu tiên và các học sinh bên tay phải của học sinh đó là vị trí thứ 2, thứ 3, , thứ n.( học sinh ở vị trí thứ n ngồi cạnh học sinh ở vị trí thứ nhất) Ta thấy: Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi khác nhau thì sẽ có 3 cách phát đề cho học sinh ở vị trí thứ n. Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi giống nhau thì có 4 cách phát đề cho học sinh ở vị trí thứ n. Do đó ta có hệ thức: S 3S 4S n 4 n n 1 n 2 Sử dụng phương pháp sai phân để tính Sn . Xét phương trình đặc trưng: 2 x 1 n n x 3x 4 0 Sn a( 1) b4 x 4 Do S2 5.4 20,S3 5.4.3 60 Ta có:
6. a 16b 20 a 4 a 64b 60 b 1 n n 10 Vậy Sn 4 1 4 S10 4 4 Bài 9. Cho S 1,2, ,2014, với mỗi tập tập con khác rỗng T  S , ta chọn một phần tử của nó làm phần tử đại diện. Tìm số cách ký hiệu phần tử đại diện cho mọi tập con khác rỗng của S thỏa mãn với mỗi tập khác rỗng T  S là hợp của các tập khác rỗng không giao nhau A,B,C  S , thì phần tử đại diện của D cũng là phần tử đại diện của một trong ba tập A, B, C. Hướng dẫn giải: + Với mỗi tập X  S, ký hiệu r X là phần tử đại diện của X. Giả sử x1 r S . Trước hết ta chứng minh khẳng định sau: Nếu x1 X và X  S thì x1 r X . - Nếu X 2012, ta viết S thành hợp của ba tập không giao nhau gồm X và hai tập con khác nữa của S. Từ giải thiết suy ra x1 r X . - Nếu X 2013, xét phần tử y S, y x1 . Coi S là giao của ba tập không giao nhau gồm x1, y và hai tập khác nữa, áp dụng trường hợp X 2012, ta suy ra r x1, y x1 , nên y r X (vì theo giả thiết phần tử đại diện của một trong ba tập cũng là phần tử đại diện của X, mà r x1, y y và hai tập còn lại đều không chứa y). Do y lấy tùy ý nên r X y,y X, y x1 . Từ đó ta có r X x1 . - Chú ý rằng khẳng định trên vẫn còn đúng với mọi tập con của S có từ 5 phần tử trở lên. + Ta có 2014 cách chọn x1 r S , với mọi x1 X  S thì r X x1 . Xét S2 S \ x1. Tương tự ta có 2013 cách chọn x2 r S2 , với mọi x2 X  S2 thì r X x2 . Lặp lại tương tự quá trình này ta có 2014.2013 .5 cách chọn x1, x2 , , x2010 S với mỗi i 1,2, ,2010 , r X xi , xi X  S \ x1, x2 , , xi 1 . Bây giờ còn lại 4 phần tử của S ký hiệu là Y y1, y2 , y3 , y4 . Ta có 4 cách chọn r Y , giả sử y1 r Y , chứng minh tương tự trên ta có r y1, y2 r y1, y3  r y1, y4  y1 Còn 7 tập chưa có phần tử đại diện là y1, y2 , y3, y1, y3 , y4, y1, y2 , y4, y2 , y3 , y4, y2 , y3, y2 , y4, y3 , y4 , phần tử đại diện của các tập này được chọn tùy ý nên có 34.23 cách chọn. + Vậy tổng cộng có 2014.2013 .4.34.23 = 2014!.108 cách xếp phần tử đại diện cho các tập con. Bài 10. Gọi hình chữ nhật kích thước 2 3(hoặc 3 2 ) bị cắt bỏ một hình vuông 1 1 ở một góc là hình chữ nhật khuyết đơn (xem hình 1). Gọi hình chữ nhật kích thước 2 3(hoặc 3 2 ) bị cắt bỏ hai hình vuông 1 1 ở hai góc đối diện là hình chữ nhật khuyết kép (xem hình 2). Người ta ghép một số hình vuông 2 2 , một số hình chữ nhật khuyết đơn và một số hình chữ nhật khuyết kép với nhau sao cho không có hai hình nào chờm lên nhau để tạo thành một hình chữ nhật kích thước 2013 2014 . Gọi s là
7. tổng số các hình vuông 2 2 và hình chữ nhật khuyết kép cần dùng trong mỗi cách ghép hình nói trên. Tìm giá trị lớn nhất của s. Hình 1 Hình 2 Hình vuông 2 x 2 Hướng dẫn giải: Tổng quát 2013 2m 1(dòng) và 2014 2n (cột) với m 1006; n 1007 gọi s là tổng số các hình vuông 2 2 và hình chữ nhật khuyết kép, gọi y là số các hình chữ nhật khuyết đơn. Ta có đẳng thức về diện tích các hình: 4s 5y 2n(2m 1) Ta đánh dấu vào các ô có tọa độ (2r; 2t) với 1 r m và 1 t n ta được m n dấu . 1 2 3 4 5 6 2013 2014 1 2 3 4 5 2012 2013 Dễ thấy trên hình: i. Hình vuông 2 2 và mỗi hình chữ nhật kép chứa đúng một dấu
8. ii. Hình chữ nhật khuyết đơn chứa một hoặc hai dấu ta có bất đẳng thức sau về số dấu trên hình: mn s y vậy thì 5m.n 5(s y) 4s 5y s hay 5mn 2n(2m 1) s suy ra s 5m.n 2n(2m 1) mn 2n n(m 2) Áp dụng vào bài với m 1006; n 1007 ta được kết quả s 1011028 . Sự tồn tại của cách ghép với s 1011028 như trên hình vẽ: 1 2 3 4 5 6 1 2 1007 hình chữ 3 nhật khuyết kép 4 5 6 7 1003 x 1007 hình vuông 2 x 2 Bài 11. Cho tập X = {1 ; 2 ; ; 2016}. Với 3 ≤ k ≤ 2016, ta kí hiệu Fk là họ các tập con gồm k phần tử của X sao cho hai tập bất kì có chung không quá k 2 phần tử. Chứng minh tồn tại tập con Mk của X sao cho |Mk| ≥ 11 và Mk không chứa tập con nào thuộc Fk. Hướng dẫn giải: Nếu k 11 thì mọi tập k gồm 11 phần tử đều thỏa mãn.
9. Xét k 11: Chọn K là tập con lớn nhất của X không chứa tập nào thuộc Fk . Khi đó, với mọi x X K , tồn tại Ax Fk sao cho Ax K  x Đặt Bx Ax x ta có: Bx  K, Bx k 1. Dễ thấy Bx đôi một khác nhau. Do đó: k 1 X K C K . k 1 Đặt K m , ta có: 2016 m C10 (1). 10 10 i 0 1 k 1 k 1 Mặt khác 2 C10 C10 C10 C10 11 C10 i 0 k 1 k 1 Do đó, nếu m 10 thì 2016 m 2006 C10 Cm trái với (1). Bài 12. Cho bảng hình chữ nhật kích thước m n (m n) . Một số ô có một số ngôi sao, giả sử mỗi cột có ít nhất một ngôi sao. Chứng minh rằng có ít nhất hai ngôi sao mà hàng chứa nó có nhiều ngôi sao hơn cột chứa nó. Hướng dẫn giải: N ngôi sao được đánh số từ 1 tới N Đặt ai ,bi tương ứng là số ngôi sao ở cột và hàng chứa ngôi sao thứ i. Ta cần chứng minh bi ai với ít nhất hai chỉ số i nào đó. . Nhận xét: Nếu ai k thì mọi ngôi sao cùng cột với ngôi sao thứ i có a j tương ứng là k . 1 Từ đó suy ra  n ai 1 1 1 1  m n   1 bi ai ai bi 1 1 Suy ra tồn tại hai chỉ số i để 0 hay bi ai với hai chỉ số. ai bi đpcm. Bài 13. Trên đường tròn ngoại tiếp đa giác lồi 2n đỉnh (n lẻ, lớn hơn 2), ta đặt tại đỉnh thứ i số ( 1)i .i . Một phép biến đổi là thay hai số tại hai đỉnh tùy ý bởi hai số mới : số mới tăng 1 đơn vị so với số cũ nếu số cũ âm và giảm 1 đơn vị so với số cũ nếu số cũ không âm. Sau một số phép biến đổi như vậy ta có thể thu được tất cả các số tại 2n đỉnh của đa giác là các số bằng nhau không? Hướng dẫn giải: Xét đa giác A1A2 A2n và tại đỉnh A1 ta đặt số -1, tại đỉnh A2 ta đặt số 2, , tại đỉnh thứ 2n ta đặt số 2n. Tổng tất cả các số trên đường tròn ban đầu là n (số lẻ).
10. Xét tính chất chẵn, lẻ của tổng 2n số trên đường tròn sau mỗi phép biến đổi thì tính chất này không đổi. Thật vậy, có ba trường hợp sau . Nếu hai số bị tác động đều là các số chẵn thì hai số này sau phép biến đổi đều là các số lẻ, do đó tính chẵn, lẻ của tổng hai số này không đổi sau phép biến đổi. Các số còn lại không đổi nên tính chẵn, lẻ của tổng của 2n số không đổi sau phép biến đổi. . Nếu hai số bị tác động đều là các số lẻ thì hai số này sau phép biến đổi đều là các số chẵn, tương tự trên, tính chẵn, lẻ của tổng của 2n số không đổi sau phép biến đổi. . Nếu hai số bị tác động có một số lẻ, một số chẵn thì hai số này sau phép biến đổi cũng là một số lẻ, một số chẵn, do đó tính chẵn, lẻ của tổng của 2n số không đổi sau phép biến đổi. Nếu có thể thu được tất cả các số tại 2n đỉnh là các số bằng nhau thì tổng của 2n số này là một số chẵn. Điều này không thể xảy ra do ban đầu tổng này là số lẻ. Vậy không thể thu được tất cả các số tại 2n đỉnh của đa giác là các số bằng nhau. Bài 14. Quần đảo Hoàng Sa có 3 loài chim bồ câu đang sinh sống, mỗi loài mang một màu sắc khác nhau , loài màu xám có 133 con, loài màu nâu 155 con và loài màu xanh có 177 con. Giả sử cứ hai con bồ câu khác màu gặp nhau thì chúng đồng thời đổi sang màu thứ ba và hai con bồ câu cùng màu gặp nhau thì chúng giữ nguyên không đổi màu. Có xảy ra tình trạng tất cả loài chim bồ câu đang sống trên đảo trở thành cùng một màu hay không? Hướng dẫn giải: Khi chia các số 133; 155; 177 cho 3 được lần lượt các số dư là:1; 2; 0 Ta xét: Nếu 1 con bồ câu xám gặp 1 con bồ câu nâu, thì chúng đồng thời đổi thành màu xanh. Khi đó ta có 132 con xám, 154 con nâu, và 179 con xanh. Những số dư của 132; 154; 179 cho 3 tương ứng là 0;1 và 2, nghĩa là lại gặp lại đầy đủ các số dư đã có. Nếu 1 con bồ câu xám gặp con bồ câu màu xanh thì chúng đồng thời đổi sang màu nâu. Khi đó ta có 132 con bồ câu xám, 157 con bồ câu nâu, và 176 con bồ câu xanh. Lấy những số trên chia cho 3 cho số dư tương ứng là 0,1 và 2, nghĩa là lại gặp cả 3 khả năng của số dư. Nếu bồ câu nâu và bồ câu xanh gặp nhau, thì chúng cùng đổi thành màu xám. Khi đó có 135 con bồ câu xám, 154 con ồ câu nâu và 176 con ồ câu xanh. Số dư củ những con bồ câu trên chia cho 3 tương ứng là 0,1và 2, vẫn có đầy đủ các số dư khi chia cho 3 Bất biến ở đây là dù thay đổi mầu như thế nào thì số dư của các sô lượng bồ câu chia cho 3 đều có đầy đủ 0,1,2. Số lượng tất cả thằn lằn trên đảo là 133+ 155+ 177= 465 là một số chia hết cho 3. Nếu tất cả các con bồ câu đều cùng một màu thì số dư của số lượng bồ câu màu xám, nâu và đỏ chia cho 3 tương ứng là 0,0,0. Điều này vô lý vì các số dư phải có đầy đủ các số dư này khi chia cho 3. Như vậy câu trả lời là không thể được. Bài 15. Cho trước số nguyên dương n 2 . Trong một giải đấu cờ vua có 2n vận động viên tham gia, mỗi người đấu với người khác đúng một ván. Tại một thời điểm trong giải, người ta thấy có n2+1 ván đấu đã diễn ra. Chứng minh rằng khi đó có thể chọn ra ba vận động viên sao cho hai người bất kỳ đều đã thi đấu với nhau. Hướng dẫn giải: Ta chứng minh bằng quy nạp theo n. Với n = 2: Giả sử có bốn vận động viên theo dự là A, B, C, D và có 5 ván đấu đã diến ra.
11. Nếu hai trong ba người B, C, D đều đã đấu với nhau một ván thì ta có điều phải chứng minh. Nếu có hai trong ba người B, C, D chưa đấu với nhau thì mỗi người B, C, D đều đã đấu với A một ván. (Nếu không thì số ván sẽ ít hơn 5). Khi đó ba người A, B, C thỏa mãn yêu cầu bài toán. Giả sử bài toán đúng với n = k (k N*,k 2) Ta chứng minh bài toán đúng với n = k + 1. Giả sử E và F là hai vận động viên đã đấu với nhau. Nếu tổng ván đấu giữa 2k vận động viên còn lại không ít hơn k 2+1 thì theo giả thiết quy nạp ta có điều phải chứng minh. Nếu tổng số ván đấu giữa 2k vận động viên không vượt quá k 2 tổng số ván mà E và F đã đấu không ít hơn 2k+1(không kể ván đấu giữa E và F). Do đó trong số 2k vận động viên còn lại, phải có một người G đã đấu với cả E và F. Khi đó ta có ba vận động viên E, F, G thỏa yêu cầu bài toán. Vậy bài toán được chứng minh. Bài 16. Giả sử có 20 người, xếp ngồi vào 4 bàn riêng biệt. Cách xếp tốt là những người ngồi cùng bàn đều quen nhau. Giả sử tồn tại cách xếp tốt, đồng thời đối với mọi cách xếp tốt, ta đều có đúng 5 người ngồi mỗi bàn. Hỏi có nhiều nhất bao nhiêu cặp quen nhau ? Hướng dẫn giải: Xét nhân vật A thuộc bàn 1, suy ra trong mỗi bàn 2, 3, 4 đều có ít nhất một người không quen A. Vì nếu quen hết 5 người trong 1 trong các bàn 2, 3, 4 thì A phải sang bàn đó, nhưng lại là 6 người (trái với giả thiết là 5 người). Suy ra số người mà A không quen lớn hơn hoặc bằng 3 người. Do đó mỗi người quen nhiều nhất là 16 người. 20.16 Mà số cặp quen nhau nhỏ hơn hoặc bằng 160 . 2 3.20 Giả sử có đúng 160 cặp quen nhau thì có đúng 30 cặp không quen nhau. 2 Suy ra có thể xếp thành 5 nhóm, mỗi nhóm 4 người không quen nhau. Mỗi người đều quen với những người thuộc 4 nhóm còn lại. Ghép người đó với mỗi nhóm 1 người vào một bàn, ta được cách xếp tốt. Bài 17. Trên bảng ô vuông 3x3, người ta đặt một số viên sỏi sao cho mỗi ô vuông có không quá một viên sỏi. Với mỗi cách đặt ta cho tương ứng với số điểm bằng tổng số : các hàng, các cột, các đường chéo chứa số lẻ các viên sỏi trên đó. Bảng không có sỏi ứng với 0 điểm. a) Tồn tại hay không cách đặt sỏi sao cho ô chính giữa bảng không có sỏi và số điểm tương ứng với cách đặt đó là 8. b) Chứng minh rằng số cách đặt sỏi với điểm số là một số chẵn bằng số cách đặt sỏi với điểm số là một số lẻ. Hướng dẫn giải: a) Giả sử ô chính giữa không có sỏi và điểm số của cách đặt là 8. Như vậy 3 hàng , 3 cột và hai đường chéo đều có một số lẻ viên sỏi. Gọi a, b, c, d là số sỏi trong các ô như hình vẽ , a,b,c,d 0,1 . Khi đó các ô đối xứng với a, b, c, d qua tâm sẽ có số sỏi tương ứng là a ',b',c',d' sao cho a a ' b b' c c' d d' 1
12. a b c 0 d Từ đó a b c a ' b' c' 3 suy ra một trong hai tổng a b c hoặc a ' b' c' là một số chẵn. Khi đó dòng thứ nhất hoặc dòng thứ ba có tổng số sỏi là một số chẵn, mâu thuẫn với giả thiết ban đầu. Vậy không tồn tại cách đặt sỏi thỏa mãn điều kiện bài toán. b) Ta gọi hai cách đặt sỏi là liên hợp với nhau nếu ô trên cùng bên trái của chúng có số sỏi khác nhau và các ô còn lại tương ứng có số sỏi như nhau. a b c a b c f e d f 0 d g h i g h i ( B) (B’) Như vậy, các cách đặt sỏi chia thành từng cặp đôi một liên hợp với nhau. Xét hai cách đặt liên hợp với nhau (B) và (B’). Tổng số sỏi ở dòng 1, cột 1 và 1 đường chéo cả hai bảng đôi một khác nhau về tính chẵn lẻ. Các dòng, cột và đường chéo còn lại của hai bảng có số sỏi như nhau. Do đó điểm số của ( B) và (B’) khác nhau 3 đơn vị, suy ra số điểm của ( B) và (B’) có tính chẵn lẻ khác nhau. Vậy hai cách đặt liên hợp với nhau, một cách xếp có điểm số chẵn, cách đặt còn lại có điểm số là một số lẻ suy ra điều phải chứng minh. Bài 18. Các số tự nhiên 0,1,2,3, được điền vào bảng ô vuông kích thước 2015 2015 (mỗi ô một số), bắt đầu từ số 0 ở chính giữa bảng, đến các số tiếp theo được điền theo hình xoắn ốc ngược chiều kim đồng hồ như hình vẽ bên dưới: 1) Biết rằng các cột của bảng được đánh số từ 1 đến 2015 từ trái sang phải và các dòng của bảng được đánh số từ 1 đến 2015 theo thứ tự từ trên xuống dưới. Hỏi theo cách điền trên thì số 2015 nằm ở dòng nào, cột nào? 2) Người ta cho phép thực hiện thao tác sau: Đầu tiên, thay số 0 ở giữa bảng bằng số 14. Mỗi lần sau đó, người ta sẽ chọn ra 12 ô vuông liên tiếp thuộc cùng hàng, hoặc 12 ô vuông liên tiếp thuộc cùng cột, hoặc 12 ô vuông thuộc một bảng hình chữ nhật 3 4 rồi cộng thêm 1 vào tất cả các ô được chọn (mỗi lần chỉ được chọn 1 trong 3 loại hình trên). Hỏi sau một số hữu hạn lần, có thể làm cho tất cả các ô vuông của bảng đã cho đều chia hết cho 2016 được không?
13. Hướng dẫn giải: 1) Ta có các nhận xét sau: i. Trong một bảng ô vuông con có kích thước lẻ (2n 1) (2n 1) và có tâm là ô chứa số 0, tất cả (2n 1)2 số từ 0 đến (2n 1)2 1 đều được điền và cột đầu tiên tính từ trái sang của bảng này chứa 2n 1 số lớn nhất (số lớn nhất là (2n 1)2 1 nằm cuối cột đó). ii. Số 0 nằm ở hàng 1008, cột 1008 của bảng. Từ đó, ta thấy rằng: Vì 2015 452 2025 nên số này nằm trong bảng ô vuông 45 45 và số lớn nhất trong bảng này là 2024. Số 2024 nằm ở cột 1 của bảng này, tương ứng là cột thứ 1008 22 986 của bảng đã cho. Số 2024 nằm ở dòng 45 của bảng này, tương ứng là dòng thứ 1008 22 1030 của bảng. Do 2024 2015 9 nên số 2015 sẽ nằm cao hơn số 2024 là 9 dòng, suy ra số 2015 nằm ở dòng thứ 1030 9 1021. Vậy số 2015 nằm ở dòng thứ 1021 và cột thứ 986 của bảng. 2) Sau bước thay 0 bởi 14, ta thấy tổng các số của bảng là: 20152 20152 1 14 1 2 3 20152 1 14 . 2 Dễ thấy số này chia 4 dư 2. Trong thao tác cộng các số trong 12 ô (bất kể nằm trên hàng nào, cột nào) của bảng thì tổng các số tăng lên đúng 12 đơn vị. Suy ra số dư của tổng các số trên bảng khi chia cho 4 là bất biến trong suốt quá trình. Để bảng có tất cả các số chia hết cho 2016 thì dễ thấy tổng của chúng phải chia hết cho 4, đây là điều không thể xảy ra. Vậy câu trả lời là phủ định. Bài 19. Tìm tất cả các số nguyên dương n sao cho tập A 1,3,,2n 1 có thể phân hoạch thành 12 tập con mà tổng các phần tử của mỗi tập con đều bằng nhau. Hướng dẫn giải: n2 Tổng các phần tử của A bằng n2 . Do đó, mỗi tập con có tổng các phần tử bằng , suy ra 12 n 6k,k ¥ *. Khi đó tổng các phần tử của mỗi tập con bằng 3k2. Vì 2n 1 12k 1 thuộc một tập con nào đó nên suy ra 12k 1 3k2 k 4. Nếu k 5 thì A 1,3,,59 chia thành 12 tập con, mỗi tập con có tổng các phần tử bằng 75, do đó mỗi tập con đều có nhiều hơn một phần tử. Hơn nữa, số các phần tử của mỗi tập con là một số lẻ, do đó mỗi tập con có ít nhất ba phần tử. Suy ra A có ít nhất 3.12 36 phần tử, vô lý vì A 30. 12 Với k 4, ta có phân hoạch A 1,3,,47 UBi , với Bi 2i 1,49 2i thỏa mãn. i 1
14. Với k 6, thì A 1,3,,71, xét các tập Bi 35 2i,73 2i với i 1,2,,9 ; B10 23,25,29,31, B11 19,21,33,35, B12 1,3,5,7,9,11,13,15,17,27, ta có một phân hoạch thỏa mãn bài toán. Với k 7, thì A 1,3,,83, xét các tập Bi 4i 3,65 2i,85 2i với i 1,2,,10; B11 3,27,35,39,43, B12 7,11,15,19,23,31,41, ta có một phân hoạch thỏa mãn bài toán. Với k 9, thì A 1,3,,107, xét các tập Bi 23 8i,109 4i,111 4i với i 1,2,,7; B8 1,41,65,67,69, B9 3,15,73,75,77, B10 29,37,57,59,61, B11 5,9,17,23,25,27,33,51,53, B12 7,11,13,19,21,35,43,45,49, ta có một phân hoạch thỏa mãn bài toán. Bây giờ, giả sử k k0 thỏa mãn bài toán, khi đó k k0 4 cũng thỏa mãn bài toán. Thật vậy, giả sử Bi ,i 1,2,,12 là một phân hoạch tập A 1,3,,12k0 1 thỏa mãn bài toán. Khi đó tập A ' 1,3,,12 k0 4 1 được phân hoạch thành các tập B'i Bi  12k0 1 2i,12k0 49 2i,i 1,2,,12 thỏa mãn bài toán. Từ các trường hợp trên suy ra các giá trị k thỏa mãn có dạng 4 4m,6 4m,7 4m,9 4m . Do vậy n 6k, với k 4 hoặc k ¥ ,k 5. Bài 20. Cho11 điểm nằm trên đường thằng d sao cho khoảng cách giữa 2 điểm bất kì ko lớn hơn 1. Đặt S(m) là tổng khoảng cách từ 1 điểm bất kì đến 10 điểm còn lại. CMR: S(m) 60 lại nhỏ thì người đi bước cuối thua, nếu bằng thì hòa. Xác định kết quả trò chơi.