Chuyên đề Các bài Toán về tổ hợp suy luận năm 2019 - Nguyễn Công Lợi

Nội dung tài liệu: Chuyên đề Các bài Toán về tổ hợp suy luận năm 2019 - Nguyễn Công Lợi

1.  Nguyễn Công Lợi CHUYÊN ĐỀ CÁC BÀI TOÁN VỀ TỔ HỢP VÀ SUY LUẬN Nghệ An, tháng 9 năm 2019
2. 1 CHUYÊN ĐỀ TỔ HỢP VÀ SUY LUẬN LỜI NÓI ĐẦU Nhằm đáp ứng nhu cầu về của giáo viên toán THCS và học sinh về các chuyên đề toán THCS, website tailieumontoan.com giới thiệu đến thầy cô và các em chuyên đề về các bài toán tổ hợp và suy luận. Chúng tôi đã kham khảo qua nhiều tài liệu để viết chuyên đề này nhằm đáp ứng nhu cầu về tài liệu hay và cập nhật được các dạng toán mới về toán tổ hợp và suy luận thường được ra trong các kì thi gần đây. Chuyên đề này gôm các chủ đề toán sau: - Chủ đề 1: Các dạng toán về nguyên lý Dirichlet - Chủ đề 2: Các bài toán về ứng dụng nguyên lý cực hạn - Chủ đề 3: Các bài toán về đại lượng bất biến và ứng dụng - Chủ đề 4: Một số bài toán tổ hợp suy luận tổng hợp Các vị phụ huynh và các thầy cô dạy toán có thể dùng có thể dùng chuyên đề toán tổ hợp và suy luận để giúp con em mình học tập. Hy vọng chuyên đề này sẽ có thể giúp ích nhiều cho học sinh phát huy nội lực giải toán nói riêng và học toán nói chung. Mặc dù đã có sự đầu tư lớn về thời gian, trí tuệ song không thể tránh khỏi những hạn chế, sai sót. Mong được sự góp ý của các thầy, cô giáo và các em học! Chúc các thầy, cô giáo và các em học sinh thu được kết quả cao nhất từ chuyên đề này! Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
3. 2 MỘT SỐ BÀI TOÁN TỔ HỢP Chủ đề 1 CÁC BÀI TOÁN ỨNG DỤNG NGUYÊN LÝ DIRICHLET I. Nguyên lí Dirichlet. Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật v|o ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp. Nguyên lý Dirichlet cơ bản: Nếu nhốt n1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ. Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp N chứa ít nhất đồ vật. (Ở đ}y x là số nguyên nhỏ nhất có giá trị nhỏ hơn hoặc bằng x) k Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m2 cái chuồng thì tồn tại một n m 1 chuồng có ít nhất con thỏ. m Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc n|o đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A m| chúng tương ứng với một phần tử của B. II. Phương pháp ứng dụng. Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó l| một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau: Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt ‚thỏ‛ v|o ‚chuồng‛ v| thoả mãn c{c điều kiện: + Số ‘thỏ‛ phải nhiều hơn số chuồng. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
4. 3 + ‚Thỏ‛ phải được nhốt hết vào các ‚chuồng‛, nhưng không bắt buộc chuồng nào cũng phải có thỏ. Thường thì phương ph{p Dirichlet được áp dụng kèm theo phương ph{p phản chứng. Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. III. Một số ví dụ minh họa. Ví dụ 1. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị. Điền v|o mỗi ô vuông của bảng n|y một số nguyên dương không vượt qu{ 10 sao cho hai số ở hai ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh rằng trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần. Lời giải Xét hình vuông cạnh 2x2 , do hình vuông n|y có mỗi hình vuông nhỏ luôn chung cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia th|nh 25 hình vuông có cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3. Từ 1 đến 0 có 3 số lẻ không chia hết cho 3 là 1, 5, 7. Áp dụng nguyên lí Dirichlet ta được một trong ba số trên xuất hiện ít 50 nhất 1 17 lần 3 Ví dụ 2. Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng. Chứng minh rằng với c{ch sơn m|u bất kì thì trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu. Lời giải Mẫu sơn m|u có thể xảy ra với bàn cờ này có dạng từ 1 đến 8. Giả sử một trong số các cột thuộc dạng 1. Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1, 2, 3 hoặc 4. Giả sử tất cả các cột còn lại thuộc dạng 5, 6, 7, 8 khi đó theo nguyên lí Dirichlet thì hai trong số sau cột có 2 cột cùng 1 dạng v| như vậy b|i to{n cũng được chứng minh Chứng minh ho|n to|n tương tự nếu 1 cột có dang 8. Giả sử không có cột nào trong các cột 1, 8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng v| b|i to{n cũng đựoc chứng minh Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
5. 4 Ví dụ 3. Trong hình chữ nhật kích thước 1.2 ta lấy 6n2 1 điểm với n là số nguyên dương. Chứng 1 minh rằng tồn tại 1 hình tròn có bán kính chứa không ít hơn 4 trong số c{c điểm đã cho. n Lời giải Chia các cạnh của hình chữ nhật th|nh n đoạn v| 2n đoạn bằng nhau ,mỗi đoạn có độ dài 1 . Nối c{c điểm chia bằng c{c đường thẳng song songvới các cạnh của hình chữ nhật ta được n 1 n.2n 2n 2 hình vuông nhỏ với cạnh là . Nếu mỗi hình vuông chứa không qu{ 3 điểm thì tổng n số điểm đã cho không qu{ 3.2n22 6n (trái với giả thiết). Do đó phải tồn tại 1 hình vuông chứa 1 2 không ít hơn 4 điểm. Rõ ràng hình vuông cạnh nội tiếp đường tròn bán kính là v| đường n 2n 1 tròn n|y được chứa trong đường tròn đồng tâm bán kính . n Ví dụ 4. Cho bảng vuông gồm n.n ô vuông. Mỗi ô vuông ghi một trong các số 1; 0; 2. Chứng minh rằng không tìm được bảng vuông nào mà tổng các số trên cột, trên h|ng, trên đường chéo là các số khác nhau. Lời giải Do trong các ô có thể nhận một trong ba số 0; 1; 2 nên có thể có trường hợp tất cả các ô của một hàng hoặc một cột hoặc một đường chéo nhận giá trị 0 hoặc nhận giá trị 2. Do đó tổng các số trên cột hoặc trên hàng hoặc trên đường chéo có giá trị nhỏ nhất là 0.n 0 và giá trị lớn nhất là 2.n 2n . Như vậy các tổng các số trên mỗi hàng, mỗi cột, mỗi đường chéo có thể nhận 2n 1 giá trị là 0;1;2;...;2n Do bảng ô vuông n.n nên sẽ có n hàng, n cột v| hai đường chéo. Do đó sẽ có 2n 2 tổng nhận một trong 2n 1 giá trị số nguyên từ 0 đến 2n. Theo nguyên tắc Dirichlet phải có ít nhất 2 tổng có giá trị bằng nhau. Điều n|y có nghĩa l| không tìm được bảng vuông nào mà tổng các số trên cột, trên h|ng, trên đường chéo là các số khác nhau. Ví dụ 5. Ở vòng chung kết cờ vua có 8 bạn tham gia. Hai bạn bất kỳ đều phải đấu với nhau một trận v| người n|o cũng phải gặp đủ 7 đấu thủ của mình. Chứng minh rằng trong mọi thời điểm của cuộc đấu, bao giờ cũng có hai đấu thủ đã đấu một số trận như nhau. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
6. 5 Lời giải Giả sử số trận thi đấu của các bạn tham gia thi đấu cờ vua là a1 ;a 2 ;...;a 8 . Do hai bạn thi đấu với nhau một trận nên ta có 0 ai 7,  1 i 8 . Xét c{c trường hợp sau: Tính đến thời điểm đó có một bạn chưa đấu trận nào suy ra không có bạn n|o đấu đủ 7 trận. Khi đó 0 ai 6,  1 i 8 do đó tồn tại aakm có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau. Tính đến thời điểm đang xét, mỗi bạn đều đã đấu ít nhất một ván. Khi đó ta có 0 ai 7,  1 i 8 , do đó tồn tại aakm có nghĩa l| có hai đấu thủ đã đấu một số trận như nhau. Vậy b|i to{n được chứng minh. Ví dụ 6. Cho 40 số nguyên dương a1 ,a 2 ,...,a 19 và b1 ,b 2 ,...,b 21 thoả mãn hai điều kiện: 1 a1 a 2 ... a 19 200 và 1 b1 b 2 ... b21 200 Chứng minh rằng tồn tại bốn số ai ;a j ;b k ;b p với 1 i,j 19;1 k,p 21 thỏa mãn ai a j ; b k b p a a b b j i p k Lời giải Xét các tổng có dạng abmn với am a1 ;a 2 ;...;a 19  và bn b1 ; b 2 ;...; b 21  . Do tập hợp a1 ;a2 ;...;a 19  có 19 phần tử và tập hợp b1 ; b2 ;...; b 21  có 21 phần tử nên, nên ta có tất cả 19.21 399 tổng dạng abmn như thế. Chú ý rằng 1 a1 a 2 ... a 19 200 và 1 b1 b 2 ... b21 200 nên 2 amn b 400 . Nên các tổng abmn nhận các giá trị nguyên dương từ 2 đến 400. Đến đ}y ta xét c{c trường hợp sau: Nếu các tổng trên nhận đủ 399 giá trị từ 2 đến 400. Khi đó từ giả thiết cảu b|i to{n ta được Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
7. 6 a b 2 a b 1 1 1 1 1 a19 b 21 400 a19 b 21 200 a a ; b b Từ đó ta suy ra được 1 19 1 21 a19 a 1 b 21 b 1 199 Nếu các tổng trên không nhận đủ 399 giá trị từ 2 đến 400. Khi đó với 399 tổng thì theo nguyên lí Dirichlet sẽ tồn tại hai tổng có giá trị bằng nhau. ai a j ; b k b p Không mất tính tổng quát ta giả sử hai tổng đó l| a b b a j k p i ai a j ; b k b p Từ đó suy ra a a b b j i p k Vậy b|i to{n được chứng minh. Ví dụ 7. Trong một cuộc tranh giải vô địch quốc gia về bóng đ{ có 20 đội tham gia. Số nhỏ nhất các trận đấu l| bao nhiêu để trong 3 đội bất kỳ luôn tìm được 2 đội đã chơi với nhau. Lời giải Ta chia 20 đội thành 2 nhóm, mỗi nhóm 10 đội và chỉ c{c đội trong cùng1 nhóm mới thi đấu với nhau. Rõ ràng cách sắp xếp này thoả mãn c{c điều kiện của bài toán và tất cả có 90 trận đấu. Ta chứng minh rằng nếu c{c điều kiện của bài toán thoả mãn thì số trận đấu sẽ lớn hơn hoặc bằng 90. Giả sử ngược lại ta tìm đội một A đấu số trận k8 . Ta ký hiệu c{c đội đã đấu với A là X. C{c đội không đấu với A l| Y, khi đó X k; Y 19 k . Dĩ nhiên c{c đội trong Y sẽ đấu với nhau nếu không hai đội thuộc Y và A sẽ l| 3 đội m| không có đội n|o chơi với nhau. Giả sử trong X có P cặp không chơi với nhau. Do đó mỗi đội Y phải đấu với mỗi đội trong P cặp đó của X và mỗi đội trong X có mặt không quá k1 cặp trong số P cặp (X có tất cả k đội). Vì vậy giữa c{c đội của X và 19 k 19 k Y đấu số trận bé hơn hoặc bằng . Mặt khác do k8 nên .P P . k1 k1 Như vậy nếu thay các trận của c{c đội trong X đấu với c{c đội trong Y bởi các trận đấu cần thiết sẽ giảm đi. Như vậy số trận đấu cần phải tiến hành là: Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
8. 7 k k 1 19 k 18 k 2 k2 18k 9.19 k 9 90 90 22 Vậy số các trận đấu ít nhất cần phải tiến hành là 90 Ví dụ 8. Chứng minh rằng trong 39 số tự nhiên liên tiếp bất kỳ luôn tồn tại ít nhất một số có tổng các chữ số chia hết cho 11. Lời giải Xét tập hợp 39 số tự nhiên liên tiếp S a1 ;a2 ;...;a 39  , ai 1 a i 1, 1 i 38 Trong tập a1 ;a2 ;...;a 20  luôn tồn tại hai số có tận cùng l| 0 v| hơn kém nhau 10. Do đó trong hai số này tồn tại ít nhất một số có chữ số hàng chục nhỏ hơn 9, kí hiệu số đó l| A Bc00 c 8,c ,B Xét 11 số A;A 1;A 2;...;A 9;A 19 . Nhận xét rằng: + 11 số trên thuộc tập S. + 11 số đó có tổng các chữ số là 11 số tự nhiên liên tiếp vì các tổng đó l|: sA;sA 1;sA 2;...;sA 9;sA 10 ,với sA là tổng các chữ số của A. Trong 11 số tự nhiên liên tiếp luôn tồn tại một số chia hết cho 11. Do vậy, ta có điều phải chứng minh. Ví dụ 9. Cho tập A 1;2;3;...;16  . Hãy tìm số nguyên dương k nhỏ nhất sao cho trong mỗi tập con gồm k phần tử của A đều tồn tại hai số phân biệt a, b mà ab22 là một số nguyên tố. Lời giải Nếu a,b chẵn thì ab22 là hợp số. Do đó nếu tập con X của A có hai phần tử phân biệt a,b mà ab22 là một số nguyên tố thì X không thể chỉ chứa các số chẵn. Suy ra k9 . Ta chứng tỏ k9 là giá trị nhỏ nhất cần tìm. Điều đó có ý nghĩa l| với mọi tập con X gồm 9 phần tử bất kỳ của A luôn tồn tại hai phần tử phân biệt a,b mà ab22 là một số nguyên tố. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
9. 8 Để chứng minh khẳng định trên ta chia tập A thành các cặp hai phần tử phân biệt a,b mà ab22 là một số nguyên tố, ta có tất cả 8 cặp 1;4 , 2;3 , 5;8 , 6;11 , 7;10 , 9;16 , 12;13 , 14;15 . Theo nguyên lý Dirichlet thì 9 phần tử của X có hai phần tử cùng thuộc một cặp v| ta có điều phải chứng minh. Ví dụ 10. Cho 2014 số tự nhiên bất kỳ. Chứng minh rằng trong số các số đó có một số chia hết cho 2014 hoặc có một số số mà tổng của các số ấy chia hết cho 2014. Lời giải Gọi 2014 số tự nhiên đã cho l| a1 ,a 2 , ,a 2014 . Xét dãy S1 a;S 1 2 a 1 a;...;S 2 2014 a 1 a 2 a 2014 Chia tất cả các số hạng của dãy cho 2014 ta có c{c trường hợp sau: Trường hợp 1: Nếu có một số hạng nào của dãy chia hết cho 2014 thì b|i to{n được chứng minh. Trường hợp 2: Nếu không có số hạng nào của dãy chia hết cho 2014 thì vì có tất cả 2014 phép chia mà số dư chỉ gồm 1, 2, ..., 2013 do đó theo nguyên lý Dirichle có ít nhất hai số hạng của dãy có cùng số dư khi chia cho 2014. Gọi hai số hạng đó l| Si và S j . Không mất tính tổng quát, giả sử 1 i j 2014 thì Si a 1 a 2 a i và Sj a 1 a 2 ai aj Lúc đó Sj S i 2014 ai 1 aj 2014 . Từ đó ta có điều phải chứng minh. Ví dụ 11. Chứng minh rằng từ 53 số tự nhiên bất kì luôn chọn được 27 số mà tổng của chúng chia hết cho 27. Lời giải Ta chứng minh từ 5 số tự nhiên bất kì luôn tìm được 3 số mà tổng của chúng chia hết cho 3. Thật vậy, mỗi số tự nhiên khi chia cho 3 thì có phần dư l| 0, 1 hoặc 2 Nếu trong 5 số dư có một số bằng 0, một số bằng 1, một số bằng 2 thì tổng của ba số tự nhiên tương ứng với ba số dư n|y l| chia hết cho 3 Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
10. 9 Nếu 5 số dư chỉ nhận không quá 2 trong 3 số 0, 1, 2 thì theo nguyên tắc Dirichlet thì tồn tại 3 số dư nhận cùng một giá trị và tổng của ba số tự nhiên tương ứng là chia hết cho 3 Từ 53 số tự nhiên đã cho chọn được 3 số mà tổng của chúng là a1 chia hết cho 3. Xét 50 số còn lại chọn được 3 số mà tổng là a2 chia hết cho 3. Lặp lại lập luận này từ 53 số ta chọn được 17 bộ, mỗi bộ gồm 3 số có tổng lần lượt là a1, a2, < a17 sao cho mỗi tổng đều chia hết cho 3. Chứng minh tương tự nhận thấy từ 5 số tự nhiên bất kì mà mỗi số đều chia hết cho 3 ta chọn được 3 số có tổng chia hết cho 9. Vậy từ 17 số ta chọn được 5 bộ mỗi bộ gồm 3 số có tổng lần lượt là b1 , b 2 ,  , b5 sao cho b9i với i 1; 2; 3; 4; 5  Từ 5 số chia hết cho 9 là b1 , b 2 ,  , b5 chọn được 3 số mà tổng của chúng là chia hết cho 27. Tổng của 3 số này chính là tổng của 27 số ban đầu. Vậy từ 53 số tự nhiên bất kì luôn chọn được 27 số mà tổng của chúng chia hết cho 27. Ví dụ 12. Trong một giải bóng đ{ có 12 đội tham dự, thi đấu vòng tròn một lượt(hai đội bất kì thi đấu với nhau đúng một trận). a) Chứng minh rằng sau bốn vòng đấu(mỗi đội thi đấu đúng 4 trận) luôn tìm được ba đội đôi một chưa thi đấu với nhau b) Khẳng định còn đúng không nếu mỗi đội thi đấu đúng 5 trận. Lời giải a) Có 12 đội mà mỗi đội thí đấu đúng 4 trận nên luôn tìm được hai đội chưa thi đấu với nhau. Gọi hai đội đó l| A v| B. Vì A v| B thi đấu đúng 4 trận nên trong 10 đội còn lại luôn tìm được ít nhất hai đội chưa thi đấu với cả A và B. Gọi một trong hai đội đó l| C. Ba đội A, B, C chưa thi đấu với nhau một trận n|o nên ba đội A, B, C l| ba đội cần tìm. b) Ta chia 12 đội bóng trên thành hai nhóm, mỗi nhóm 6 đội. Trong mỗi nhóm đôi một thi đấu với nhau. Như vậy trong 12 đội này, mỗi đội thi đấu đúng 5 trận. Xét ba đội tùy ý, theo nguyên lí Dirichlet luôn tìm được hai đội cùng nhóm. Như vậy trong ba đội bóng bất kì luôn tìm được hai đội thí đấu với nhau. Do đó khẳng định trên không còn đúng nếu mỗi đội thi đấu đúng 5 trận. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
11. 10 Ví dụ 13. Cho X là một tập hợp gồm 700 số nguyên dương đôi một khác nhau, mỗi số không lớn hơn 2006. Chứng minh rằng trong tập hợp X luôn tìm được hai phần tử x, y sao cho x – y thuộc tập hợp E 3;6;9 . Lời giải 700 Theo nguyên lý Dirichlet thì trong 700 số có ít nhất 1 234 số có cùng số dư khi chia cho 3 3. Gọi 234 số đó l| 1 a1 a 2 ... a 234 2006 . Giả sử không tồn tại hai số aij ;a nào thỏa mãn aija 3;6;9  do đó aij a 12 (vì aij a 3 và aaij). Trong 234 số trên, hai số kề nhau hơn kém nhau ít nhất 12 đơn vị nên a234 a 1 233.12 2796 2006 , điều này vô lý. Như vậy ta có điều phải chứng minh. Chú ý: + Ta có thể làm chặt bài toán bằng cách giảm số các số cho ban đầu hoặc tăng gi{ trị cho các số có thể nhận. Ta có thể làm chặt bài toán bằng cách thay 700 số thành 504 số. Gọi 504 số nguyên dương đôi một kh{c nhau đã cho l| 1 a1 a 2 ... a 504 2006 . Xét 504 4 2016 số nguyên dương như sau: < a1 a2 a503 a504 < a31 a32 a3503 a3504 < a61 a62 a6503 a6504 < a91 a92 a9503 a9504 Vì các số trong bảng trên nhận các giá trị nguyên từ 1 đến 2006 9 2015 nên theo nguyên lí 2016 Dirichlet, có ít nhất 12 số nhận cùng một giá trị hay có hai số bằng nhau, suy ra điều 2015 phải chứng minh. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
12. 11 Ví dụ 14. Cho năm số nguyên dương đôi một phân biệt sao cho mỗi số trong chúng không có ước số nguyên tố nào khác 2 và 3. Chứng minh rằng trong năm số đó tồn tại hai số mà tích của chúng là một số chính phương. Lời giải Gọi các số đã cho l| a1 ;a 2 ;a 3 ;a 4 ;a 5 vì các số này không có ứơc số nguyên tố nào khác 2 và xyii 3 nên các số n|y đều có dạng ai 2 .3 với xii ; y là các số tự nhiên. Xét 5 cặp số x;y1 1 ,x;y 2 2 ,x;y 3 3 ,x;y 4 4 ,x;y 5 5 mỗi cặp số này nhận giá trị một trong bốn trường hợp sau (số chẵn; số chẵn), (số chẵn; số lẻ), (số lẻ; số lẻ) và (số lẻ; số chẵn) nên theo nguyên lí Dirichlet thì có ít nhất 2 cặp số trên nhận cùng một dạng giá trị. Không mất tính tổng quát khi giả sử x1 ; y1 , x 2 ; y 2 cùng nhận giá trị dạng( số chẵn; số lẻ). Khi đó xx12 và x1 y 1 x 2 y 2 x 1 x 2 y 1 y 2 yy12 đều là số chẵn nên a12 .a 2 .3 .2 .3 2 .3 là một chính phương. Do đó ta có điều phải chứng minh. Ví dụ 15. Cho lưới ô vuông kích thước 5x5. Người ta điền vào mỗi ô của lưới một trong các số 1;0; 1. Xét tổng của các số được tính theo từng cột, theo từng hàng và theo từng đường chéo. Chứng minh rằng trong tất cả các tổng đó luôn tồn tại hai tổng có giá trị bằng nhau. Lời giải Có tất cả 12 tổng gồm 5 tổng theo cột, 5 tổng theo hàng và 2 tổng theo đường chéo. Mỗi tổng gồm năm số hạng mà mỗi số hạng nhận một trong ba số là 1 hoặc 0 hoặc 1 . Do mỗi tổng là một số nguyên. Gọi các tổng đó l| Si với i 1;2;3;...;12 thỏa mãn 5 Si 5 . Vậy Si có thể nhận trong mười một giá trị 5; 4; 3;...;0;1;...;5 . Mà ta lại có 12 tổng Si nên theo nguyên lí Dirichlet thì có ít nhất hai tổng nhận cùng một giá trị. Vậy ta có điều phải chứng minh. Ví dụ 16. Cho n3 số nguyên dương a1 ;a 2 ;a 3 ;...;a n đôi một khác nhau. Tìm giá trị lớn nhất của n sao cho tổng của ba số bất kỳ trong n số đó luôn l| một số nguyên tố. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
13. 12 Lời giải Dễ thấy với n3 ta luôn tìm được các số nguyên dương thỏa mãn yêu cầu bài toán. Với n4 ta xét c{c trường hợp sau: Trường hợp 1: Với n4 , ta tìm được bốn số nguyên dương 1, 3, 7, 9 thỏa mãn yêu cầu bài toán. Trường hợp 2: Với n5 , ta sẽ chứng minh luôn tìm được ba số có tổng lớn hơn 3 v| chia hết cho 3. Thật vậy, một số nguyên khi chia cho 3 có thể có số dư l| hoặc 0 hoặc 1 hoặc 2. Theo nguyên lý Dirichlet thì trong 5 số nguyên dương bất kỳ có ít nhất hai số có cùng số dư khi chia cho 3. + Nếu có nhiều hơn 2 số có cùng số dư khi chí cho 3 thì có ít nhất 3 số có cùng số dư khi chia cho 3. Chọn 3 số này thì tổng của chúng chia hết cho 3. + Nếu có đúng 2 số có số dư r với r 0;1;2  thì loại hai số n|y, khi đó ta còn lại 3 số có số dư khác r. Theo nguyên lý Dirichlet thì có ít nhất 2 số có cùng số dư kh{c r v| một số còn lại có số dư khác số dư của hai số n|y. Như vậy trong 5 số đó luôn tồn tại 3 số có 3 số dư kh{c nhau khi chia cho 3. Chọn 3 số này thì tổng của chúng chia hết cho 3. Do đó trong 5 số nguyên dương ta luôn chọn được 3 số có tổng chia hết cho 3 và tổng này lớn hơn 3 nên nó không phải là số nguyên tố. Từ đó suy ra n5 thì không thỏa mãn yêu cầu bài toán. Vậy giá trị lớn nhất thỏa mãn yêu cầu bài toán là n4 . Ví dụ 17. Mỗi đỉnh của hình lập phương được điền một trong các số 1;2;3;4;5;6;7;8 . Hai đỉnh kh{c nhau điền hai số kh{c nhau. Người ta tính tổng hai số ở hai đỉnh kề nhau. Chứng minh rằng trong các tổng tính được có ít nhất hai tổng bằng nhau. Lời giải Do mỗi đỉnh của hình lập phương nhận các giá trị khác nhau từ các số 1;2;3;4;5;6;7;8 . Do ta tính tổng hai số ở hai đỉnh kề nhau nên ta có 12 tổng. Khi đó mỗi tổng là một số nguyên dương nhận các giá trị thuộc tập 3;4;5;...;13;14;15 . Ta sẽ chứng minh trong 12 tổng này không thể đồng thời nhận các giá trị 3, 4, 5 ,6 và không thể đồng thời nhận các giá trị 12, 13, 14, 15. Thật vậy, giả sử có các tổng nhận các giá trị 3, 4, 5, 6. Ta kí hiệu đỉnh K l| đỉnh được điền số K. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
14. 13 Ta có 3 1 2;4 1 3 nên đỉnh 1 v| đỉnh 2 kề nhau, đỉnh 1 kề với đỉnh 3. Do đó đỉnh 2 v| đỉnh 3 không kề nhau. Vì 5 1 4 hoặc 5 2 3 , nhưng đỉnh 2 v| đỉnh 3 không kề nhau nên đỉnh 1 và đỉnh 4 kề nhau. Do đó đỉnh 1 lần lượt kề với đỉnh 2, đỉnh 3, đỉnh 4, suy ra đỉnh 1 không kề với đỉnh 5, đỉnh 2 không kề với đỉnh 4. Vì vậy không xuất hiện tổng có giá trị bằng 6. Với các tổng nhận các giá trị 12, 13, 14, 15 ta chứng minh ho|n to|n tương tự. Từ đó suy ra 12 tổng nhận không quá 11 giá trị nên theo nguyên lí Dirichslet có ít nhất hai tổng bằng nhau. Ví dụ 18. Cho tập hợp X 1; 2; 3;...; 2024. Chứng minh rằng trong 90 số khác nhau bất kỳ 1 được lấy ra từ tập X luôn tồn tại hai số x và y sao cho xy . 2 Lời giải Chia 2012 số 1; 2; 3;...; 2012 th|nh 44 đoạn gồm 1; 3 , 4; 8 ,..., 1936; 2012 . 2 C{c đoạn trên có dạng tổng quát là k2 ; k 1 1 . Như vậy 90 số thuộc tập hợp X nằm trong 44 đoạn trên. Theo nguyên lí Dirichlet thì tồn tại ba số trong 90 số trên nằm trong cùng một đoạn. Không mất tính tổng quát ta giả sử hai số đó l| x, y, z 2 và chúng nằm trong đoạn k2 ; k 1 1 . 2 2 Chia đoạn k2 ; k 1 1 th|nh hai đoạn là k22 ; k k và k2 k; k 1 1 Khi đó theo nguyên lí Dirichlet tồn tại hai số nằm trên cùng một đoạn. Giả sử hai số đó l| x v| y. Khi đó Nếu x và y nằm trên đoạn k22 ; k k thì ta được 1 1 1 x y k2 k k 2 k 2 k k 2 k k 4 2 2 2 Nếu x và y nằm trên đoạn k2 k; k 1 1 thì ta được Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
15. 14 2 2 2 k 1 1 k k k1 x y k 1 1 k2 k . 2 k 1 1 k2 k 2k 2 Từ đó ta có điều phải chứng minh. Ví dụ 19. Cho A là tập hợp gồm 6 phần tử bất kỳ của tập hợp 0;1;2;...;14 . Chứng minh rằng tồn tại hai tập hợp con B,B12của tập hợp A( B,B12khác nhau và khác rỗng ) sao cho tổng tất cả các phần tử của tập hợp B1 bằng tổng tất cả các phần tử của tập hợp B2 . Lời giải Do A là tập hợp có 6 phần tử nên số tập hợp con khác rỗng và khác A của tập hợp A là 26 2 62 . Xét tập hợp X là tập hợp con bất kì trong 62 tập hợp con trên và SX là tổng các phần tưt của X. Tập hợp X có nhiều nhất 5 phần tử thuộc tập hợp 0;1;2;...;14  nên ta có 0 S X 10 11 12 13 14 60 . Như vậy với 62 tập hợp con của A như trên thì tồng tại 62 tổng không vượt quả 60. Theo nguyên lý Dirichlet thì tồn tại hai tổng có giả trị bằng nhau. Điều đó chứng tỏ tồn tại hai tập hợp con B,B12của tập hợp A có tổng các phần tử của chúng bằng nhau. Ví dụ 20. Trong hình vuông cạnh bằng 1 ta đặt 51 điểm phân biệt bất kì. Chứng minh rằng 1 có ít nhất 3 trong số 51 điểm đó nằm trong một hình tròn bán kính . 7 Lời giải 1 Chia hình vuông đã cho th|nh 25 hình vuông con bằng nhau có cạnh bằng . Theo nguyên lý 5 Dirichlet thì tồn tại ít nhất một hình vuông nhỏ chứa ít nhất ba điểm trong số 51 điểm đó. Ta kí 2 hiệu hình vuông đó l| C. Khi đó hình vuông nhỏ C có đường chéo là . Đường tròn ngoại tiếp 5 Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
16. 15 1 2 1 1 hình vuông nhỏ C có bán kính . . Vậy ba điểm nói trên nằm trong hình tròn 2 552 7 1 đồng tâm với đường tròn ngoại tiếp hình vuông nhỏ đó có b{n kính . 7 Tổng quát hóa bài toán: Dựa vào bài giải bài toán trên ta có thể tổng quát hóa bài toán trên với a là kích thước của cạnh hình vuông, m là số điểm đặt bất kì, phân biệt. Chứng minh rằng có ít nhất n a2 trong số m điểm đó nằm trong một hình trong bán kính . (Trong đó kí hiệu [a] là phần m 2. n1 nguyên của a). Lời giải m a2 Chia hình vuông đã cho th|nh hình vuông con bằng nhau có cạnh bằng . Theo n1 m n1 nguyên lí Dirichlet thì tồn tại ít nhất một hình vuông nhỏ có chứa ít nhất n điểm trong số m điểm đó. Ta kí hiệu đó l| hình vuông C. Đường tròn ngoại tiếp C có bán kính aa22 . Vậy n điểm trên nằm trong hình tròn đồng tâm với đường tròn C có mm 2. 2. n 1 n 1 a2 bán kính . m 2. n1 Ví dụ 21. Trong hình tròn đường kính bằng 5 có 10 điểm. Chứng minh rằng tồn tại ít nhất hai điểm mà khoảng cách giữa chúng bé hơn hoặc bằng 2. Lời giải Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
17. 16 Thật vậy, trong đường tròn t}m O đường kính D 5, vẽ đường tròn đồng t}m v| đường kính 2. IX II Chia hình tròn đã cho th|nh 9 phần(xem hình C III vẽ) đường tròn đường kính 2 và 8 phần bằng VIII O B 1 A nhau II, III, <, IX m| mỗi phần là hình I IV 8 VII v|nh khăn. Rõ ràng phần I có đường kình VI V bằng 2. Xét chẳng hạn hình III, ta kí hiệu là 1 ABCD (có là hình v|nh khăn). Ta hãy tính 8 đường kính của nó. Có thể thấy ngay đường kính của III là d AC BD . Vì DOA 45o , nên d2 DA 2 DO 2 AO 2 2DO.OA.cos450 2 22 5 5 2 24 5 2 2 29 5 Hay ta được d 1 2 .1. 1 . Tù đó suy ra d .1,4 nên d2 . 2 2 2 4 2 42 Theo nguyên lí Dirichlet tồn tại ít nhất hai điểm rơi v|o một trong các miền I, II, III, < , IX có đường kính bằng 2, còn các miền II, <, IX có đường kính bằng nhau và bằng d2 , từ đó suy ra tồn tại hai trong số 10 điểm đã cho m| khoảng cách giữa chúng nhỏ hơn hoặc bằng 2. Đó chính l| điều cần chứng minh. Ví dụ 22. Trên mặt phẳng cho 25 điểm. Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình tròn bán kính 1 chứa không ít hơn 13 điểm đã cho. Lời giải Lấy A là một trong số 25 điểm đã cho. Xét hình tròn O1 A;1 có tâm A bán kính 1. Chỉ có hai khả năng sau có thể xảy ra như sau: + Thứ nhất: Nếu tất cả c{c điểm đã cho nằm trong O1 A;1 thì kết luận của bài toán hiển nhiên đúng. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
18. 17 + Thứ hai: Tồn tại điểm B kh{c điểm A và B thuộc trong số 25 điểm đã cho, sao cho B không nằm trong đường tròn O1 A;1 , khi đó ta có AB 1. Xét hình tròn O2 B;1 có tâm B bán kính 1. Lấy C l| điểm bất kì trong số 25 điểm đã cho sao cho C khác A và khác B. Theo giả thiết và AB 1 ta có Min CA;CB  1. Vì thế C thuộc đường tròn O1 A;1 hoặc C thuộc đường tròn O2 B;1 . Điều này chứng tỏ rằng các hình tròn O1 A;1 và O2 B;1 chứa tất cả 25 điểm đã cho. Vì thế theo nguyên lí Dirichlet thì ít nhất 1 trong hai hình tròn trên chứa 13 điểm đã cho. Đó l| điều phải chứng minh. Bài toán tổng quát: Cho 2n 1 điểm trên mặt phẳng với n3 . Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Khi đó tồn tại hình tròn bán kính 1 chứa không ít hơn n1 điểm đã cho. Ví dụ 23. Tìm hình vuông có kích thước bé nhất, để trong hình vuông đó có thể sắp xếp năm hình tròn bán kính bằng 1 sao cho không có hai hình tròn n|o trong chúng có điểm chung. Lời giải Giả sử hình vuông ABCD có tâm O A B và cạnh a, chứa năm hình tròn không cắt A' B' O' O'' nhau v| đều có bán kính bằng 1. Vì cả năm hình tròn n|y đểu nằm trọn trong hình O O' vuông, nên các tâm của chúng nằm trong D' C' hình vuông A’B’C’D’ có tâm O và cạnh O'' D C a2 , ở đ}y A’B’//AB. C{c đường thẳng nối c{c trung điểm cùa các cạnh đối diện của hình vuông A’B’C’D’ chưa A’B’C’D’ thành 4 hình vuông nhỏ. Theo nguyên lí Dirichlet tồn tại một trong 4 hình vuông nhỏ mà trong hình vuông này chứa ít nhất hai trong số 5 tâm hình tròn nói trên(không mất tính tổng quát ta giả sử l| O’ v| O‛). Để ý rằng vì không có hai hình tròn nào(trong số năm hình tròn) cắt nhau nên O'O'' 2 Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
19. 18 Mặt kh{c do O’ v| O‛ cùng nằm trong một hình vuông nhỏ(cạnh của hình vuông nhỏ đó bằng a2 a2 a2 ) nên ta lại có O'O'' . 2 . Từ đó ta suy ra được . 2 2 a 2 2 2 . 2 2 2 Vậy mọi hình vuông cạnh a thỏa mãn yêu cầu đề b|i, ta đều có a 2 2 2 . Bây giờ xét hình vuông ABCD có a 2 2 2 . Xét năm hình tròn có t}m l| O, A’, B’, C’, D’ (xem hình vẽ) , thì mọi yêu cầu của đề bài thỏa mãn. Tóm lại, hình vuông có kích thước bé nhất cần tìm là hình vuông với cạnh a 2 2 2 . Ví dụ 24. Chứng minh rằng trong một hình tròn bán kính 1, không thể chọn được qu{ 5 điểm mà khoảng cách giữa hai điểm tùy ý trong chúng đều lớn hơn 1. Lời giải Chia hình tròn thành 6 hình quạt bằng nhau (tâm các hình quạt đều tại t}m O đã cho). Ta biết rằng A2 khoảng cách giữa hai điểm bất kì trong một hình A 1 A3 quạt nhỏ hơn hoặc bằng 1, vì thế từ giả thiết suy ra O tại mỗi hình quạt có không qu{ 1 điểm rơi v|o. Giả A6 A4 thiết phản chứng chọn được qu{ năm điểm thỏa A5 mãn yêu cầu đề bài. Vì lí do trên nên số điểm không thể quá 7(vì nếu số điểm chọn được mà lớn hơn hoặc bằng 7 thì theo nguyên lí Dirichlet có ít nhất hai điểm được chọn nằm trong một cung hình quạt, m| điều này mâu thuẫn với nhận xét trên.). Vậy từ giả thiết phản chứng suy ra tồn tại s{u điểm A,A,A,A,A,A1 2 3 4 5 6 và mỗi điểm nằm trong một hình quạt sao cho khoảng cách giữa hai điểm tùy ý trong chúng đều lớn hơn 1. 0 Do A122334455616 OA A OA A OA A OA A OA A OA 360 . 3600 Khi đó suy ra MinA OA 600 ,i 1,6 (ở đ}y đặt AA ). i i 1 6 71 Xét tam giác Ak OA k 1 với k 1;2;3;4;5;6  và AA71 , sao cho MinAi OA i 1 A k OA k 1 Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC
20. 19 0 Khi đó Ak OA k 1 60 . Vì OA 1; OA 1; A OA 600 nên từ đó suy ra A OA Max A A O;OA A . k k 1 k k 1 k k 1 k k 1 k k 1 Từ đó theo mối liên hệ giữa cạnh và góc trong tam giác Ak OA k 1 , thì Ak Ak 1 max OAk ,OA k 1  1. Điều này mâu thuẫn với Ak A k 1 1(vì hệ s{u điểm A,A,A,A,A,A1 2 3 4 5 6 thỏa mãn yêu cầu đề bài). Từ đó ta thấy giả thiết phản chứng l| sai. Điều đó có nghĩa l| không thể chọn qu{ 5 điểm thỏa mãn yêu cầu để bài. Ví dụ 25. Cho 1000 điểm M1 ,M 2 ,...,M 1000 trên mặt phẳng. Vẽ một đường tròn bán kính bằng 1 tùy ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao cho SM1 SM 2 ... SM 1000 1000 . Lời giải Xét một đường kính SS12tùy ý của đường tròn bán M2 M1 kính bằng 1, ở đ}y S,S12l| hai đầu của đường kính. Khi đó ta có S12 S 2 , nên ta có S1 S2 O S M S M S S 2 1 1 2 1 1 2 S M S M S S 2 1 2 2 2 1 2 ... M1000 S1 M 1000 S 2 M 1000 S 1 S 2 2 Cộng từng vế của 1000 bất đẳng thức trên ta có: S1 M 1 S 1 M 2 ... S1 M 1000 S 2 M 1 S 2 M 2 ... S2 M 1000 2000 Từ đó theo nguyên lí Dirichlet suy ra trong hai tổng SM1 1 SM 1 2 ...SM 1 1000 ;SM 2 1 SM 2 2 ...SM 2 1000 có ít nhất một tổng lớn hơn hoặc bẳng 1000. Giả sử S1 M 1 S 1 M 2 ... S1 M 1000 1000. khi đó lấy SS 1 . Đó l| điều phải chứng minh. Tác giả: Nguyễn Công Lợi TÀI LIỆU TOÁN HỌC