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

1. Toán Tổ Hợp Bài 1. Xếp 100 bạn học sinh thành hai hàng ngang. Hỏi có bao nhiêu cách chọn ra một số bạn học sinh từ 100 học sinh ban đầu sao cho không có hai bạn nào đứng kề nhau được chọn. Hai bạn đứng kề nhau là hai bạn có số thứ tự liên tiếp trong cùng một hàng hoặc cùng số thứ tự ở hai hàng. Hướng dẫn giải Gọi số học sinh ban đầu là 2n và Un là số cách chọn ra một số bạn xếp thành 2 hàng ngang thỏa mãn yêu cầu bài toán. Ta bỏ đi một bạn học sinh ở đầu của một hàng, còn 2n 1 người . Gọi Vn là số cách chọn ra một số bạn từ 2n 1 người đó thỏa mãn yêu cầu bài toán. (0,5đ) *) Xét số cách chọn từ 2n người 1 3 n 2 4 n Xảy ra các trường hợp sau +TH1: Bạn ở vị trí 1 được chọn. Khi đó bạn ở vị trí 2, 3 không được chọn. Do đó có Vn 1 1 cách chọn ( Thêm 1 cách không chọn ai cả từ 2n 1 bạn) +TH2: Bạn ở vị trí 2 được chọn. Tương tự có Vn 1 1 cách chọn +TH3: Cả 2 bạn ở vị trí 1 và 2 không được chọn. Khi đó có Un 1 cách Vậy ta có Un Un 1 2Vn 1 2 (1) (1đ) *)Xét số cách chọn từ 2n 1 bạn 1 2 n × n Xảy ra các trường hợp sau +Th1: Bạn ở vị trí 1 được chọn.khi đó bạn ở vị trí 2 không được chọn . Vậy có Vn 1 1 cách +Th2: Bạn ở vị trí 1 không được chọn . Có Un 1 cách Vậy ta có Vn Vn 1 1 Un 1 (2) (1đ) Từ (1) và (2) ta tìm được Un 1 2 Un Un 1 2 (0,5đ)
2. n 1 n 1 1 2 1 2 2 Từ đó suy ra U (0,5đ) n 2 Với n 50 ta có số cách chọn thỏa mãn yêu cầu bài toán là 51 51 1 2 1 2 2 U (0,5đ) 50 2 Bài 2. Cho tập X 1,2,3, 2015 , xét tất cả các tập con của X , mỗi tập hợp có 3 phần tử. Trong mỗi tập hợp con ta chọn số bé nhất. Tính trung bình cộng của các số được chọn. Hướng dẫn giải Xét X 1,2,3 n và các tập con gồm r phần tử của X 1 r n . Các tập hợp con của X có phần tử được chọn là 1,2 n – r 1 ( có rất nhiều tập con có chung phần tử bé nhất). Cách cấu tạo các tập hợp như sau: Lấy A  X \ 1 , A có r – 1 phần tử, thì 1 A là tập hợp có r phần tử trong đó số 1 là phần tử bé nhất. Vậy có: (r 1) + C(n 1) tập con có số bé nhất là 1. Tương tự ta có (r 1) + C(n 2) tập con có r phần tử có số bé nhất là 2 r 1 + Cn r 1 tập con có r phần tử có số bé nhất là n – r 1 Suy ra trung bình cộng của số được chọn là 1 r 1 r 1 r 1 r 1Cn 1 2Cn 2 n r 1 Cn r 1 Cn Ta chứng minh: 1 r 1 r 1 r 1 n 1 r 1Cn 1 2Cn 2 n r 1 Cn r 1 Cn r 1 r 1 r 1 r 1 n 1 r r 1 1Cn 1 2Cn 2 n r 1 Cn r 1 Cn Cn 1 r 1
3. r r (r 1) Gọi vế trái của (1) là S . Sử dụng công thức C(m 1) Cm Cm ta được: r r r r r r r S 1(Cn C(n 1) ) 2(C(n 1) C(n 2) ) (n r)(C(r 1) Cr ) (n r 1)Cr Bài 3. Cho n là số nguyên dương. Cho 2n điểm trên phân biệt trên một đường tròn được gán giá trị bởi các số 1,2, ,2n (2 điểm khác nhau được gán giá trị khác nhau) theo một cách nào đó. Mỗi dây cung được nối 2 điểm trong các điểm trên và được gán giá trị bằng độ chênh lệch dương giữa 2 đầu mút. Chứng minh rằng ta có thể chọn được n dây cung đôi một không cắt nhau sao cho tổng giá trị của các dây cung bằng n2 Bổ đề: Trên một được tròn có 2n điểm phân biệt. Người ta tô màu 2n điểm này bằng 1 trong 2 màu màu xanh đỏ sao cho có đúng n điểm được tô màu xanh và đúng n điểm được tô màu đỏ. 2 điểm khác màu nhau bất kì được nối bởi 1 dây cung. Khi đó với mỗi cách tô màu luôn tồn tại n dây cung mà không có 2 dây cung nào cắt nhau. Chứng minh: Ta sẽ chứng minh bổ đề trên bằng quy nạp Dễ thấy bổ đề đúng với n 1. Giả sử bổ đề đúng với mọi n m . Xét n m 1: Do các điểm chỉ được tô bởi 1 trong 2 màu nên phải tồn tại 2 điểm kề nhau mà chúng được tô khác màu. Ta chọn dây cung có 2 đầu mút là 2 điểm này. Theo giả thiết quy nạp tồn tại cách chọn m cung trong số các dây cung có đầu mút là các điểm trong 2m điểm còn lại mà không có 2 dây cung nào cắt nhau. Rõ ràng không có dây cung nào trong m dây cung này cắt dây cung vừa chọn phía trên. Như vậy tồn tại cách chọn m 1 dây cung mà không có 2 dây cung nào cắt nhau, Bổ đề được chứng minh Trở lại bài toán: Ta tô các điểm có giá trị là 1,2,,n bằng màu đỏ, các điểm n 1,,2n bằng màu xanh. Khi đó theo bổ đề tồn tại cách chọn n dây cung mà mỗi dây cung có 2 đầu mút được tô bởi 2 màu khác nhau và chúng đôi một không cắt nhau. Tổng giá trị của các dây cung sẽ bằng: (n 1) (n 2) ? 2n 1 2 n n n2 (ĐPCM) Bài 4. Cho số nguyên dương n 3 . Chứng minh rằng tập hợp X 1; 2; 3; ; n2 n có thể chia thành hai tập con không giao nhau sao cho a a không tập nào trong chúng chứa n phần tử a ,a , ,a với a a a và a k 1 k 1 với mọi 1 2 n 1 2 n k 2 k 2; 3; , n 1. 2 2 2 2 2 2 Đặt Sk k k 1; k k 2; ;k ; Tk k 1; k 2; ;k k n 1 n 1 S  Sk ; T  Tk . Ta chứng minh S, T là các tập con cần tìm của X k 1 k 1 Dễ dàng thấy S T  và S T X
4. a a Ta chứng minh phản chứng. Giả sử S gồm các phần tử a ,a , ,a với a a a và a k 1 k 1 1 2 n 1 2 n k 2 với mọi k 2; 3; , n 1. Khi đó ta có ak ak 1 ak 1 ak , với mọi k 2; 3; , n 1 (1) Nếu a1 Si ., ta có i n 1 do Sn 1 n . Suy ra tồn tại ít nhất n Si n i phần tử thuộc a1; a2 ; ; an Si 1  Si 2   Sn 1 . Áp dụng nguyên lý Dirichlet, tồn tại ít nhất một tập S j , i j n chứa ít nhất 2 phần tử trong số các phần tử a1,a2 , ,an . Tức là tồn tại ak sao cho ak , ak 1 S j và ak 1 S1  S2   S j 1 . Khi đó ta có ak 1 ak S j 1 j 1; ak ak 1 Tj 1 1 j Suy ra ak 1 ak ak ak 1 . Điều này, mâu thuẫn với (1) a a Vậy S không chứa các phần tử a ,a , ,a với a a a và a k 1 k 1 với mọi k 2; 3; , n 1 1 2 n 1 2 n k 2 . Chứng minh tương tự ta cũng có tập T không chứa các phần tử a1,a2 , ,an với a1 a2 an và a a a k 1 k 1 với mọi k 2; 3; , n 1. k 2 Vậy S, T là các tập con cần tìm của X . Bài 5. Trong mặt phẳng cho 2n 1 (n ¥ * ) đường thẳng phân biệt sao cho không có hai đường nào song song hoặc vuông góc và không có ba đường nào đồng quy. Chúng cắt nhau tạo thành các tam giác. Chứng n n 1 2n 1 minh rằng số các tam giác nhọn tạo thành không vượt quá . 6 n n 1 2n 1 Gọi số tam giác tạo thành là f n . Ta phải chứng minh f n 1 ,n ¥ * 6 Với ba đường thẳng bất kỳ trong số các đường thẳng đã cho luôn cắt nhau tạo thành một tam giác hoặc nhọn hoặc tù. Gọi g n là số các tam giác tù. Ta gọi một tam giác tạo bởi ba đường thẳng a,b,c nào đó là: "giả nhọn cạnh a " nếu các góc chung cạnh a của tam giác đó là các góc nhọn. Chọn một đường thẳng d nào đó và coi nó là trục hoành, các đường thẳng còn lại được chia làm hai tập: Tập T là các đường thẳng với hệ số góc dương, Tập T là tập các đường thẳng với hệ số góc âm. Hai đường thẳng tạo với d một tam giác "giả nhọn" nếu một đường thẳng thuộc tập T và một đường thẳng thuộc tập T .
5. Gọi p là số đường thẳng thuộc T và q là số các đường thẳng thuộc tập T . Khi đó p q 2n và số tam p q 2 giác "giả nhọn cạnh d " là pq . Ta có pq n 2 Nhưng do d có thể là đường thẳng bất kỳ trong số 2n 1 đường thẳng đã cho nên ta có số cặp (đường thẳng d ; tam giác "giả nhọn cạnh d") sẽ nhỏ hơn hoặc bằng n2 2n 1 . Trong cách tính trên mỗi tam giác nhọn được tính 3 lần (theo 3 cạnh) còn mỗi tam giác tù được tính 1 lần nên 3 f n g n n2 2n 1 (1) Thế nhưng tổng số các tam giác là: 2n 1 2n 2n 1 C3 f n g n (2) 2n 1 6 Từ (1) và (2) suy ra (2n 1)2n 2n 1 n(n 1)(2n 1) 2 f n n2 2n 1 f n g n n2 (2n 1) 6 3 n n 1 2n 1 hay f n 6 Bài 6. Tìm tất cả các số tự nhiên n sao cho trong mặt phẳng tồn tại n đường thẳng mà mổi đường thẳng cắt đúng 2014 đường khác Xét n đường trong mặt phẳng, mà mổi đường thẳng cắt đúng 2014 đường khác Nếu a là một đường thẳng trong n đường và có đúng k đường song song với nó 0 k n . Cho b là đường thẳng bất kỳ cắt a, khi đó b cắt tất cả các đường không song song với a và b với số giao điểm bằng số giao điểm của a với các đường thẳng đó đồng thời b cắt các đường thẳng song song với a mà mổi đường thẳng cắt đúng 2014 đường khác Suy ra có đúng k đường song song với b. Vậy n đường được chia thành S nhóm, mổi nhóm gồm k 1 đường thẳng song song với nhau => Số giao điểm của mỗi đường với các đường khác là k 1 (S 1) 2014
6. Mà 2014 = 2.19.53 và k 1 là ước nguyên dương của 2014 k 1 1; 2; 19; 53; 38; 106; 1007; 2014 n k 1 S 2014 k 1 => n {2015; 2016; 2033; 2067; 2120; 2510; 3021; 4028} Bài 7. Trên bàn cờ 10 x 10 người ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ ba. Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các số lớn thứ ba được chọn. Sắp xếp thứ tự của 10 số lớn thứ ba của các hàng là a1 a2 a10. Ta thấy tối đa là 20 số có thể lớn hơn a1 (là các số lớn thứ nhất và thứ hai ở mỗi hàng). Vì vậy a1 80. Tương tự có tối đa 28 số có thể lớn hơn a2 . Vì vậy a2 72. Từ đó a1 a2 a10 80 72 a10 7 a10 6 a10 8a10 180. Trong khi đó, tổng các số ở hàng chứa a10 không lớn hơn 100 99 a10 a10 1 a10 7 8a10 171. Do 8a10 171 8a10 180 nên hàng chứa a10 là hàng thỏa mãn yêu cầu. Bài 8. Cho tập hợp X có 2016 phần tử. Chọn ra 64 tập con X1 , X 2 , , X 64 của tập X (mỗi tập con đều chứa nhiều hơn 1008 phần tử). Chứng minh tồn tại tập con A của X có số phần tử không vượt quá 6 mà A X i  , với i 1,64 . (Chuyên Thái Bình) Lời giải Tổng số phần tử trong 64 tập con lớn hơn 64.1008 32.2016 . Vì vậy tồn tại một phần tử a của tập X thuộc ít nhất 33 tập con, giả sử là X1, X2, , X33. Xét 31 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử b của tập X thuộc ít nhất 16 tập con, giả sử là X34, X35, , X49. Xét 15 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử c của tập X thuộc ít nhất 8 tập con, giả sử là X50, X51, , X57. Xét 7 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử d của tập X thuộc ít nhất 4 tập con, giả sử là X58, X59, X60, X61. Xét 3 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử e của tập X thuộc ít nhất 2 tập con, giả sử là X62, X63.
7. Với tập X64 còn lại ta lấy một phần tử f. Như vậy tập con A chứa các phần tử a, b, c, d, e, f thỏa mãn bài toán. Suy ra đpcm. Bài 9. Những ô của hình vuông kích thước 7 7 được tô bằng hai màu. Chứng minh rằng tồn tại ít nhất 21 hình chữ nhật với đỉnh cùng màu và các cạnh song song với các cạnh của hình vuông. Giải: Ta cho màu được tô là trắng và đen. Lấy một hàng bất kỳ, ta giả sử tồn tại k ô đen và 7 – k ô trắng. Khi đó 2 2 2 tồn tại Ck C7 k k 7k 21 9 Cặp ô cùng màu. Vậy tồn tại ít nhất 7.9 = 63 cặp ô cùng màu trên cùng hàng. 2 Tiếp theo tồn tại C7 21 cặp cột. Suy ra tồn tại 21.2 = 42 tổ hợp của màu và cặp cột. Với tổ hợp i 1;24 , giả sử tồn tại ji cặp trong cùng một tổ hợp, thì tồn tại ít nhất 42 ji – 1 hình chữ nhật cho tổ hợp này. Vì tổng của ji ít nhất là 63 nên tồn tại ít nhất ( ji 1) 63 42 21 i 1 Vậy tồn tại ít nhất 21 hình chữ nhật thỏa mãn yêu cầu của bài toán. Bài 10. Cho tập hợp A 1;2; ;2013. Cần phải loại khỏi A ít nhất bao nhiêu phần tử để tập hợp còn lại có tính chất: Không phần tử nào bằng tích của hai phần tử khác. Lời giải Loại khỏi A tập hợp {2;3; ;44}, tập này có 43 phần tử. Khi đó tập còn lại là {1;45;46; ;2012;2013}. Rõ ràng tập này thỏa mãn yêu cầu: Không có phần tử nào là tích của hai phần tử khác. 1.0 đ Ta sẽ chứng minh mọi cách tách khỏi A một tập hợp có nhiều nhất 42 phần tử đều không thỏa mãn yêu cầu đề bài. 0.5 đ Thật vậy xét các bộ ba sau (43 bộ ba): 2, 87, 2.87 3, 86, 3.86 4, 85, 4.85 44, 45, 44.45
8. Xét hàm số f (x) x(89 x) với 2 x 44 . Ta có f '(x) 89 2x 0,2 x 44 . Vậy f là hàm đồng biến khi 2 x 44 . Suy ra f (2) f (3) f (44) 2.87 3.86 44.45. Dễ thấy 2 3 44 45 46 87 2.87 3.86 44.45 . Vì 44.45 1980 2013 nên toàn bộ các phần tử của 43 bộ ba đều là khác nhau và đều nằm trong tập hợp A . Vì ta tách ra khỏi A tối đa 42 phần tử, nên phần còn lại của A (sau khi tách) phải có ít nhất một bộ ba nói trên. Vậy mọi cách tách như thế không thỏa mãn yêu cầu đầu bài. 2.0 đ Kết luận: Số phần tử ít nhất cần tách khỏi A là 43 phần tử. 0.5 đ Bài 11. Trên bảng ô vuông cố định có kích thước 3 3 người ta xếp một số viên sỏi sao cho mỗi ô vuông có nhiều nhất một viên sỏi. Mỗi cách xếp sỏi được tính điểm như sau, nếu tổng số sỏi trên một hàng (hoặc trên một cột hoặc trên một trong hai đường chéo) là một số lẻ thì được tính 1 điểm. Bảng không có sỏi ứng với 0 điểm, bảng xếp kín 9 viên sỏi ứng với 8 điểm. a) Tồn tại hay không cách xếp 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 xếp đó là 8. b) Chứng minh rằng số cách xếp sỏi với điểm số là một số chẵn bằng số cách xếp sỏi với điểm số là một số lẻ. Giải a) Giả sử ô chính giữa không có sỏi và điểm số của cách xếp 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. a b c a b c 0 d d' 0 d c' b' a ’ 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ác xếp sỏi thỏa mãn điều kiện bài toán. b) Ta gọi hai cách xếp 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 e d g h i g h i (B) (B’) Như vậy, các cách xếp sỏi chia thành từng cặp đôi một liên hợp với nhau.
9. Xét hai cách xếp 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ủa 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 xếp liên hợp với nhau, một cách xếp có điểm số chẵn, cách xếp còn lại cố điểm số là một số lẻ suy ra điều phải chứng minh. Bài 12. Cho một hình phẳng có diện tích bằng 1 được phủ kín bởi hữu hạn các hình tròn. Chứng minh rằng 1 trong số các đường tròn đó có thể chọn được 1 hình tròn có diện tích không bé hơn hoặc chọn được 1 số 9 1 hình tròn đôi một rời nhau có tổng diện tích không bé hơn . 9 Kí hiệu: O; R – đường tròn tâm O bán kính R . dtF – diện tích hình phẳng F. Do số các đường tròn là hữu hạn nên luôn chọn được hình tròn có bán kính lớn nhất. Gọi đường tròn đó là O1; R1 . Gọi F1 là hình phẳng tạo bởi O1; R1 và các hình tròn có điểm chung với hình tròn O1; R1 . Dễ thấy, tất cả các hình tròn tạo nên F1 đều nằm trong hình tròn O1;3R1 . dtF Do đó: dtF dt O ;3R 9dt O ; R dt O ; R 1 1 1 1 1 1 1 1 1 9 Trường hợp 1: O1; R1 có điểm chung với tất cả các hình tròn còn lại. 1 Do các hình tròn phủ kín hình phẳng có diện tích bằng 1 nên dtF 1 . Từ (1) ta được dt O ; R 1 1 1 9 (đpcm) Trường hợp 2: Tồn tại hình tròn không có điểm chung với O1; R1 . Do số các đường tròn là hữu hạn nên ta có thể chọn được trong số các hình tròn đó k (k ≥1) các hình tròn O2 ; R2 ; O3; R3 ; ; Ok 1; Rk 1 thỏa mãn 2 điều kiện: a) Với mỗi i 2, 3, ,k 1 thì Oi ; Ri là hình tròn có bán kính lớn nhất không có điểm chung với các hình tròn O1; R1 ; , Oi 1; Ri 1 đã chọn trước đó. b) Không tồn tại hình tròn không có điểm chung với ít nhất 1 đường tròn trong các đường tròn O1; R1 ; O2 ; R2 ; ; Ok 1; Rk 1 Với mỗi i 2, , k 1 gọi Fi là hình phẳng tạo bởi Oi ; Ri và các hình tròn có điểm chung với hình tròn Oi ; Ri . Do a) nên tất cả các hình tròn tạo nên Fi đều nằm trong hình tròn Oi ;3Ri . dtF Do đó: dtF dt O ;3R 9dt O ; R dt O ; R i 2 i i i i i i i 9
10. Từ b) do các hình tròn phủ kín hình phẳng có diện tích bằng 1 nên: dtF1 dtF2 dtFk 1 1 (3). 1 Từ (1), (2) và (3) suy ra dt O ; R dt O ; R . 1 1 k 1 K 1 9 Theo các xác định các hình tròn thì O1; R1 ; O2 ; R2 ; ; Ok 1; Rk 1 rời nhau (đpcm). Bài 13. Cho 2015 điểm trên đường thẳng, tô các điểm bằng một trong 3 màu xanh, đỏ, vàng (mỗi điểm chỉ tô một màu). Có bao nhiêu cách tô khác nhau sao cho không có 3 điểm liên tiếp nào cùng màu. Giải Gọi Sn là số cách tô màu thỏa mãn cho n điểm (bài toán của ta là n 2015 ). Ta sẽ tính theo n , xét hai điểm cuối cùng của có hai trường hợp xảy ra: +Nếu hai điểm cuối cùng màu thế thì điểm thứ n 1 khác màu 2 điểm cuối. +Nếu hai điểm cuối khác màu thì điểm thứ n 1 tô bất kì. Từ đó sinh ra hai số đặc trưng là số cách tô n điểm mà hai điểm cuối cùng màu, là số cách tô màu n điểm mà hai điểm cuối khác màu và cả hai cùng thỏa mãn 3 điểm liên tiếp khác màu. Ta có: Sn 1 2M n 3Pn , Pn 1 2Sn ;M n 1 Pn . Thế thì Sn 1 2Pn 1 6Sn 1 4Sn 2 6Sn 1 . Vậy ta có hệ thức truy hồi: Sn 1 6Sn 1 4Sn 2 0 . Bây giờ ta 2 tính S3 , S4 thấy ngay S3 27 3 24 , S4 4! 3 12 49 . Phương trình đặc trưng X 6X 4 0 có nghiệm là:. n n Công thức xác định Sn ax1 bx2 với a,b thỏa mãn: 24 13 23 a a(3 13)3 b(3 13)3 24 2 13(3 13)3 a(3 13)4 b(3 13)4 49 24 13 23 b 3 2 13(3 13) Sau đó cho n 2015 ta được kết quả bài toán. Bài 14. Gọi a1a2 an với ai 2;0 là một xâu có độ dài n . Gọi xâu 20 là xâu OLIMPIC nếu 2 và 0 là hai phần tử liên tiếp theo thứ tự đó ở trong xâu có độ dài n đã cho ( ví dụ như xâu 2220022 có độ dài là 7 và trong đó có 1 xâu OLIMPIC). Xét các xâu có độ dài 30 và chứa k 9 xâu OLIMPIC, biết rằng có C31 xâu như thế. Tìm k ? Giải Gọi H là số là xâu chứa toàn là số 2 có độ dài lớn hơn hay bằng 1
11. Gọi K là số là xâu chứa toàn là số 0 có độ dài lớn hơn hay bằng 1. Ta có các trường hợp sau: Trường hợp 1. HKHKHK HK (*) ( có k xâu loại H, k xâu loại K) Trường hợp 2. HKHKHK HKH ( có k+ 1 xâu loại H, k xâu loại K) Trường hợp 3. KHKHK KHK ( có k xâu loại H, k+1 xâu loại K) Trường hợp 4. KHKHK KHKH( có k+1 xâu loại H, k+1 xâu loại K) Xét trường hợp 1. Gọi x1 là số phần tử ở xâu H ( H ở vị trí đầu tiên trong (*)) , x1 1 Gọi x2 là số phần tử ở xâu K ( K ở vị trí thứ hai trong (*)) , x2 1. Gọi x2k là số phần tử ở xâu K ( K ở vị trí cuối trong (*)) , x2k 1 Ta có : x1 x2 x2k 30 . 2k 1 Theo bài toán chia kẹo Euler : Số xâu có độ dài 30 và chứa k xâu OLIMPIC trong trường hợp 1 là C29 . Tương tự như vậy ta có các trường hợp còn lại và kết hợp với quy tắc cộng ta có : 2k 1 2k 2k 2k 1 9 C29 C29 C29 C29 C31 2k 1 9 9 2k 1 C31 C31 k 4 9 31 (2k 1) Vậy k 4 . Bài 15. Cho số nguyên n 1. Tìm số lớn nhất các cặp gồm 2 phần tử phân biệt của tập 1;2; ;n sao cho tổng của các cặp khác nhau là các số nguyên khác nhau và không vượt quá n . Giải Giả sử có k cặp thỏa mãn đề bài. Gọi S là tổng của k cặp đó, thì S 1 2 2k k(2k 1) k(k 1) Dễ thấy S n (n 1) (n k 1) nk . Do đó, 2 k(k 1) 2n 1 k(2k 1) nk k 2 5 2n 1 Bây giờ ta xây dựng cặp thỏa mãn đề bài như sau 5
12. 2n 1 Trường hợp 1: Số n có dạng 5k 1 hoặc 5k 2. Khi ấy, 2k . Ta xét các cặp sau 5 (4k 1;k), (4k;k 1), (3k 2;1), (3k;2k), (3k 1;2k 1), (2k 1;k 1) Rõ ràng dãy trên có 2k cặp thỏa mãn đề bài. 2n 1 Trường hợp 2: Số n có dạng 5k 3 hoặc 5k 4 hoặc 5k 5 . Khi ấy, 2k 1. Ta xét các cặp sau 5 (4k 2;k 1), (4k 1;k), ,(3k 2;1),(3k 1;2k 1),(3k;2k), ,(2k 1;k 1) Dãy trên có 2k 1 thỏa mãn đề bài. 2n 1 Vậy số lớn nhất các cặp thỏa mãn đề bài là 5 Có n n 4 cặp vợ chồng tham dự buổi dạ tiệc. Biết rằng mỗi người đều có thể trò chuyện với tất cả những người khác, trừ vợ hoặc chồng mình. Các cuộc trò chuyện lập thành các nhóm người C1, C2 , , Ck với tính chất sau: Không có một cặp vợ chồng nào nói chuyện trong cùng một nhóm và hai người bất kì không phải vợ chồng thì đều có đúng một nhóm để họ trò chuyện.Chứng minh rằng: k 2n . *) Gọi gi i 1,2,,2n là số nhóm mà người thứ i tham gia trò chuyện. Do người thứ i nói chuyện với ít nhất một cặp vợ chồng (A,B) và tồn tại hai nhóm khác nhau chứa A và chứa B nên ta có gi 2 i 1,2,,2n . *) Trường hợp 1 : Tồn tại i sao cho gi 2 . Giả sử Cm Ch i . Khi đó mỗi cặp vợ chồng không phải vợ chồng của i có một người tham gia vào nhóm Cm và người kia tham gia vào nhómCh . Khi đó mỗi người của nhóm Cm \ i sẽ nói chuyện vói người không phải bạn đời của mình trong nhóm Ch \ i . Do các nhóm này phân biệt nên có tất cả n 1 n 2 nhóm như vậy. Do đó: k n 1 n 2 2 2n với n 4 . *) Trường hợp 2: gi 3 với mọi i 1,2,,2n Khi đó ta gán cho người thứ i biến số xi . Xét hệ phương trình 2n ẩn:  xi 0 ;t 1,2,,k . (*) i Ct Giả sử k 2n . Khi đó hệ trên có số phương trình ít hơn số ẩn nên tồn tại i sao cho xi khác 0.
13. * Đặt yt  xi ; M { i, j với i, j là vợ chồng}; M = {(i,j) với i,j khônglà vợ chồng} i Ct Khi đó: 2 k k 2n 2 2  yt   xi  gi xi 2  xi x j * t 1 t 1 i Ct i 1 (i, j) M 2n 2n 2 2 (gi 1)xi  xi 2 xi x j 2  xi x j i 1 i 1 i j (i, j) M 2n 2n 2 2 (gi 1)xi  xi 2  xi x j i 1 i 1 (i, j) M 2n 2n 2 2 2 (gi 2)xi  xi  (xi x j ) i 1 i 1 (i, j) M k 2 Vậy ,  yt 0 xi 0;i 1,2, ,2n t 1 Hay, yt 0,t 1,2, ,k xi 0;i 1,2, ,2n Vậy hệ (*) có nghiệm xi 0;i 1,2, ,2n ( vô lý) Nên k 2n . Bài 16. Tập hợp M gồm hữu hạn điểm trên mặt phẳng sao cho với mọi điểm X thuộc M tồn tại đúng 4 điểm thuộc M có khoảng cách đến X bằng 1. Hỏi tập hợp M có thể chứa ít nhất là bao nhiêu phần tử? Giải +) Rõ ràng có ít nhất hai điểm P,Q thuộc M sao cho PQ 1 . Ký hiệu : M P {X M / PX 1}. Từ giả thiết M P 4 ta có:| M p  M q | 2 . Nếu tồn tại P, Q sao cho | M p  M q | 1 thì M chứa ít nhất 9 điểm. +(1.50 đ) Trường hợp với mọi P,Q sao cho PQ 1và | M p  M q | 2 . Khi đó M p  M q R, S , lúc đó M P R, S,T,U và M q R, S,V ,W và giả sử M P,Q, R, S,T,U,V ,W ta cóTQ 1, UQ 1, VP 1, WP 1. • Nếu TR,TS,UR,US khác 1: suy ra M t  Mq M u  M q V ,W suy ra T hay U trùng với Q , vô lý. • Nếu TR,TS,UR,US có một số bằng 1: Không giảm đi tính tổng quát, giả sử TV 1 lúc đó TS 1 và TV 1 hay TW = 1. Giả sử TV 1 lúc đó TW 1 suy raTU 1, và
14. M t P, R,U,V và M u P,T,V ,W lúc đó UTV , RPT,UTV là các tam giác đều cạnh 1, ta có hình 1. Điều này mâu thuẫn vìVR 2 . +(0.50 đ) Vậy M chứa ít nhất là 9 điểm. Dấu bằng xảy ra với hình2. Vậy M có thể chứa ít nhất là 9 điểm. A5 A9 A6 V T R A1 A2 A3 A7 U P A8 A4 Bài 17. Tìm số nhỏ nhất trong các cặp tập hợp có giao khác tập  trong 2000 tập hợp phân biệt sao cho với 3 tập hợp bất kì trong 2000 tập hợp đó đều có ít nhất một cặp tập hợp có giao khác tập . • Giải tổng quát đối với n tập hợp ( trong bài n 2000 ). Ta có hình biểu diễn (K) của n tập hợp như sau: n tập hợp được biểu diễn bởi n điểm phân biệt trong mặt phẳng ( không có 3 điểm nào thẳng hàng), hai tập hợp có giao khác  biểu diễn bởi 1 đường liền nét( __ ) nối với hai điểm biểu diễn, hai tập hợp có giao bằng  biểu diễn 1 đường không liền nét ( ) nối hai điểm biểu diễn. Kí hiệu P là tập hợp n điểm, k n là số đoạn nối liền nét của một biểu diễn (K) thỏa giả thiết bài toán ( tức là: với 3 điểm bất kỳ của P có ít nhất một đoạn liền nét). Bài toán trở thành tìm giá trị nhỏ nhất d n của k n . M A Q B C N P • Ta luôn luôn có thể giả thiết rằng : Trong biểu diễn (K) tồn tại hai điểm A, B mà đoạn nối AB là không liền nét. Đặt Q P \ A, B , như vậy, Q có n 2 điểm, trong biểu diễn (K) ta bỏ đi đoạn AB và tất cả các đoạn nối với A, nối với B và ta được biểu diễn (K*) của tập Q thỏa điều kiện bài toán. Gọi k(n-2) là số các đoạn liền nét trong biểu diễn (K*). • Lấy C Q, suy ra các đoạn CA, CB phải có ít nhất một đoạn liền nét (vì đoạn AB không liền nét). Vì Q có n 2 điểm, nên suy ra : k n n 2 k n 2 (*). • Công thức truy hồi (*) cho ta : k n n 2 n 4 4 k 4 vì n chẵn.
15. n n 2 • Suy ra k n n 2 n 4 4 d 4 n 2 n 4 4 2 4 (dod 4 2 ). n n 2 Chứng tỏ : Tồn tại d n . 4 n n 2 n • Chọn n tập hợp để có d n như sau : Nhóm X gồm tập hợp giao nhau khác  từng đôi 4 2 n một, nhóm Y gồm tập hợp giao nhau khác  từng đôi một. Mỗi tập hợp của nhóm này thì không có giao 2 khác  với bất kỳ một tập hợp của nhóm kia. Cách chọn trên thỏa giả thiết bài toán. n n n n n(n 2) •Số đoạn nối liền nét giữa điểm của X là : ( -1) + ( -2) + ( -3) + + 1 = 2 2 2 2 8 n(n 2) •Số đoạn nối liền nét giữa n điểm của X và Y là : . 4 n(n 2) 20001998 •Vậy d n . Thế n = 2000 ta được số cần tìm là: 999000 . 4 4