Nguyên tắc Đi-rích-lê được phát biểu dưới dạng bài toán như sau:
Nếu đem m thỏ vào n lồng với $m>n$ thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ. Tương tự, nếu đem m đồ vật vào n ô ngăn kéo, với $m>n$, thì ít nhất cũng phải có 1 ô ngăn kéo chứa không ít hơn 2 đồ vật
Phần chứng minh bài toán, các bạn chắc gần như ai cũng biết, mình chỉ xin nêu một vài bài toán vận dụng cơ bản.
Ví dụ 1:
Trong một lớp chuyên toán có 40 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít nhất cũng có 8 em có điểm số như nhau, biết rằng điểm số các em đều là các số nguyên.
Lời giải:
Theo giả thiết của bài toán thì chỉ có một em đạt điểm 10 và một em đạt điểm 4, do đó sẽ có $40-2=38$ em đạt điểm 5 đến điểm 9. Coi mỗi học sinh là một "thỏ", mỗi loại điểm là 1 "lồng", như vậy ta sẽ có các lồng sau:
"Lồng 5": nhốt những ai đạt điểm 5
"Lồng 6": nhốt những ai đạt điểm 6
"Lồng 7": nhốt những ai đạt điểm 7
"Lồng 8": nhốt những ai đạt điểm 8
"Lồng 9": nhốt những ai đạt điểm 9
Với 5 lồng nhốt 38 thỏ, vậy có ít nhất một lồng nhốt không ít hơn 8 thỏ, bài toán được chứng minh.
Ví dụ 2:
Cho 10 số tự nhiên bất kì: $a_{1},a_{2},a_{3},...,a_{9},a_{10}$
Chứng minh rằng thế nào cũng có một số hoặc tổng một số số liên tiếp nhau trong dãy 10 số đã cho chia hết cho 10.
Lời giải:
Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới sau đây:
Đặt $B_{1}=a_{1}$
$B_{2}=a_{1}+a_{2}$
$B_{3}=a_{1}+a_{2}+a_{3}$
...
$B_{10}=a_{1}+...+a_{10}$
Ta thấy rằng:
- Nếu tồn tại một $B_{i}$ nào đó ($i=1,2,3,4,...,10$) chia hết cho 10 thì bài toán đã được chứng minh
- Nếu không tồn tại một $B_{i}$ nào đó chia hết cho 10 thì ta chỉ việc đem tất cả $B_{i}$ chia cho 10, lúc đó được 10 số dư từ 1 đến 9, trong khi đó các số tự nhiên từ 1-9 chỉ có 9 số (như vậy tương đương với việc nhốt 10 chủ thỏ vào 9 lồng), theo nguyên tắc Đi-rích-lê, tồn tại 1 lồng nhốt không ít hơn 2 chú thỏ, tương đương với việc tồn tại hai số có cùng số dư, như vậy có hiệu chia hết cho 10, bài toán được chứng minh
Các ví dụ:
A.Các bài toán số học:
1. Toán suy luận:
Ví dụ 1: 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.
GIẢI: Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào đã thi đấu 9 trận như vậy 10 đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9. Vậy theo nguyên lý Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.
Ví dụ 2: 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.
GIẢI: Giả sử 6 đội bóng đó là A,B,C,D,E,F. Xét đội A.
Theo nguyên lý Đirichlê 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.
Ví dụ 3: CMR trong n người bất kì, tồn tại hai người có số người quen như nhau (kể cả trường hợp quen 0 người)
GIẢI: Tương tự ví dụ 1, ta xét n nhóm...
Ví dụ 4: Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10. CMR í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)
GIẢI: Có 43 học sinh phân chia vào 8 loại điểm (từ 2 đến 9). Giả sử mỗi loại trong 8 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có không quá 5.8=40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có điểm kiểm tra bằng nhau.
2.Sự chia hết:
Trong các phép tính trên số nguyên thì phép chia là rất đặc biệt.Phép chia có hàng loạt các tính chất mà các phép còn lại không có. Ví dụ các phép toán cộng , trừ , nhân đều thực hiện với số 0 còn phép chia thì không thể.Vì những lí do đặc biệt đó mà trong toán học xây dựng hẳn 1 lý thuyết về phép vchia . Những ví dụ sau có liên quan mật thiết giữa phép chia và nguyên lý Dirchlet
Ví dụ 1: CMR tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2007.
GIẢI: Xét 2008 số có dạng $1,11,...,11...11$. Theo nguyên tắc Ddirrichle thì tồn tại hai số có cùng số dư khi chia cho 2007. Giả sử hai số đó là:
$A=11...1_{n}$ và $B=11...1_{k}$ với k<>
Khi đó $A-B=11...1_{n-k}.10^k$ chia hết cho 2007
Do $(2007,10^k)=1$ nên $C=11...1_{n-k}$ chia hết cho 2007
Ví dụ 2: CMR trong n+1 số bất kì thuộc tập hợp ${1,2,3,...,2n}$ luôn chọn được hai số mà số này là bội của số kia.
GIẢI: Viết n+1 số đã cho dưới dạng:
$a_{1}=2^{k_{1}}b_{1},a_{2}=2^{k_{2}}b_{2},...,a_{n+1}=2^{k_{n+1}}b_{n+1}$
Trong đó $b_{1},b_{2},...,b_{n+1}$ là các số lẻ. Ta có $1\leq b_{1},b_{2},...,b_{n+1} \leq 2n-1$.
Mặt khác trong khoảng từ 1 đến 2n-1 có đúng n số lẻ nên tồn tại hai số $m \leq n$ sao cho $b_{n}=b_{m}$. Khi đó, trong hai số $a_{n}$ và $a_{m}$ có một số là bội của số kia.
Ví dụ 3: Cho 5 số nguyên phân biệt $a_{i}(i=1,2,3,4,5)$. Xét tích:
$P=(a_{1}-a_{2})(a_{1}-a_{3})(a_{1}-a_{4})(a_{1}-a_{5})(a_{2}-a_{3})(a_{2}-a_{4})(a_{2}-a_{5})(a_{3}-a_{4})(a_{3}-a_{5})(a_{4}-a_{5})$
CMR $P$ chia hết cho 288
GIẢI: $288=3^2.2^5$
-Chứng minh P chia hết cho 9.
Xét 4 số $a_{1},a_{2},a_{3},a_{4}$ tồn tại 2 số có cùng số dư khi chia cho 3. Giả sử $a_{1}$ đồng dư $a_{2}$ (mod3) thì $a_{1}-a_{2}$ chia hết cho 3. Lại xét $a_{2},a_{3},a_{4},a_{5}$ trong 4 số này lại tồn tại 2 số có cùng số dư khi chia cho 3. Suy ra P chia hết cho 9.
-Chứng minh P chia hết cho $2^5$
Trong 5 số đã cho có 3 số cùng tính chẵn lẻ.
- Nếu 4 số chẵn, chẳng hạn $a_{1}=2k_{1},a_{2}=2k_{2},a_{3}=2k_{3},a_{4}=2k_{4}$ thì:
$P=32(k_{1}-k_{2})(k_{1}-k_{3})(k_{1}-k_{4})(a_{1}-a_{5})(k_{2}-k_{3})(k_{2}-k_{4})(a_{2}-a_{5})(a_{3}-a_{4})(a_{3}-a_{5})(a_{4}-a_{5})$ chia hết cho 32.
-Nếu có 3 số chẵn, 2 số lẻ thì đặt:
$a_{1}=2k_{1}.a_{2}=2k_{2},a_{3}=2k_{3},a_{4}=2k_{4}+1,a_{5}=2k_{5}+1$
Ta có $P=16(k_{1}-k_{2})(k_{1}-k_{3})(k_{2}-k_{3}).M$
Trong 3 số $k_{1},k_{2},k_{3}$ có 2 số cùng tính chẵn lẻ. Giả sử $k_{1}$ đồng dư $k_{1}$ (mod 2) thì $k_{1} - k_{2}$ chia hết cho 2 nên P chia hết cho 32.
-Nếu có 3 số lẻ thì $a_{1},a_{2},a_{3}$ còn $a_{4},a_{5}$ chẵn thì đặt $a_{1}=2k_{1}+1,a_{2}=2k_{2}+1,a_{3}=2k_{3}+1,a_{4}=2k_{4},a_{5}=2k_{5}$
Xét tương tự cũng có P chia hết cho 32.
Vậy ta có P chia hế cho 288
3. Toán về tổng, hiệu, chữ số tận cùng...các loại:
Ví dụ 1: Cho 51 số nguyên dương khác nhau có 1 chữ số và có 2 chữ số. CMR ta có thể chọn ra 6 số nào đó mà bất cứ 2 số nào trong số đã lấy ra ấy không có chữ số hàng đơn vị giống nhau cũng không có chữ số hàng chục giống nhau.
GIẢI:Vì có 51 số nên tìm được 6 chục sao cho một nhóm có không ít hơn 6 số rơi vào một trong các số chục đó, một nhóm có không ít hơn 5 số rơi vào chục khác... Cuối cùng có ít nhất một trong các số đã cho rơi vào một chục nào đó (như vậy số các chục khác nhau không ít hơn 6) về các số đã cho là khác nhau (chú ý các số dạng xét nhiều nhất có 2 chữ số ) do đó ở nhóm cuối cùng ta lấy một số , sau đó nhóm trước đó (vì có ít nhất 2 chữ số hàng đơn vị của hai số trong nhóm ấy khác nhau) ta lấy một số khác với chữ số hàng đơn vị khác số chọn trước, rồi nhóm trước đó lại lấy 1 số có chữ số hàng đơn vị khác 2 số chọn trước... Cuối cùng sẽ được 6 số phải tìm với các chữ số khác nhau.
Ví dụ 2: Chọn bất kì n+1 số trong 2n số tự nhiên từ 1 đến 2n $(n\geq 2)$. CMR trong các số được chọn có ít nhất 1 số bằng tổng của 2 số được chọn (kể cả các trường hợp 2 số hạng của tổng bằng nhau ).
GIẢI: Giả sử $a_{1} < a_{2} < a_{3} < ... < a_{n} < a_{n+1}$ là $n+1$ số được chọn.
Xét n số: $a_{n+1} -a_{1}=b_{1}$
$a_{n+1} -a_{2}=b_{2}$
... (mỗi hiệu đều nhỏ hơn 2n)
$a_{n+1} -a_{n}=b_{n}$
Trong tập $2n+1$ số đó là $a_{1},a_{2},...,a_{n+1}; b_{1},b_{2},...,b_{n}$ tồn tại 2 số bằng nhau, hai số ấy không thể cùng thuộc dãy $a_{1},a_{2},...,a_{n+1}$ cũng không thể cùng thuộc dãy $b_{1},b_{2},...,b_{n}$. Ta có:
$a_{n+1}-a_{1}=a_{i}$ suy ra $a_{n+1}=a_{1}+a_{i}$ (đpcm)
B. Các bài toán hình học:
1. Đánh giá các điểm, các đường thẳng:
Ví dụ 1: Cho một hình vuông và 13 đường thẳng, mỗi đường thẳng đều chia hình vuông thành hai tứ giác có tỉ số diện tích 2:3. CMR trong số 13 đường thẳng đó, có ít nhất 4 đường thẳng cùng đi qua một điểm.
GIẢI: Gọi d là đường thẳng chia hình vuông ABCD thành hai tứ giác có tỉ số diện tích 2:3. Đường thẳng d không thể cắt hai cạnh kề nhau của hình vuông vì khi đó không tạo thành hai tứ giác. Giả sử d cắt hai cạnh AB và CD tại M và N, khi đó nó cắt đường trung bình EF tại I
Giả sử $S_{AMND} =\frac{2}{3}S_{BMNC}$ thì $EI=\frac{2}{3}IF$
Như vậy mỗi đường thẳng đã cho chia các đường trung bình của hình vuông theo tỉ số 2:3. Có 4 điểm chia các đường trung bình của hình vuông ABCD theo tỉ số 2:3.
Có 13 đường thẳng, mỗi đường thẳng đi qua một trong 4 điểm. Vậy theo nguyên lý Đirichlê có ít nhất 4 đường thẳng đi qua.
Ví dụ 2: Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm. CMR tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5.
GIẢI: Các đường trung bình của tam giác đều cạnh 1 sẽ chia nó ra làm 4 tam giác đều cạnh 0,5. Do đó trong một tam giác nhỏ đó có ít nhất 2 điểm đã cho, và các điểm đó không thể rơi vào các đỉnh của tam giác. Vậy khoảng cách giữa hai điểm đó nhỏ hơn 0,5.
2. Đánh giá góc và độ dài:
Ví dụ 1: Trên mặt phẳng cho n đường thẳng từng đôi một không song song với nhau. CMR góc giữa hai đường thẳng nào đó trong số đó không lớn hơn $\frac{180^{\circ}}{n}$
GIẢI: Lấy trên mặt phẳng một điểm bất kì và kẻ qua đó các đường thẳng song song với các đường thẳng đã cho. Chúng chia mặt phẳng ra làm 2n góc, có tổng các góc bằng $360^{\circ}$. Do đó tồn tại một góc không lớn hơn $\frac{180^{\circ}}{n}$
Ví dụ 2: Bên trong một đường tròn bán kính n đặt 4n đoạn thẳng có có độ dài 1. CMR có thể kẻ một đường thẳng song song hoặc vuông góc với đường thẳng l cho trước và cắt ít nhất hai đoạn thẳng đã cho.
GIẢI: Giả xử $l_{i}$ là đoạn thẳng bất kì vuông góc với l. Kí hiệu độ dài các hình chiếu của đoạn thẳng thứ i lên các đường thẳng I và $l_{1}$ là $a_{i}$ và $b_{i}$ tương ứng vì độ dài của mỗi đoạn thằng bằng 1 nên $a_{i} + b_{i} \geq 1$. Do đó
$(a_{1}+...+a_{4n}) + (b_{1}+...+b_{4n}) \geq 2n$. Không mất tính tổng quát giả sử $a_{1}+...+a_{4n} \geq b_{1}+...+b_{4n}$. Khi đó $a_{1}+...+a_{4n} \geq 2n$. Tất cả các đoạn thẳng đã cho đều được chiếu xuống đoạn thẳng có độ dài 2n, vì chúng đều nằm trong đường tròn bán kính n.Nếu như các hình chiếu của các đoạn thẳng đã cho lên đường thẳng l không có điểm chung, thì sẽ có $a_{1}+...+a_{4n} < 2n$. Do đó trên l phải có một điểm bị các điểm của ít nhất 2 trong số các đoạn thẳng đã cho chiếu lên nó. Đường vuông góc với l tại điểm đó sẽ cắt ít nhất hai đoạn thẳng đã cho.
3. Các bài toán về tô màu
Bài 1 : Giả sử mỗi điểm trong mặt phẳng được tô bằng một trong 2 màu đỏ và xanh
Chứng minh tồn tại 1 hình chữ nhật có các đỉnh cùng màu
Giải : Giả sử ta có một lưới ô vuông tạo bởi 3 đường nằm ngang và 9 đường thẳng đứng , mỗi nút lưới được tô bởi một màu xanh hoặc đỏ.
Xét 3 nút lưới của một đường dọc , mỗi nút có hai cách tô màu nên mỗi bộ ba nút trên đường dọc ấy có 2.2.2=8 cách tô màu.
Có 9 đường dọc, mỗi đường có 8 cách tô màu nên tồn tại hai đường có cách tô màu như nhau.
Chẳng hạn hai bộ ba điểm đó là $A_{1}, A_{2}, A_{3}$ và $B_{1}, B_{2}, B_{3}$
3 điểm $A_{1}, A_{2}, A_{3}$ chỉ được tô bởi hai màu nên tồn tại hai điểm cùng màu, chẳng hạn $A_{1}$ và $A_{2}$, khi đó hình chữ nhật
$A_{1}A_{2}B_{2}B_{1}$ có 4 đỉnh cùng một màu.
Bài 2 :Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng.Chứng minh rằng với cách sơn màu bất kì ,trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu
Lời giải :
Mẫu sơn màu có thể xảy ra với bàn cờ này có dạng từ 1 đến 8.Giả sử một trong số các cột thuộc dạng 1.Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1,2,3 hoặc 4.Giả sử tất cả các cột còn lại thuộc dạng 5,6,7,8 Khi đó theo nguyên lí Dirichlet 2 trong số 6 cột có 2 cột cùng 1 dạng và như vậy bài toán cũng được chứng minh
Chứng minh hoàn toàn tương tự nếu 1 cột có dang 8 .Giả sử không có cột nào trong các cột 1,8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng và bài toán cũng đựoc chứng minh
4.Nguyên lý Dirichlet cho diện tích
Nếu A là một bề mặt và $A_{1}, A_{2},..., A_{n}$ là các bề mặt sao cho $A_{i} \subset A_{n} và S(A) < S(A_{1}) +S(A_{2})+...+S(A_{n})$ thì ít nhất có 2 bề mặt trong số các bề mặt thì trên có điểm trong chung
Cụ thể hoá
1.Cho những đoạn thẳng $\bigtriangleup _{1},\bigtriangleup _{2},...,\bigtriangleup _{n}$ nằm trong đoạn $\bigtriangleup$ và tổng độ dài của $\bigtriangleup _{1},\bigtriangleup _{2},...,\bigtriangleup _{n}$ lớn hơn độ dài của $\bigtriangleup$. Khi đó ít nhất 2 trong số những đoạn $\bigtriangleup _{1},\bigtriangleup _{2},...,\bigtriangleup _{n}$ có điểm trong chung
2. Cho những đa diện $P_{1},P_{2},...,P_{n}$ nằm trong đa diện P và tổng thể tích của $P_{1},P_{2},...,P_{n}$ lớn hơn thể tích của P. Khi đó ít nhất 2 trong số những đa diễn $P_{1},P_{2},...,P_{n}$ có điểm trong chung
3. Cho những cung $C_{1},C_{2},...,C_{n}$ nằm trên đường tròn C và tổng độ dài của $C_{1},C_{2},...,C_{n}$ lớn hơn C. Khi đó ít nhất 2 trong số những cung $C_{1},C_{2},...,C_{n}$ có điểm trong chung
