Nguyên lý Dirichlet do nhà Toán học người Đức đưa ra được áp dụng phổ biến trong nhiều bài toán thi học sinh giỏi từ lớp 1 đến lớp 12. Trong bài viết này hệ thống giáo dục Vinastudy.vn sẽ hướng dẫn cách giải bài toán nguyên lý Dirichlet . Kính mời quý phụ huynh, thầy cô và các em học sinh cùng tham khảo !
Nguyên lí Dirichlet được phát biểu như sau: Nếu nhốt hết 5 con thỏ vào 4 cái chuồng thì luôn có ít nhất hai con thỏ bị nhốt trong cùng một chuồng. Mở rộng: Nếu nhốt hết $m$ con thỏ vào $n$ cái chuồng thì luôn tồn tại một chuồng nhốt ít nhất là $1+\left[ \frac{m-1}{n} \right]$ con thỏ. (với $\left[ \frac{m-1}{n} \right]$ là phần nguyên của $m-1$ chia cho $n$ )
Bài 1: Một hội nghị có 52 đại biểu được ngồi vào 10 dãy ghế. Chứng minh rằng tồn tại một dãy ghế có số đại biểu ngồi lớn hơn hoặc bằng 6. Bài giải: Theo nguyên lí Dirichlet, tồn tại một dãy ghế có số đại biểu ngồi không ít hơn: $\left[ \frac{52}{10} \right]+1=6$ Bài 2. Phòng họp có 10 người tùy ý. Chứng minh luôn có ít nhất 2 người có số người quen bằng nhau. Bài giải: có 10 người nên số người quen nhiều nhất của mỗi người là 9. Phòng 0: chứa những người không có người quen. Phòng 1: chứa những người có 1 người quen. ………………………………………………………………… Phòng 9: chứa những người có 9 người quen. Để ý rằng phòng 0 và phòng 9 không thể cùng có người. Thực chất 10 người chứa trong phòng 9. Theo nguyên lí dirichlet tồn tại ít nhất $1+\frac{10-1}{9}=2$ người. từ đó có điều phải chứng minh. Bài 3: Một hội nghị có $n$ người tham dự ($n\ge 2$). Chứng minh rằng luôn tồn tại hai người có số người quen bằng nhau. Bài giải: có $n$ người nên số người quen nhiều nhất của mỗi người là $n-1$ . Phòng 0: chứa những người không có người quen. Phòng 1: chứa những người có 1 người quen. ………………………………………………………………… Phòng $n-1$: chứa những người có $n-1$ người quen. Để ý rằng phòng 0 và phòng $n-1$ không thể cùng có người. Thực chất $n$ người chứa trong phòng $n-1$. Theo nguyên lí dirichlet tồn tại ít nhất $1+\frac{n-1}{n-1}=2$ người. từ đó có điều phải chứng minh. Bài 4. Một lớp có 30 học sinh. Khi viết chính tả, em A phạm 14 lỗi, các em khác phạm ít hơn, chứng minh có ít nhất 3 học sinh không mắc lỗi hoặc mắc số lỗi bằng nhau. Bài giải: giả sử: Phòng 1: chứa các em mắc 1 lỗi Phòng 2: chứa các em mắc 2 lỗi …………………………………………….. Phòng 14: chứa các em mắc 14 lỗi Phòng 15: chứa các em không mắc lỗi. Theo giả thiết phòng 14 chỉ có em A. suy ra còn lại 14 phòng chứa 29 em. Theo nguyên lí Dirichlet tại một phòng chứa ít nhất $1+\frac{29-1}{14}=3$ em. Ta suy ra điều phải chứng minh. Bài 5. Trong một giải bóng đá có 10 đội tham gia, biết cứ hai đội nào trong số đó cũng đấu với nhau một trận. Chứng minh tại bất kì thời điểm nào cũng có hai đội đã đấu một số trận như nhau. Bài giải: Xét một thời điểm bất kì của lịch thi đấu ( mỗi đội thi đấu tối đa 9 trân) Phòng 0: chứa các đội chưa đấu trận nào. Phòng 1: chứa các đội đã thi đấu 1 trận. ………………………………………………………… Phòng 9: chứa các đội đã thi đấu 9 trận. Để ý rằng phòng 0 và phòng 9 không thể có cùng đội thi đấu. Thực chất 10 đội chứa trong 9 phòng. Theo nguyên lí Drichlet suy ra tại một thời điểm bất kì nào cũng có 2 đội có số trận đấu như nhau. Bài 6: Cho 5 số dương đôi một khác nhau sao cho mỗi số không có ước nguyên tố nào khác 2 và 3. Chứng minh rằng trong 5 số đó tồn tại hai số mà tích của chúng là một số chính phương. (Đề thi vòng 2, THPT Chuyên Đại học Sư Phạm, năm học 2012 – 2013) Bài giải: Gọi các số đã cho là ${{a}_{1}};{{a}_{2}};{{a}_{3}};...;{{a}_{5}}$ với ${{a}_{i}}={{2}{{{x}_{i}}}}{{.3}{{{y}_{j}}}}$ (${{x}_{i}};{{y}_{i}}\in N$) Trong 5 cặp số $\left( {{x}_{1}},{{y}_{1}} \right);....;\left( {{x}_{5}},{{y}_{5}} \right)$ , mỗi cặp số thuộc một trong bốn dạng: (chẵn, chẵn); (chẵn, lẻ); (lẻ, chẵn); (lẻ, lẻ) Theo nguyên lí Dirichlet tồn tại $\left[ \frac{5-1}{4} \right]+1$ = 2 cặp số cùng dạng. TH1: Giả sử 2 cặp số $\left( {{x}_{1}},{{y}_{1}} \right);\left( {{x}_{2}},{{y}_{2}} \right)$ cùng dạng (chẵn, chẵn) $\Rightarrow $ ${{x}_{1}}+{{x}_{2}}$ và ${{y}_{1}}+{{y}_{2}}$ đều là các số chẵn. TH2: Giả sử 2 cặp số $\left( {{x}_{1}},{{y}_{1}} \right);\left( {{x}_{2}},{{y}_{2}} \right)$ cùng dạng (chẵn, lẻ) $\Rightarrow $ ${{x}_{1}}+{{x}_{2}}$ và ${{y}_{1}}+{{y}_{2}}$ đều là các số chẵn. TH3: Giả sử 2 cặp số $\left( {{x}_{1}},{{y}_{1}} \right);\left( {{x}_{2}},{{y}_{2}} \right)$ cùng dạng (lẻ, chẵn) $\Rightarrow $ ${{x}_{1}}+{{x}_{2}}$ và ${{y}_{1}}+{{y}_{2}}$ đều là các số chẵn. TH4: Giả sử 2 cặp số $\left( {{x}_{1}},{{y}_{1}} \right);\left( {{x}_{2}},{{y}_{2}} \right)$ cùng dạng (lẻ, lẻ) $\Rightarrow $ ${{x}_{1}}+{{x}_{2}}$ và ${{y}_{1}}+{{y}_{2}}$ đều là các số chẵn. Vậy ${{x}_{1}}+{{x}_{2}}$ và ${{y}_{1}}+{{y}_{2}}$ đều là các số chẵn nên ${{a}_{1}}{{a}_{2}}={{2}{{{x}_{1}}+{{x}_{2}}}}{{.3}{{{y}_{1}}+{{y}_{2}}}}$ là số chính phương. (vì số chính phương có các thừa số nguyên tố với số mũ chẵn). Bài 7. Chứng minh đối với một số n nguyên dương bất kì bao giờ cũng tìm được một số tự nhiên mà các chữ số của nó chỉ gồm có chữ số 5 và chữ số 0 và chia hết cho n. Bài giải: xét n + 1 số sau: ${{a}_{1}}=5;{{a}_{2}}=55;...;{{a}_{n+1}}=55...5$(n + 1 chữ số 5). Theo nguyên lí Dirichlet: với n + 1 số trên sẽ tồn tại hai số có cùng số dư khi chia cho n. Hiệu của hai số này là số có dạng: 55…50…0 gồm toàn chữ số 0 và chia hết cho n ( điều phải chứng minh). |
