Tiêu đề HSG T7 - CĐ16 - ỨNG DỤNG NGUYÊN LÍ DIRCHLET (20 TRANG).pdf ✅

ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. 1 CHUYÊN ĐỀ 16: Ứ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ẠNG1.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. 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ỏ.
ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. 2 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. 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.
ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. 3 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. + TH2: Nếu không có 2 người nào cùng trao đổi với nhau về vấn đề II thì cả 3 người này trao đổi với nhau về vấn đề III suy bài toán cũng đã được chứng minh. Vậy luôn có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề
ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. 4 DẠNG 2. SỰ SẮP XẾP Bài 1. Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh rằng tồn tại hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc bằng 3. Phân tích:Vì yêu cầu liên quan đến hiệu hai ô cạnh nhau (hiệu 2 số trong hai ô) nên ta coi số các hiệu có thể của hai ô cạnh nhau là số thỏ, số các cặp ô cạnh nhau từ ô ghi số 1 đến ô ghi số 16 là các lồng. Lời giải Xét hàng có ô ghi số 1 và cột có ô ghi số 16. Hiệu giữa hai số này là 15 (coi như là 15 thỏ). Số cặp ô kề nhau từ ô ghi số 1 đến ô ghi số 16 nhiều nhất là 6 (gồm 3 cặp ô chung cạnh tính theo hàng và 3 cặp ô chung cạnh tính theo cột) (coi như có 6 lồng). Ta có: 15 6.2 3.   Vậy theo nguyên lý Dirichlet luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không nhỏ hơn 3. Cách khác: Chuyển từ một ô bất kì sang ô kề nó gọi là một bước. Xét hai ô ghi số 1 và số 16 chuyển từ ô ghi số 1 đến ô ghi số 16 chỉ cần không quá 6 bước chuyển (nhiều nhất là 3 bước theo hàng ngang, 3 bước theo hàng dọc). Tồn tại một bước chuyển có hiệu lớn hơn hoặc bằng 3. Thật vậy giả sử tất cả các bước chuyển đều nhỏ hơn hoặc bằng 2 thì từ số 1, qua không quá 6 bước chuyển tăng thêm không quá 12, không đạt được đến số 16. Vậy tồn tại hai ô kề nhau có hiệu các số của hai ô đó lớn hơn hoặc bằng 3. Bài 2.Viết 16 số, mỗi số có giá trị bất kỳ là 1,2,3,4 . Ghép thành từng cặp 2 số được 8 cặp số. Chứng minh rằng tồn tại hai cặp số mà tồng các số trong hai cặp đó bằng nhau. Phân tích: Ta sắp xếp các tổng của các cặp theo thứ tự từ lớn đến bé thì lớn nhất là 8 còn bé nhất là 2 được dãy các tổng 2,3,4,5,6,7,8 . Ta coi các tổng này là các lồng, còn các con thỏ là các cặp có thể. Lời giải Tổng hai số của mỗi cặp trong 8 cặp số có giá trị nhỏ nhất là: 1 1 2   , có giá trị lớn nhất là: 4 4 8   . Như vậy 8 tổng đó nhận 7 giá trị: 2,3,4,5,6,7,8 . Theo nguyên lý Dirichlet, tồn tại hai tổng bằng nhau, tức là tồn tại hai cặp có tổng bằng nhau. Bài 3.Người ta chia một hình vuông thành 16 hình vuông nhỏ bằng cách chia mỗi cạnh thành 4 phần bằng nhau. Người ta viết vào mỗi ô của bảng một trong các số a a ; 0; sau đó tính tổng các số theo từng cột, từng hàng và từng đường chéo. Chứng minh rằng trong tất cả các tổng đó luôn tồn tại 2 tổng có giá trị bằng nhau. Phân tích:Có bao nhiêu tổng theo cột, theo hàng, theo đường chéo đó chính là “số thỏ”. Mỗi tổng có thể có giá trị bao nhiêu. Số giá trị của tổng sẽ là số “lồng”. Lời giải