Title CHUYÊN ĐỀ 26 - ỨNG DỤNG NGUYÊN LÝ DIRICHLET.pdf ✅

CHỦ ĐỀ ÔN THI HSG 7 – MỚI 0386536670 1 SẢN PHẨM CỦA: CỘNG ĐỒNG GV TOÁN VN – NGUYỄN HỒNG ỨNG DỤNG NGUYÊN LÝ DIRICHLET I. TÓM TẮT LÍ THUYẾT. - Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim. - Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau: Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng. - Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n. - Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m cái chuồng thì tồn tại một chuồng có ít nhất n m 1 m         con thỏ . * Một số chú ý: 1. Các bài toán áp dụng nguyên tắc Đirichle thường là các bài toán chứng minh sự tồn tại của sự vật, sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc đó. 2. Nhiều bài toán, nguyên tắc Đirichle chỉ xuất hiện sau khi biến đổi qua một bước trung gian, hoặc thành lập các dãy số mới. 3. Để giải bài toán áp dụng nguyên tắc Đirichle, nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng. 4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Đirichle hoặc dự đoán sẽ phải dùng nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và "lồng", khái niệm "nhốt thỏ vào lồng" và thỏa mãn các điều kiện: + Số thỏ phải nhiều hơn số lồng. + Thỏ phải được nhốt hết vào các lồng, nhưng không bắt buộc lồng nào cũng phải có thỏ. 5. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Đirichle. 6. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường. 7. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra được các bài toán tổng quát hơn hoặc cụ thể hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà mình đã làm. II.CÁC DẠNG BÀI TẬP: DẠNG 1. SỰ TƯƠNG HỖ Bài 1. Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.
CHỦ ĐỀ ÔN THI HSG 7 – MỚI 0386536670 2 SẢN PHẨM CỦA: CỘNG ĐỒNG GV TOÁN VN – NGUYỄN HỒNG Phân tích: Ta thành lập được các cái lồng đó là các lồng chứa số trận đã đấu của các đấu thủ (có 4 lồng), số đấu thủ ta coi là các con thỏ. Lời giải Gọi 5 lồng 0,1, 2,3, 4 thứ tự chứa các đấu thủ đã đấu 0,1, 2,3, 4 trận. Cũng chú ý rằng hai lồng 0 và 4 không thể cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, tồn tại 2 người trong cùng một lồng tức là tồn tại hai đấu thủ có số trận đấu bằng nhau. Bài 2. Cho 5 người tùy ý. CMR trong số đó có ít nhất 2 người có số người quen như nhau (hiểu rằng A quen B thì B quen A). Phân tích: Chú trọng đến câu hỏi “ 2 người có số người quen như nhau” Từ đó hiểu rằng 5 người đóng vai trò là số thỏ. Ta có thể tạo ra các lồng như sau: Lồng 1 chứa số người không quen ai, lồng 2 chứa số người có số người quen là 1,... Lời giải Gọi lồng 0 chứa những người có số người quen là 0 . Gọi lồng 1 chứa những người có số người quen là 1. ... Gọi lồng 4 chứa những người có số người quen là 4 . Như vậy ta có 5 lồng. Nếu lồng 0 có chứa ai đó thì lồng 4 phải trống. Ngược lại nếu lồng 4 có chứa ai đó thì lồng 0 phải trống. Vậy thực chất chỉ có 4 lồng nhốt 5 thỏ nên có ít nhất 2 người ở cùng một phòng tức là hai người đó có số người quen như nhau. Bài 3. Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lúc nào cũng có hai đội đã đấu số trận như nhau (kể cả số trận đấu là 0). Phân tích: Hiểu tương tự như bài toán trên. Lời giải Gọi A0 là phòng chứa các đội có số trận đấu là 0 . Gọi A1 là phòng chứa các đội có số trận đấu là 1. ... Gọi A9 là phòng chứa các đội có số trận đấu là 9 . Nếu phòng A0 có ít nhất 1 đội thì phòng A9 không có đội nào và ngược lại phòng A9 có ít nhất 1 đội thì phòng A0 không có đội nào. Vậy thực chất chỉ có 9 phòng được sử dụng mà lại có 9 đội nên có ít nhất 2 đội vào chung một phòng hay có ít nhất 2 đội có cùng số trận đấu như nhau. Bài 4. Có 6 đội bóng thi đấu với nhau (mỗi đội phải đấu 1 trận với 5 đội khác). CMR vào bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào.
CHỦ ĐỀ ÔN THI HSG 7 – MỚI 0386536670 3 SẢN PHẨM CỦA: CỘNG ĐỒNG GV TOÁN VN – NGUYỄN HỒNG Phân tích: Coi 6 đội bóng là 6 con thỏ vậy ta tìm cách thành lập các lồng. Vì bài toán yêu cầu tận 3 đội tức 3 con thỏ trong một lồng nên trước tiên ta cần chọn ra 1 con thỏ rồi xét các con thỏ khác cùng tính chất (đã đấu hay chưa đấu) với con thỏ đã chọn. Như vậy, khi đó ta tạo ra các lồng như sau : Lồng 1 chứa các đội chưa đấu với đội chọn ra trận nào, lồng 2 chứa các đội đã đấu với đội đã chọn. Lời giải Giả sử 6 đội bóng đó là A B C D E F , , , , , . Xét đội A: Theo nguyên lý Dirichlet ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác. Không mất tính tổng quát, giả sử A đã đấu với B C D , , . + Nếu B C D , , từng cặp chưa đấu với nhau thì bài toán được chứng minh. + Nếu B C D , , có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A B C , , từng cặp đã đấu với nhau. Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau trận nào. Bài 4. Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2 và chỉ có 2 học sinh được điểm 10 . Chứng minh rằng ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau ( điểm kiểm tra là một số tự nhiên từ 0 đến 10). Lời giải Số học sinh có điểm kiểm tra từ 2 đến 9 là : 45 – 2 43  Ta có : 43 8.5 3   Như vậy , khi phân chia 43 học sinh vào 8 loại điểm kiểm tra ( từ 2 đến 9 ) thì theo nguyên lí Dirichlet luôn tồn tại ít nhất 5 1 6   học sinh có điểm kiểm tra giống nhau (đpcm ) Bài 5. Có 17 nhà toán học trao đổi với nhau về 3 vấn đề. Mỗi người tra đổi với một người về 1 vấn đề. CMR cũng có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề (I và II, II và III, III và I). Phân tích: Tương tự như 17 điểm được nối với nhau bằng 3 màu à luôn tồn tại một tam giác với 3 cạnh cùng màu tức là 3 nhà toán học trao đổi với nhau về cùng một vấn đề. Lời giải Một nhà toán học trao đổi với 16 nhà toán học khác về 3 vấn đề nên theo nguyên lý Dirichlet có ít nhất 6 người sẽ được một người trao đổi về cùng một vấn đề, giả sử đó là vấn đề I. 6 người này lại trao đổi với nhau về 3 vấn đề: + TH1: Nếu có 2 người nào đó cùng trao đổi về vấn đề I thì bài toán được chứng minh. + TH2: Nếu không có 2 người nào cùng trao đổi về vấn đề 1 thì 6 người này chỉ trao đổi về 2 vấn đề II và III. Một người trao đổi với 5 người còn lại về 2 vấn đề II và III. Theo nguyên lý Dirichlet có ít nhất 3 người cùng được một người trao đổi về 1 vấn đề, giả sử đó là vấn đề II. Ba người này lại tiếp tục trao đổi với nhau: + TH1: Nếu có 2 người nào đó cùng trao đổi với nhau về vấn đề II thì bài toán được chứng minh.