Một số ứng dụng nguyên lý Dirichlet

Nguyên lý Dirichlet còn gọi là "nguyên tắc nhốt thỏ vào lồng", được phát biểu ở dạng đơn giản: "Nếu đem nhốt 3 con thỏ vào 2 chiếc lồng thì phải có một lồng nhốt không ít hơn 2 thỏ". Nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán. Nhiều khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Dirichlet mà bài toán trở nên dễ dàng giải quyết. Mời các bạn cùng tham khảo chi tiết nội dung bài viết!
Nội dung trích xuất từ tài liệu:
Một số ứng dụng nguyên lý Dirichlet Hội thảo Khoa học, Sầm Sơn 28-28/09/2019MỘT SỐ ỨNG DỤNG NGUYÊN LÝ DIRICHLET Nguyễn Đình Thanh Trường THPT Chuyên Lam Sơn, Thanh Hóa Tóm tắt nội dung Nguyên lý Dirichlet còn gọi là nguyên tắc nhốt thỏ vào lồng, được phát biểu ở dạngđơn giản: Nếu đem nhốt 3 con thỏ vào 2 chiếc lồng thì phải có một lồng nhốt khôngít hơn 2 thỏ. Nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại cótác dụng rất lớn trong giải toán. Nhiều khi có những bài toán, người ta đã dùng rấtnhiều phương pháp toán học để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lýDirichlet mà bài toán trở nên dễ dàng giải quyết.1 Nguyên lý Dirichlet Nguyên lý Dirichlet tổng quát được phát biểu như sau: Nếu đem nhốt m × n + r (m, n, r là các số nguyên dương) con thỏ vào n chiếc lồng thìít nhất cũng có một lồng nhốt không ít hơn m + 1 con thỏ. Chứng minh (dùng phương pháp phản chứng): Giả sử ngược lại, mỗi lồng chứakhông quá m con thỏ thì tổng số thỏ sẽ không quá m × n con. Mâu thuẫn với giả thiết làsố thỏ bằng m × n + r. Ưu điểm của nguyên lí Dirichlet là nó cho phép khẳng định đượcsự tồn tại của một đối tượng có tính chất nào đó mà không cần chỉ ra mô hình cụ thể củanó.2 Ứng dụng nguyên lý Dirichlet vào giải toán2.1 Ứng dụng nguyên lý Dirichlet vào giải toán về suy luận logicVí dụ 2.1. Trong một thùng có đựng 105 quả táo, gồm 4 loại. Chứng minh rằng trong sốtáo ấy, bao giờ ta cũng có thể tìm được ít ra 27 quả táo cùng một loại táo nào đó.Lời giải. Trong bài này ta coi nhưquả táo đóng vai trò làthỏ, loại táo đóng vai trò làlồng,Vì: 105 = 26 × 4 + 1, theo nguyên lý Dirichlettìm được một loại táo có ít nhất có 26 + 1 =27 quả.Ví dụ 2.2. Trong 1 lớp học có 30 học sinh. Chứng tỏ rằng trong số học sinh ta sẽ tìm thấy2 học sinh có tên bắt đầu bằng một chữ cái giống nhau.Lời giải. Bảng chữ cái Tiếng Việt gồm 29 chữ cái, trong lúc đó số học sinh lớn hơn, những30 em. Ở đây, các chữ cái đóng vai trò các lồng, còn các bạn học sinh đóng vai trò các chúthỏ mà ta phải nhốt vào lồng,vì số thỏ lớn hơn số lồng nên ta sẽ tìm được ít nhất một 1 Hội thảo Khoa học, Sầm Sơn 28-28/09/2019lồng nhốt nhiều hơn 1 chú thỏ, tức là tìm được ít nhất 2 học sinh có tên bắt đầu cùng mộtchữ cái.Ví dụ 2.3. Một lớp học có 30 học sinh. Khi viết chính tả, em A phạm 14 lỗi, các em khácphạm ít lỗi hơn. Chứng minh rằng có ít nhất là 3 học sinh không mắc lỗi hoặc mắc số lỗibằng nhau.Lời giải. Ta phân lớp học thành 15 nhóm (ta coi như thỏ là học sinh, lồng là nhóm): Nhóm 1: Gồm các em mắc 1 lỗi. Nhóm 2: Gồm các em mắc 2 lỗi. ... Nhóm 14: Gồm các em mắc 14 lỗi. Nhóm 15: Gồm các em không mắc lỗi. Theo giả thiết ta cóNhóm 14 chỉ có em A. Còn lại 14 nhóm chứa 29 em. Vì 29 =2 × 14 + 1, theo nguyên lý Dirichlet tồn tại một nhóm chứa ít nhất 2 + 1 = 3 em. Từ đócó điều phải chứng minh.Ví dụ 2.4. Có 15 đội bóng tham dự một giải đấu theo thể thức đấu vòng tròn một lượt.Chứng minh rằng tại bất kì thời điểm nào của giải ta luôn tìm được 2 đội có cùng số trậnđã đấu bằng nhau tại thời điểm đó (có thể là 0 trận).Lời giải. Số trận đã đấucủa mỗi đội có thể nhận 15 giá trị khác nhau: 0; 1; 2; . . . , 14.Trongtrường hợp này không thể áp dụng ngay nguyên lý Dirichlet được vì số đội cũng là 15. Hai trường hợp 0 trận và 14 trận không thể xảy ra đồng thời vì nếu có một đội nàochưa đấu trận nào thì đồng thời không thể có một đội nào đó đã đấu hết 14 trận, ngượclại nếu có một đội đã đá 14 trận thì không thể có 1 đội chưa đá một trận nào. Vì vậy sốtrận đã đấu của mỗi đội trong thực tế có thể nhận 14 giá trị từ 0 đến 13 hoặc từ 1 đến14.Khi đó theo nguyên lý Dirichlet ta luôn có thể tìm được hai đội có cùng số trận đãđấu.2.2 Ứng dụng nguyên lý Dirichlet vào giải toán Số họcVí dụ 2.5. Chứng minh rằng từ 52 số nguyên bất kỳ luôn có thể chọn ra hai số mà tổnghoặc hiệu của chúng chia hết cho 100Lời giải. Tất cả các số dư trong phép chia cho 100 được chia thành 51 nhóm như sau:{0} , {1; 99} , {2; 98} , . . . , {49; 51} , {50}. Có 52 số nên theo nguyên lý Dirichlet có hai sốmà các số dư khi chia cho 100 thuộc cùng một nhóm trên. Hai số này có hiệu chia hếtcho 100 (nếu số dư của chúng bằng nhau) hoặc có tổng chia hết cho 100 (nếu số dư củachúng khác nhau).Ví dụ 2.6. Chứng minh rằngtồn tại số tự nhiên có tất cả các chữ số bằng 1, chia hết cho2019Lời giải. Xét dãy số hữu hạn:1; 11; 111; . . . ; 111 | {z. . . 1} 2020 s`e 1 Dãy này có 2020 số hạng khác nhau,lấy 2020 số này chia cho 2019 ta được các phần dưthuộc tập hợp có 2019 phần tử sau: {0; 1; 2; . . . ; 2018}. ...