Nguyên lý Dirichlet và những bài toán liên quan

NGUYÊN LÝ DIRICHLET VÀ NHỮNG BÀI TOÁN LIÊN QUAN NGUYỄN MINH TUẤN Bộ Môn Toán học Trường ĐHGD, ĐHQG HN Nhà G7, 144 đường Xuân Thủy, q. Cầu Giấy Hà Nội, Việt Nam Email: nguyentuan@vnu.edu.vn Ngày 05 Tháng 11 năm 2013 1 Giới thiệu Nguyên lý chuồng bồ câu, nguyên lý hộp hay nguyên lý ngăn kéo Diritchlet được phát biểu như sau: nếu n con chim bồ câu được đặt vào m chuồng, với n > m, thì ít nhất một chuồng có nhiều hơn 1 con. Nguyên lý này có thể minh họa bởi nhiều ví dụ cụ thể hơn, chẳng hạn: trong 3 găng tay, có ít nhất hai găng tay phải hoặc hai găng tay trái.. Mặc dù đây có vẻ là một trực giác đơn giản nhưng nó lại được dùng để chứng minh nhiều điều bất ngờ trong toán học. Người đầu tiên đề xuất ra nguyên lý này được cho là nhà toán học Đức Johann Dirichlet1 khi ông đề cập tới nó với tên gọi nguyên lý ngăn kéo. Vì vậy, nguyên lý ngăn kéo Dirichlet hay gọn hơn nguyên lý Dirichlet là những cách khác nói về nguyên lý chuồng bồ câu. Nguyên lý ngăn kéo Dirichlet cũng đúng cho tập hợp vô hạn phần tử. Cụ thể, ta có khẳng định sau: giả sử số lượng vô hạn các phần tử chứa trong n (hữu hạn) tập hợp. Khi đó, tồn tại ít nhất một tập hợp chứa vô hạn phần tử. Để phát biểu dưới dạng tổng quát hơn, ta cần một số ký hiệu. Ta ký hiệu dm/ne là phần nguyên trên của phân số m/n bằng số nguyên nhỏ nhất không nhỏ số m/n. Ví dụ d9/10e = 1. Ta ký hiệu bm/nc là phần nguyên dưới của phân số m/n bằng số nguyên lớn nhất không vượt quá m/n. Ví dụ b4/5c = 0. 1Tên đầy đủ là Johann Peter Gustav Lejeune Dirichlet, 1805-1859 1 Hình 1: Dirichlet, nhà toán học người Đức, 1805-1859 Định lý 1.1. Nếu m con chim bồ câu được đặt vào n chuồng và m > n, thì (ít nhất) một chuồng có ít nhất bm/nc con nếu m chia hết n, và ít nhất bm/nc+1 con nếu m không chia hết n. Hình 2: Nguyên lý chuồng chim bồ câu 2 Mở rộng hơn, ta có có định lý sau: Định lý 1.2. Nếu m vật có trong n hộp, thì ít nhất một hộp có không ít hơn dm/ne vật, và một hộp có không quá bm/nc vật. Nguyên lý ngày sinh đề cập đến khả năng về một số người có cùng ngày sinh trong số m người cho trước. Theo nguyên lý ngăn kéo Dirichlet, nếu m = 367 thì có ít nhất hai người có cùng ngày sinh. Hình 3: Rebecca Dirichlet 2 Một số bài toán Bài toán 2.1. Chứng minh rằng không tồn tại đường thẳng không đi qua đỉnh và cắt ba cạnh của tam giác. Lời giải. Ta chứng minh bằng phản chứng. Giả sử ngược lại, tồn tại đường thẳng không đi qua đỉnh và ` cắt ba cạnh của tam giác ABC. Gọi P1 và P2 là hai nửa mặt phẳng được chia tách bởi đường thẳng `. Ba đỉnh tam giác A,B,C chưa trong hai nửa mặt phẳng P1, P2. Theo nguyên tắc Dirichlet, tồn 3 tại hai đỉnh thuộc cùng một nửa mặt phẳng. Gọi hai đỉnh đó là A và B thuộc nửa mặt phẳng P2. Ta suy ra ` không cắt cạnh AB. Bài toán 2.2. Chứng minh rằng không tồn tại đường thẳng không đi qua đỉnh và cắt tất cả các cạnh của (2n+ 1)-giác. Lời giải. Ký hiệu các đỉnh liên tiếp của đa giác là A1A2 · · ·A2n+1. Suy ra các cạnh của đa giác là A1A2, A2A3, . . . A2nA2n+1, A2n+1A1. Ta chứng minh bằng phản chứng. Giả sử ngược lại, tồn tại đường thẳng ` không đi qua đỉnh và cắt các cạnh của đa giác. Gọi P1 và P2 là hai nửa mặt phẳng được chia tách bởi đường thẳng `. Xét đỉnh A1. Không mất tính tổng quát ta có thể giả thiết A1 ∈ P1. Vì ` cắt cạnh A1A2 ta suy ra A2 ∈ P2. Do ` cắt cạnh A2A3 nên A3 ∈ P1. Cứ lập luận tiếp tục, ta suy ra đỉnh A2n+1 ∈ P1. Như vậy, hai đỉnh A1 và A2n+1 cùng thuộc nửa mặt phẳng P1. Từ đây ta suy ra ` không cắt cạnh A2n+1A1. Mâu thuẫn với giả thiết. Bài toán 2.3. Bài toán 2.2 có đúng không đối với đa giác có số chẵn cạnh? Lời giải. Câu trả lời là phủ định. Minh họa bằng hình vẽ. Bài toán 2.4. Chứng minh rằng trong sáu người bất kỳ, tồn tại ba người đôi một quen hoặc không quen nhau. Lời giải. Gọi sáu người là A,B,C,D,E, F . Ta có thể coi A,B,C,D,E, F là những điểm trong mặt phảng và không thẳng hàng.Ta nối các đỉnh vói nhau theo quy tắc: nếu hai người tương ứng quen nhau ta nối cạnh bởi màu đỏ, ngược lại là màu xanh. Xét A và năm cạnh AB,AC,AD,AE,AF . Trong năm cạnh này tồn tại ba cạnh cùng màu. Giả sử các cạnh AB,AD,AF cùng màu đỏ. Bây giờ, xét các cạnh BD,DF, FB. Ba cạnh này, nếu chúng có cùng màu xanh ta được điều phải chứng minh, rằng ba người B,D, F đôi một không quen nhau. Trái lại, nếu có một cạnh màu đỏ, chẳng hạn cạnh DF . Ta suy ra ba cạnh AD,DF,AF cùng màu đỏ, hay ba người A,D, F đôi một quen nhau. Bài toán được chứng minh. Bài toán nêu trên tương đương với bài toán sau. Bài toán 2.5. Cho sáu điểm không thẳng hàng trong mặt phẳng. Cứ hai điểm được nối với nhau bằng một cạnh được tô màu đỏ hoặc xanh. Chứng minh rằng tồn tại tam giác có ba cạnh cùng màu. Bài toán 2.6. Cho mười sáu điểm không thẳng hàng trong mặt phẳng. Mỗi điểm được tô một trong ba màu đỏ, da cam, hoặc vàng, và hai điểm được nối với nhau bằng một cạnh được tô màu lục hoặc lam. Chứng minh rằng tồn tại tam giác có ba đỉnh cùng màu và ba cạnh cùng màu. 4 Lời giải. Mười sáu điểm được tô bởi ba màu nên có ít nhất sáu điểm cùng màu. Như vậy, ta đưa bài toán này về Bài toán 2.5 cho sáu điểm. Nhận xét 2.1. Con số 16 có thể thay đổi bởi những số bất kỳ, cùng với số màu thay đổi tương ứng. Bài toán 2.7 (bài toán bắt tay). Trong hội nghị có n đại biểu. Khi gặp nhau họ đều bắt tay nhau. Chứng minh rằng tồn tại hai người có số lần bắt tay bằng nhau. Lời giải. Mỗi đại biểu được chia vào một trong n nhóm A0, A1, . . . , An−1 đúng bằng số lần bắt tay của họ. Như vậy, ta có n nhóm. Ta thấy, nếu A0 6= ∅ (nghĩa là có ít nhất một đại biểu chưa bắt tay đại biểu khác, có số lần bắt tay bằng 0) thì An−1 = ∅. Tương tự, nếu An−1 6= ∅ thì A0 = ∅. Như vậy, hai tập hợp A0 và An−1 luôn có ít nhất một tập bằng rỗng. Tóm lại, có n phần tử chia vào n nhóm nhưng luôn có một nhóm không được xếp vào. Theo nguyên lý Dirichlet, tồn tại ít nhất hai phần tử trong cùng một nhóm. Bài toán được chứng minh. Bài toán này tương đương với bài toán sau. Bài toán 2.8. Giải vô địch bóng đá Anh có 20 đội. Chứng minh rằng tại mọi thời điểm của vòng 1, luôn tồn tại ít nhất hai đội có số trận đã đá bằng nhau. Bài toán 2.9. Cho 51 điểm thuộc hình vuông cạnh bằng 5. Chứng minh rằng tồn tại ít nhất ba điểm cùng thuộc một hình tròn có bán kính 1/ √ 2. Lời giải. Chia hình vuông thành 5 × 5 = 25 hình vuông cạnh bằng 1. Như vậy, ta có 25 ô vuông chứa 51 điểm. Theo nguyên lý Dirichlet tồn tại ít nhất 3 điểm thuộc một hình vuông. Tất nhien, hình tròn ngoại tiếp hình vuông có bán kính R = 1/ √ 2 chứa ba điểm đó. Bài toán được chứng minh. Nhận xét 2.2. Ta có thể thay đổi số 51 bởi số bất kỳ, và độ dài cạnh cũng vậy. Tuy nhiên, tùy thuộc vào số điểm và kích thước cạnh mà ta có kết luận tương ứng. Bài toán 2.10. Thầy giáo cho 49 học sinh xếp thành 7 hàng dọc và 7 hàng ngang chơi trò chơi sau: sau một tiếng trống, mỗi học sinh đổi sang một vị trí khác cùng hàng hoặc cùng cột. Gõ trống xong, cả lớp đổi chỗ. Thấy vẫn là 7 hàng ngang và 7 hàng dọc, thầy hỏi: - Các em đã đổi chỗ chưa? - Rồi ạ! Cả lớp đồng thanh đáp. - Có em nào chưa đổi chỗ như thầy yêu cầu không? Thầy hỏi tiếp. Cả lớp im lặng. - Có ít nhất một em chưa đổi chỗ! Thầy nói. Bạn cho biết suy luận logic nào để khẳng định của thầy là đúng. 5 Lời giải. Coi 7 hàng ngang và 7 hàng dọc như là một hình vuông gồm 7×7 = 49 ô vuông nhỏ, mỗi học sinh đứng trong một ô nhỏ đó. Bằng cách tô màu giống như bàn cờ vua: hai ô cùng hàng hoặc cùng cột khác màu nhau, nhưng các ô chéo cùng màu. Có cả thảy 49 ô được tô hai màu nên số ô màu đen không bằng số ô màu trắng. Giả sử có 25 ô đen và 24 ô trắng. Theo quy tắc đổi chỗ, mỗi em phải chuyển sang ô khác màu với ô đang đứng. Như vậy, có 25 em đang đứng ở ô đen phải chuyển sang 24 ô ở ô trắng. Điều này là không thể. Đó là lý do khẳng định của thầy là đúng. Nhận xét 2.3. Ta có thể thay số 7 bởi số lẻ bất kỳ. Bài toán 2.11. Trên bàn cờ vua 8 × 8 người ta bỏ đi hai ô đối đỉnh. Một trong hai ô đỉnh còn lại có một con mã. Hỏi con mã đó có thể đi làn lượt đến tất cả các ô còn lại được không, với điều kiện mỗi ô chỉ được đến một lần? Lời giải. Bàn cờ có 32 ô đen và 32 ô trắng. Hai ô đối đỉnh luôn cùng màu, nên chỉ còn 30 chẳng hạn là màu đen, còn 32 ô trắng. Con mã đi lần lượt từ ô trắng sang ô đen. Nhưng từ 32 ô trắng không thể đến lần lượt được 30 ô đen. Vậy, câu trả lời là: không thể. Bài toán 2.12. Một lớp có 37 học sinh. Chứng minh rằng có ít nhất 4 học sinh có cùng tháng sinh. Lời giải. Một năm có 12 tháng. Chia 37 học sinh vào 12 nhóm theo tháng sinh. Suy ra tồn tại ít nhất 4 học sinh trong cùng một nhóm. Bài toán được chứng minh. Bài toán 2.13. Cho n số tự nhiên a1, a2, . . . an. Chứng minh rằng tồn tại một số hoặc tổng một số số trong đó để tổng chia hết n. Lời giải. Xét n tổng A1 = a1 A2 = a1 + a2 ... ... ... . . . ... ... ... An−1 = a1 + a2 + · · ·+ an−1 An = a1 + a2 + · · ·+ an−1 + an. Nếu một trong các số Aj (j = 1, 2, . . . n) chia hết n, ta có điều phải chứng minh. Ngược lại, các số Aj không chia hết n. Bởi vậy, số dư đó sẽ thuộc tập hợp sau có n− 1 phần tử { 1, 2, 3, . . . , n− 1 } . 6 Theo nguyên lý Dirichlet, tồn tại hai số Aj và Ak có cùng số dư khi chia n, nghĩa là Aj = Ak (mod n). Giả sử Aj > Ak. Từ đây ta suy ra Aj − Ak chia hết n. Bài toán 2.14. Cho 100 số tự nhiên trong khoảng từ 1 đến 199. Chứng minh rằng tồn tại hai số để số này chia hết cho số kia. Lời giải. Ký hiệu 100 số tự nhiên đó là a1, a2, . . . , a100. Giả sử a1 ≤ a2 ≤ · · · ≤ a100. Nếu trong các số a1, a2, . . . , a100 có số 1 thì bài toán hiển nhiên đúng. Giả sử mọi số đều lớn hơn 1. Ta phân tích mỗi số theo lũy thừa của 2 a1 = 2 k1b1, a2 = 2 k2b2, ... ... . . . ... ... a99 = 2 k99b99, a100 = 2 k100b100, ở đây b1, b2, . . . , b100 là những số lẻ từ 3 đến 199. Từ 3 đến 199 chỉ có 99 số lẻ, nên tồn tại i < j để bi = bj . Suy ra aj chia hết ai. Nhận xét 2.4. Ta có thể tổng quát bài toán trên như sau: Cho n số từ nhiên từ 1 đến 2n− 1. Chứng minh rằng tồn tại hai số để số này chia hết số kia. Bài toán 2.15. Có 19 số tự nhiên liên tiếp. Chứng minh rằng tồn tại ít nhất một số có tổng các chữ số chia hết 10. Lời giải. Gọi các số đó là a1, a2, . . . , a19. Trong 10 số đầu tiên a1, a2, . . . , a10 tồn tại một số có tận cùng bằng 0. Gọi số đó là ak (k ≤ 10). Ta ký hiệu ak = m1m2 . . .mj0. Gọi s là tổng các chữ số của ak. Do k ≤ 10 nên còn ít nhất 9 số tiếp theo là ak+1, ak+2, . . . , ak+9. Ta suy ra các số ak+1, ak+2, . . . , ak+9 có tổng các chữ số lần lượt bằng s+ 1, s+ 2, . . . , s+ 9. Trong 10 số tự nhiên liên tiếp s, s+ 1, s+ 2, . . . , s+ 9 có một số chia hết cho 10. Giả sử đó là s + `. Ta suy ra số ak+` có tổng các chữ số chia hết 10. 7 Bài toán 2.16. Có 39 số tự nhiên liên tiếp. Chứng minh rằng tồn tại ít nhất một số có tổng các chữ số chia hết 11. Lời giải. Gọi các số đó là a1, a2, . . . , a39. Trong 20 số đầu tiên a1, a2, . . . , a20 tồn tại một số chia hết 20. Gọi số đó là ak (k ≤ 20). Ta ký hiệu ak = m1m2 . . .mj0, trong đó mj là số chẵn. Gọi s là tổng các chữ số của ak. Do k ≤ 20 nên còn ít nhất 19 số tiếp theo là ak+1, ak+2, . . . , ak+19. Vì mj là số chẵn nên mj ≤ 8. Ta suy ra các số ak+1, ak+2, . . . , ak+9, ak+19 có tổng các chữ số lần lượt bằng s+ 1, s+ 2, . . . , s+ 10. Trong 11 số tự nhiên liên tiếp s, s+ 1, s+ 2, . . . , s+ 10 có một số chia hết cho 11. Giả sử đó là s + `. Ta suy ra tồn tại số aj có tổng các chữ số chia hết 11. Bài toán 2.17. Cho 52 số tự nhiên bất kỳ. Chứng minh rằng tồn tại hai số có tổng hoặc hiệu chia hết 100. Lời giải. Mỗi số tự nhiên chia 100 co số dư từ 0 đến 99. Tuy vậy, các số dư có thể viêt là những số sau: 0,±1,±2, . . . ,±49,±50 (các số dư 51, 52, . . . 99 có thể vết là các số dư bằng -49, -48, . . . , -1). Có 52 số dư được chia trong 51 nhóm 0,±1,±2, . . . ,±49,±50 nên tồn tại hai số có số dư trong cùng nhóm, ký hiệu là ±k, 0 ≤ k ≤ 50. Nếu hai số dư cùng dau thì hệu hai số chia tương ứng chia hết 100, còn nếu chúng trái dấu thì tổng hai số chia tương ứng chia hết 100. Bài toán được chứng minh. Nhận xét 2.5. Bạn đọc có thể thay số 52 bởi số tự nhiên bất kỳ, và chú ý tới kết luận. Bài toán 2.18. Chứng minh rằng tồn tại số là lũy thừa của 19 có dạng A = · · · 000 · · ·0001; nghĩa là tồn tại n ∈ N sao cho 19n = · · · 000 · · ·0001︸ ︷︷ ︸ 2013 chữ số 0 8 Lời giải. Xét dãy vô hạn số 19, 192, 193, . . . 19n . . . Chia mỗi số cho 102014 ta được các số dư từ 0 đến 102014 − 1. Do dãy số trên là vô hạn nên tồn tại hai số có cùng số dư khi chia cho 102014. Ta suy ra hiệu của chúng chia hết cho 102014. Ta có 19m − 19n = 19n(19m−n − 1) = 0 (mod 102014). Do (19n, 102014) = 102014 nên 19m−n − 1 = 0 (mod 102014). Tóm lại, ta có 19m−n − 1 = · · · 000 · · ·000︸ ︷︷ ︸ 2014 chữ số 0 . Từ đây ta suy ra điều phải chứng minh. Nhận xét 2.6. Ta có thể thay số 19 bởi số bất kỳ nguyên tố cùng nhau với 10. Bài toán 2.19. Chứng minh rằng tồn tại vố số số có dạng B = 20142014 · · ·20142014 mà chúng chia hết 2013. Lời giải. Tương tự như Bài toán 2.18 bằng cách xét vô hạn số sau 2014, 20142014, 201420142014, . . . Nhận xét 2.7. Liệu có thể thay số 2014 bởi số bất kỳ khác? Nghiên cứu kỹ hưn, bạn đọc sẽ tìm thấy câu trả lời thú vị. Bài toán 2.20. Chứng minh rằng tồn tại số tự nhiên mà mỗi chữ số chỉ là một trong hai số 0 hoặc 3 để nó chia hết 2013. Lời giải. Xét 2014 số có sau 3, 33, 333, 3333, 33333, . . .333 · · ·333︸ ︷︷ ︸ 2014 chữ số 3 . Tồn tại hai số có cùng số dư khi chi cho 2013. Hiệu hai số này chỉ gồm các chữ số 0 và 3 là số cần tìm. 9 Bài toán 2.21. Trên mặt phẳng cho 49 đ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 ít nhất 25 điểm thuộc cùng một hình tròn bán kính 1. Lời giải. Gọi A1 là một trong số 49 điểm đã cho. Xét hình tròn ω1 tâm A1 bán kính bằng 1. Xét hai khả năng: 1. Tất cả các điểm nằm trong ω1. Ta có điều phải chứng minh. 2. Tồn tại điểm A2 6∈ ω1. Suy ra khoảng cách A1A2 > 1. Xét hình tròn ω2 tâm A2 bán kính 1. Từ giả thiết: ba điểm bất kỳ đều tồn tại hai điểm khoảng cách nhỏ hơn 1, ta suy ra mọi điểm đã cho thuộc một trong hai hình tròn ω1 hoặc ω2. Vậy là, có 49 điểm thuộc một trong hai hình tròn nên tồn tại ít nhất 25 điểm thuộc cùng một hình tròn. Bài toán được giải quyết. Bài toán có thể tổng quát hóa như sau. Bài toán 2.22. Có 2n+1 điểm trên mặt phẳng(với n ≥ 3). Biết rằng ba điểm bất kì luôn tồn tại hai điểm có khoảng cách nhỏ hơn 1. Chứng minh rằng tồn tại n+ 1 điểm thuộc cùng một hình tròn bán kính 1. Lời giải. Chọn một điểm A bất kỳ trong số 2n + 1 điểm đã cho. Xét đường tròn ω1 có tâm A bán kính bằng 1. Có hai khả năng: 1. Tất cả các điểm nằm trong ω1. Ta có điều phải chứng minh. 2. Tồn tại điểm A2 6∈ ω1. Suy ra khoảng cách A1A2 > 1. Xét hình tròn ω2 tâm A2 bán kính 1. Từ giả thiết: ba điểm bất kỳ đều tồn tại hai điểm khoảng cách nhỏ hơn 1, ta suy ra mọi điểm đã cho thuộc một trong hai hình tròn ω1 hoặc ω2. Vậy là, có 2n + 1 điểm thuộc một trong hai hình tròn nên tồn tại ít nhất n+ 1 điểm thuộc cùng một hình tròn. Bài toán được giải quyết. Bài toán 2.23. Cho 2000 số tự nhiên từ 1 đến 10.000. Chứng minh rằng tồn tại hai số có hiệu là một số có bốn chữ số bằng nhau. Lời giải. Chia 2000 số cho 1111 được các số dư từ 0 đến 1110. Từ 1 đến 10.000 có 9 số chia hết 111 là các số 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, và 9999. Dó đó, trong số 2000 số đã cho tồn tại ít nhất 2 số có cùng số dư khác 0 khi chia cho 1111. Ta suy ra hiệu của chúng chia hết 1111. Những các số từ 1 dến 10.000 chi hết 1111 khi và chỉ khi nó có bốn chữ số bằng nhau. 10 Nhận xét 2.8. Bạn đọc có thể thay dữ liệu trong bài toán để được nhiều bài toán khác. Bài toán 2.24. Tồn tại hay không số tự nhiên có dạng A := 20132013 · · ·20132013︸ ︷︷ ︸ n số 2013 để A chia hết 2320? Lời giải. Xét tập hợp vô hạn số có dạng 20132013 · · ·20132013︸ ︷︷ ︸ n số 2013, , ở đây n ≥ 1. Chia mỗi số cho 2320 ta được các số dư từ 0 đến 2320− 1. Ta suy ra tồn tại hai số có cùng số dư. Giả sử A := 20132013 · · ·20132013︸ ︷︷ ︸ m số 2013 = k (mod 2320), B := 20132013 · · ·20132013︸ ︷︷ ︸ n số 2013 = k (mod 2320), ở đây A > B. Khi đó A−B chia hết 2320. Hay 104n × 20132013 · · ·20132013︸ ︷︷ ︸ m−n số 2013 ... 2320. Do (2320, 10n) = 1 ta có 20132013 · · ·20132013︸ ︷︷ ︸ m−n số 2013 ...2320 ... 2320. Bài toán được chứng minh. Nhận xét 2.9. Bạn đọc có thể thay các dữ liệu trong bài toán để được nhiều bài toán khác. Bài toán 2.25. Có 49 học sinh trong một lớp. Hàng tuần thầy giáo chia lớp thành 7 nhóm, mỗi nhóm 7 em để thực hành môn kỹ thuật điện. Chứng minh rằng sau 9 tuần có ít nhất hai học sinh đã cùng ở một tổ trong hai tuần khác nhau. Lời giải. Giả sử ngược lại, không có hai em nào chung một tổ trong hai tuần khác nhau. Gọi A là một học sinh bất kỳ. Sau 9 tuần em đó đã ở cùng tổ với ít nhất 9× 6 = 54 bạn khác khác nhau. Vô lý vì sĩ số lớp là 49. 11 Bạn hãy tổng quát bài toán trên! Bài toán 2.26. Cho 2013 số tự nhiên dương đôi một khác nhau và nhỏ hơn 4020. Chứng minh rằng có thể chọn được ba số để một số bằng tổng hai số kia. Lời giải. Giả sử a1 < a2 < · · · < a2013. Xét 2012 số sau đây đôi một khác nhau: a2 − a1, a3 − a1, a4 − a1, . . . , a2013 − a1. Ta gọi các số này thuộc nhóm A. Cùng với 2012 số sau cũng đôi một khác nhau a2, a3, . . . , a2013, ta gọi là nhóm B. Các số thuộc nhóm A (đôi một khác nhau) cũng như các số thuộc nhóm B (đôi một khác nhau) là 4024 số tự nhiên dương trong khoảng từ 1 đến 4020. Ta suy ra tồn tại số ở nhóm này bằng số ở nhóm kia. Giả sử ak − a1 = a`. Do đó ta có ak = a1 + a`. Điều phải chứng minh. Bài toán 2.27. Chứng minh rằng tồn tại số n ∈ N để 17n có dạng 111 . . . 111. Lời giải. Xét dãy vô hạn số có dạng 11, 111, 1111, 11111, . . . Chia mỗi số cho 17 ta được số dư từ 0 đến 16. Nếu có số dư nào bằng 0 ta suy ra điều phải chứng minh. Trái lại, tồn tại hai số dư bằng nhau. Giả sử 111 . . . 111︸ ︷︷ ︸ m số 1 = 111 . . . 111︸ ︷︷ ︸ n số 1 (mod 17). Ta có thể giả thiết m > n. Khi đó 111 . . . 111︸ ︷︷ ︸ m số 1 − 111 . . . 111︸ ︷︷ ︸ n số 1 = 0 (mod 17). Hay 10n111 . . . 111︸ ︷︷ ︸ m số 1 = 0 (mod 17). Do (10n, 17) = 1 ta có 111 . . . 111︸ ︷︷ ︸ m số 1 = 0 (mod 17). Từ đây ta suy ra điều phải chứng minh. Nhận xét 2.10. Bạn đọc hãy thay số 17 bởi số tự nhiên khác phù hợp để có bài toán mới. 12 Bài toán 2.28. Cho m,n là số tư nhiên thỏa mãn (m,n) = 1. Chứng minh rằng tồn tại k ∈ N để cho (mk − 1) ... n. Lời giải. Xét vô hạn số có dạng m,m2, m3, m4, . . . , mn, . . . Chia mỗi số cho n ta được n số dư từ 0 đến n − 1. Do đó, tồn tại hai số có cùng số dư. Giả sử mi = mj (mod n). Giả sử j > i. Ta suy ra mj −mj = mi(mj−i − 1) = 0 (mod n). Từ giả thiết (m,n) = 1 ta suy ra mj−i−1 = 0 (mod n). Ta có điều phải chứng minh. Bài toán 2.29. Cho 2013 điểm thuộc hình tròn bán kính 1 (đơn vị độ dài). Chứng minh rằng tồn tại điểm S trên đường tròn để tổng khoảng cách từ nó đến 2013 đã cho không nhỏ hơn 2013 (đơn vị độ dài). Lời giải. Gọi M1,M2, . . . ,M2013 là 2013 điểm thuộc hình tròn. Chọn hai điểm A và B đối tâm bất kỳ thuộc đường tròn. Với mội k = 1, 2, . . . 2013 ta có AMk +BMk ≥ 2. Do đó [ 2013∑ k=1 AMk ] + [ 2013∑ k=1 BMk ] ≥ 2013× 2 = 4026. Coi vế trái như là tổng của hai số (trong ngoặc vuông) không nhỏ hơn 4026. Ta suy ra có ít nhất một tổng không nhỏ hơn 2013. Giả sử tổng thứ nhất không nhỏ hơn 2013. Ta suy ra điểm A thỏa mãn yêu cầu của bài toán. Bài toán 2.30. Chứng minh rằng tồn tại số tự nhiên có dạng A := 111 . . . 111︸ ︷︷ ︸ n số 1 để A ... 39. Lời giải. Tương tự như lời giải cho Bài toán 2.27. 13 3 Bài tập Bài tập 1. Một lớp 43 học sinh viết chính tả tiếng Việt. Có đúng một học sinh mắc 9 lỗi, các em còn lại mắc lỗi ít hơn. 1. Chứng minh rằng có ít nhất 5 học sinh có số lỗi bằng nhau. 2. Biết rằng không có học sinh nào mắc 6, 7, 8 lỗi, và có không quá 6 học sinh có cùng số lỗi. Hỏi ít nhất bao nhiêu em không mắc lỗi nào? Bài tập 2. Chứng minh rằng tồn tại số tự nhiên có bốn chữ số cuối cùng bằng 2014 để số đó chia hết 2013. Bài tập 3. Giả sử mỗi điểm thuộc mặt phẳng được tô bởi một trong hai màu xanh hoặc đỏ. Chứng minh rằng tồn tại ít nhất một hình chữ nhật có bốn đỉnh cùng màu. Bài tập 4. Cho 2014 số tự nhiên đôi một khác nhau từ 1 đến 4026. Chứng minh rằng tồn tại hai số có hiệu bằng 2013. Bài tập 5. Cho 1978 tập hợp A1, A2, . . . , A1978, mỗi tập hợp có đúng 40 phần tử. Biết rằng hai tập hợp bất kỳ chỉ có một phần tử chung. Chứng minh rằng tồn tại một phần tử thuộc 1978 tập hợp nới trên. Bài tập 6. Cho tập hợp A gồm 2014 số 1 hoặc -1. Chứng minh rằng có thể chia tập A thành hai nhóm A = A1 ∪ A2 để tổng các số trong nhóm A1 bằng tổng các số thuộc nhóm A2. Bài tập 7. Tồn tại hay không hai số chính phương có hiệu bằng 2014? Bài tập 8. Cho chín đường thẳng cùng có tính chất là mỗi đường thẳng chia hình vuông thành hai tứ giác có tỉ số diện tích bằng 2/3. Chứng minh rằng có ít nhất ba đường thẳng trong số đó cùng đi qua một điểm. Bài tập 9. Các số tự nhiên 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 được viết theo thứ tự bất kỳ. Thành lập dãy mới bằng mỗi số trong dãy trên cộng với số thứ tự của nó. Chứng minh rằng trong dãy thứ hai, có ít nhất hai số chia 10 có cùng số dư. Bài tập 10. Cho hình chóp đáy là đa giác chín cạnh. Tất cả các cạnh bên và 27 đường chéo của đa giác đáy được tô bằng một trong hai màu đỏ hoặc xanh. Chứng minh rằng tồn tại ba đỉnh của hình chóp sao cho chúng là những đỉnh của hình tam giác với các cạnh được tô cùng màu. 14 THOMAS ALVA EDISON Hình 4: Tài năng là 1% trí tuệ, 99% lao động 15