"nếu
nhốt vào n chiếc lồng một số chú thỏ mà số lượng lớn hơn n thì ta sẽ
tìm được một chiếc lồng mà trong đó có nhiều hơn một chú thỏ ".
Nguyên tắc Dirichlet,đôi lúc người ta cũng gọi là nguyên tắc chuồng thỏ hoặc nguyên tắc chim bồ câu.
Người ta cũng phát biểu một Nguyên tắc DIRICHLET mở rộng như sau:nếu như trong n lồng,ta nhố một số thỏ nhiều hơn k.n con thỏ (k thuộc n) thì chắc chắn sẽ có một lồng nhốt nhiều hơn k con thỏ".
Nguyên tắc Dirichlet được sử dụng rông rãi trong việc giải nhiều bài toán!
II.Một ví vụ bài toán Đơn giản Giải bằng nguyên tắc Dirichlet :
Trong
một lớp học có 30 học sinh.Chứng tỏ rằng trong số học sinh sẽ tìm thấy
2(theo nghĩa có ít nhất 2)học sinh có tên bắt đầu bằng một chữ cái giống
nhau.
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ững 30 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
cái lồng nên ta sẽ phải tìm được ít nhất một cái lồng nhiều hơn 1 chú
thỏ ,tức là tìm được ít nhất hai học sinh có tên bắt đầu cùng môt chữ
cái.
Qua nhừng gì mình đã giải thích các cậu chắc đã hiểu thêm nhiều về Nguyên tắc Dirichlet!
!chúc các bạn có nhiều thành công trong những bài toán áp dụng nguyên tắc Dirichlet này chào tạm biết các bạn! 
VD1:
1. CMR: tồn tại một số tự nhiên x<17sao cho (25^x - 1) chia hết cho 17
GIải:
Tất nhiên ta xét x\leq1 vì nếu xét x = 0 thì quá tầm thường.
Ta
xét 16 số (25^k-1) với k = 1, 2, ..., 16. Ta phải CMR với một k
nào đó số 25^k-1 chia hết cho 17. Ta CM bằng phản chứng. Giả sử
với mọi 1 \leq k \leq 16 số (25^k-1)không chia hết cho 17. =>
trong 16 số trên không có 2 số nào cho cùng số dư khi chia cho 17.
Thật thế nếu với 1 \leq i < j \leq 16 có (25^j-1)=17 xa+r và
(25^i-1)=17xb+r
=> 17x(a-b)=(25^j-1)-(25^i-1)=25^iX(25^{j-i}-1)
=> (25^n-1) chia hết cho 17 với n = j - i và 1<n \leq 16-1=15
trái với giả thiết là với mọi k thuộc [1, 16] số (25^k-1) không chia hết cho 17
Vậy
trong 16 số đang xét không có 2 số nào cho cùng số dư khi chia
cho 17 và từ giả thiết không có số nào cho số dư 0 khi chia cho
17. Theo nguyên lý Dirichlet (16 số dư khác nhau được xếp vào 16
ngăn kéo dư khác nhau từ 1 đển 16) thì với n nào đó mà 1 \leq n
\leq 16
có (25^n-1) chia cho 17 dư 16, tức 25^n-1=17xN+16
=> 25^n=17xN+17 => 25^n chia hết cho 17, vô lý vì 25^n chỉ có ước
nguyên tố duy nhất là 5. Vậy giả thiết sai (đ.p.c.m)
Vd2
CHo dãy số 5 số tự nhiên bất kì a1; a2; ....; a5 CMR: tồn tại 1 số chia hết cho 5 hoặc tổng của một số số chia hết cho 5.
Giải:
Ta xét 5 số a1, (a1 + a2), (a1 + a2 + a3), (a1 + a2 + a3 + a4),
(a1
+ a2 + a3 + a4 + a5). Nếu 1 trong 5 số đó chia hết cho 5 ta có
đ.p.c.m. Nếu không có số nào chia hết cho 5 thì theo nguyên lý
Dirichlet ít nhất 2 trong 5 số đó có cùng số dư (có 4 số dư
khác 0 là 1, 2, 3, 4), tức hiệu 2 số đó chia hết cho 5. Mà hiệu 2
số bất kỳ trong 5 số trên cũng là tổng của một số số của dãy
đã cho (đ.p.c.m)
vd3
Ở mỗi ô của 1 hình vuông kích thước 5
nhân 5 ô; Ta viết 1 trong 3 số 0; 1; -1 sao cho mỗi ô vuông có đúng 1
số. CMR trong các tổng của 5 số theo 1 cột; theo 1 hàng; theo mỗi đường
chéo có ít nhất 2 tổng bằng nhau.
giải:
Ta có tổng cộng tất
cả 12 hàng, cột và đường chéo (5 hàng, 5 cột, 2 đường chéo).
Các tổng là những số thỏa mãn -5 \leq tổng \leq 5 (min khi tất
cả các ô = -1, max khi tất cả các ô = 1)
Có 12 tổng và 11
giá trị khác nhau để lấy (-5, ..., 0, ..., 5) vậy theo nguyên lý
Dirichlet phải có ít nhất 2 tổng có cùng giá trị (đ.p.c.m)
vd4
CM
trong 1 hình tròn có bán kính bằng 1, không thể có nhiều hơn 5 điểm có
khoảng cách giữa 2 điểm bất kì trong chúng đều lớn hơn 1
Giải:
Ta
xét 6 điểm trong đường tròn. Ta cmr khoảng cách giữa 2 điểm nào
đó \leq 1. Ta xét điểm P1 trên bán kính OA. Lấy về 1 phía của A
điểm B và C sao cho \hat{AOB} = \hat{AOC} = 60^o. Nếu trong hình
quạt AOB hoặc AOC có 2 điểm đang xét thì dễ thấy chúng cách
nhau một khoảng \leq 1 (đ.p.c.m). Giả sử trong 2 hình quạt trên
không có điểm nào ngoài P1. Ta chia hình quạt lớn BOC thành 4
hình quạt bằng nhau => góc ở tâm của mỗi hình quạt = 60^o.
Ta có 5 điểm còn lại trong 4 hình quạt vậy trong ít nhất 1
hình quạt có 2 điểm đang xét.
Khoảng cách giữa 2 điểm đó không lớn hơn bán kính = 1.
Với
5 điểm dễ thấy là nếu xếp chúng vào 5 đỉnh của hình ngũ
giác đều nội tiếp thì khoảng cách gữa 2 điềm bất kỳ \geq
cạnh của ngũ giác > bán kính = 1 (Ta xét cạnh P1P2. Trong tam
giác OP1P2 cạnh P1P2 đối điện với góc 72^o nên lớn hơn OP1 và
OP2 là những cạnh đối diện với góc 54^o)
VD5
Trên
mặt phẳng, cho 25 điểm phân biệt và trong 3 điểm bất kì, bao giờ cũng
tìm được 2 điểm có khoảng cách giữa chúng <1. Chứng minh rằng, tồn
tại 1 hình tròn có bán kính = 1 chứa không ít hơn 13 điểm như trên.
Giải:
Lấy
điểm P1 là tâm kẻ đường tròn C1 với bán kính = 1. Nếu C1 chứa
25 điểm đã cho thì ta có đ.p.c.m. Giả sử P2 không thuộc C1 tức
P1P2 > 1. Lấy điểm P2 là tâm kẻ đường tròn C2 với bán kính =
1. Ngoài C1 và C2 không còn điểm nào đã cho Thật thế nếu P3
nằm ngoài C1 và C2 thì ta có P1P2 > 1, P1P3 > 1, P2P3 > 1,
vô lý vì trong tam giác P1P2P3 phải có 1 cạnh < 1. 25 điểm
nằm trong 2 đường tròn nên theo nguyên lý Dirichlet trong 1 đường
tròn có ít nhất 13 điểm đã cho.
Nguyên lý dirichlet: Nếu nhốt kn+1 thỏ vào k lồng thì một trong các lồng (tồn tại 1 lồng) chứa ít nhất n+1 thỏ.
1. CMR: tồn tại một số tự nhiên x<17sao cho (25^x - 1) chia hết cho 17
GIải:
Tất nhiên ta xét x\leq1 vì nếu xét x = 0 thì quá tầm thường.
Ta
xét 16 số (25^k-1) với k = 1, 2, ..., 16. Ta phải CMR với một k
nào đó số 25^k-1 chia hết cho 17. Ta CM bằng phản chứng. Giả sử
với mọi 1 \leq k \leq 16 số (25^k-1)không chia hết cho 17. =>
trong 16 số trên không có 2 số nào cho cùng số dư khi chia cho 17.
Thật thế nếu với 1 \leq i < j \leq 16 có (25^j-1)=17 xa+r và
(25^i-1)=17xb+r
=> 17x(a-b)=(25^j-1)-(25^i-1)=25^iX(25^{j-i}-1)
=> (25^n-1) chia hết cho 17 với n = j - i và 1<n \leq 16-1=15
trái với giả thiết là với mọi k thuộc [1, 16] số (25^k-1) không chia hết cho 17
Vậy
trong 16 số đang xét không có 2 số nào cho cùng số dư khi chia
cho 17 và từ giả thiết không có số nào cho số dư 0 khi chia cho
17. Theo nguyên lý Dirichlet (16 số dư khác nhau được xếp vào 16
ngăn kéo dư khác nhau từ 1 đển 16) thì với n nào đó mà 1 \leq n
\leq 16
có (25^n-1) chia cho 17 dư 16, tức 25^n-1=17xN+16
=> 25^n=17xN+17 => 25^n chia hết cho 17, vô lý vì 25^n chỉ có ước
nguyên tố duy nhất là 5. Vậy giả thiết sai (đ.p.c.m)
Vd2
CHo dãy số 5 số tự nhiên bất kì a1; a2; ....; a5 CMR: tồn tại 1 số chia hết cho 5 hoặc tổng của một số số chia hết cho 5.
Giải:
Ta xét 5 số a1, (a1 + a2), (a1 + a2 + a3), (a1 + a2 + a3 + a4),
(a1
+ a2 + a3 + a4 + a5). Nếu 1 trong 5 số đó chia hết cho 5 ta có
đ.p.c.m. Nếu không có số nào chia hết cho 5 thì theo nguyên lý
Dirichlet ít nhất 2 trong 5 số đó có cùng số dư (có 4 số dư
khác 0 là 1, 2, 3, 4), tức hiệu 2 số đó chia hết cho 5. Mà hiệu 2
số bất kỳ trong 5 số trên cũng là tổng của một số số của dãy
đã cho (đ.p.c.m)
vd3
Ở mỗi ô của 1 hình vuông kích thước 5
nhân 5 ô; Ta viết 1 trong 3 số 0; 1; -1 sao cho mỗi ô vuông có đúng 1
số. CMR trong các tổng của 5 số theo 1 cột; theo 1 hàng; theo mỗi đường
chéo có ít nhất 2 tổng bằng nhau.
giải:
Ta có tổng cộng tất
cả 12 hàng, cột và đường chéo (5 hàng, 5 cột, 2 đường chéo).
Các tổng là những số thỏa mãn -5 \leq tổng \leq 5 (min khi tất
cả các ô = -1, max khi tất cả các ô = 1)
Có 12 tổng và 11
giá trị khác nhau để lấy (-5, ..., 0, ..., 5) vậy theo nguyên lý
Dirichlet phải có ít nhất 2 tổng có cùng giá trị (đ.p.c.m)
vd4
CM
trong 1 hình tròn có bán kính bằng 1, không thể có nhiều hơn 5 điểm có
khoảng cách giữa 2 điểm bất kì trong chúng đều lớn hơn 1
Giải:
Ta
xét 6 điểm trong đường tròn. Ta cmr khoảng cách giữa 2 điểm nào
đó \leq 1. Ta xét điểm P1 trên bán kính OA. Lấy về 1 phía của A
điểm B và C sao cho \hat{AOB} = \hat{AOC} = 60^o. Nếu trong hình
quạt AOB hoặc AOC có 2 điểm đang xét thì dễ thấy chúng cách
nhau một khoảng \leq 1 (đ.p.c.m). Giả sử trong 2 hình quạt trên
không có điểm nào ngoài P1. Ta chia hình quạt lớn BOC thành 4
hình quạt bằng nhau => góc ở tâm của mỗi hình quạt = 60^o.
Ta có 5 điểm còn lại trong 4 hình quạt vậy trong ít nhất 1
hình quạt có 2 điểm đang xét.
Khoảng cách giữa 2 điểm đó không lớn hơn bán kính = 1.
Với
5 điểm dễ thấy là nếu xếp chúng vào 5 đỉnh của hình ngũ
giác đều nội tiếp thì khoảng cách gữa 2 điềm bất kỳ \geq
cạnh của ngũ giác > bán kính = 1 (Ta xét cạnh P1P2. Trong tam
giác OP1P2 cạnh P1P2 đối điện với góc 72^o nên lớn hơn OP1 và
OP2 là những cạnh đối diện với góc 54^o)
VD5
Trên
mặt phẳng, cho 25 điểm phân biệt và trong 3 điểm bất kì, bao giờ cũng
tìm được 2 điểm có khoảng cách giữa chúng <1. Chứng minh rằng, tồn
tại 1 hình tròn có bán kính = 1 chứa không ít hơn 13 điểm như trên.
Giải:
Lấy
điểm P1 là tâm kẻ đường tròn C1 với bán kính = 1. Nếu C1 chứa
25 điểm đã cho thì ta có đ.p.c.m. Giả sử P2 không thuộc C1 tức
P1P2 > 1. Lấy điểm P2 là tâm kẻ đường tròn C2 với bán kính =
1. Ngoài C1 và C2 không còn điểm nào đã cho Thật thế nếu P3
nằm ngoài C1 và C2 thì ta có P1P2 > 1, P1P3 > 1, P2P3 > 1,
vô lý vì trong tam giác P1P2P3 phải có 1 cạnh < 1. 25 điểm
nằm trong 2 đường tròn nên theo nguyên lý Dirichlet trong 1 đường
tròn có ít nhất 13 điểm đã cho.
Nguyên lý dirichlet: Nếu nhốt kn+1 thỏ vào k lồng thì một trong các lồng (tồn tại 1 lồng) chứa ít nhất n+1 thỏ.
mà
mí cái bài trên kia, thuộc loại: siu đơn giản so với bọn tui học ^^! Mà
cậu phải cóp lí thuyết trước bài tập chớ, như vậy ng` ta hông hỉu là
đúng thui.
cái nguyên lí này có thể tóm tắt như sau (nguyên lí lồng -thỏ =>dễ hỉu hơn là ẩn n)
vd: ta có 3 con thỏ bỏ vào 2 lồng, như vậy sẽ tồn tại 1 lồng chắc chắn chứa ít nhất 2 con. =>ok?:48::
Vậy tổng quát ta có: Nếu có m chú thỏ, đem nhốt vào n lồng thoả m>n thì chắc chắn tồn tại 1 lồng chứa ko ít hơn 2 chú thỏ.
Nguyên lí đi-dép-lê chỉ quan tâm đến việc tồn tại hay ko tồn tại mà ko phải chỉ ra sự tường min của sự việc.