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.
thế,
ai đọc ko hỉu thì lên tiếng, tớ sẽ giải thích thêm. cái nguyên lí này
hồi học, mấy cái ví dụ trên kia mà gặp thì ...ko bao h bởi nó quá dễ, có
ngay, còn mấy cái bài khó á, toàn phải qua mấy bước trung gian thui,
ghét dạng này:46:::35::
cái nguyên lí này, hồi học bọn tui hay trêu là cái nguyên lí "đi-dép-lê" ke ke :21: :21::
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.
thế,
ai đọc ko hỉu thì lên tiếng, tớ sẽ giải thích thêm. cái nguyên lí này
hồi học, mấy cái ví dụ trên kia mà gặp thì ...ko bao h bởi nó quá dễ, có
ngay, còn mấy cái bài khó á, toàn phải qua mấy bước trung gian thui,
ghét dạng này:46:::35::
đọc chưa mà bảo nó dễ zậy? nếu pà bảo mấy bì
này thật sự quá dễ and đơn giản và hồi cấp 2 pà học dirichlet còn khó
hơn nhiều thì em xin bái phục, khéo giờ này pà chị đang học lớp chuyên
toán của đại học khoa học tự nhiên rồi đóa, đâu phải ngồi đây! and, mấy
cái ví dụ kia có bài thì nguyên lý dirichlet có sẵn nhưng có bài thì
phải làm qua bước trung gian.
này nhé, nếu nhìn cả bài và nhìn qua cả
lời giải thì ta thấy mấy bài toán dirichlet thật là quá dễ, nhưng thử
giải từ đầu xem nó có quá dễ như ta nghĩ ko???
"này nhé, ami, đừng có lớn bắt nạt bé nha~!!, coi chừng mai tui học hết cho bít tay!!!"
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.
thế,
ai đọc ko hỉu thì lên tiếng, tớ sẽ giải thích thêm. cái nguyên lí này
hồi học, mấy cái ví dụ trên kia mà gặp thì ...ko bao h bởi nó quá dễ, có
ngay, còn mấy cái bài khó á, toàn phải qua mấy bước trung gian thui,
ghét dạng này:46:::35::
đọc chưa mà bảo nó dễ zậy? nếu pà bảo mấy bì
này thật sự quá dễ and đơn giản và hồi cấp 2 pà học dirichlet còn khó
hơn nhiều thì em xin bái phục, khéo giờ này pà chị đang học lớp chuyên
toán của đại học khoa học tự nhiên rồi đóa, đâu phải ngồi đây! and, mấy
cái ví dụ kia có bài thì nguyên lý dirichlet có sẵn nhưng có bài thì
phải làm qua bước trung gian.
này nhé, nếu nhìn cả bài và nhìn qua cả
lời giải thì ta thấy mấy bài toán dirichlet thật là quá dễ, nhưng thử
giải từ đầu xem nó có quá dễ như ta nghĩ ko???
"này nhé, ami, đừng có lớn bắt nạt bé nha~!!, coi chừng mai tui học hết cho bít tay!!!"
ami_thienthantuyet
21-07-2009, 22:40
hờ,
nói nhé: tớ đọc hết rùi, mí cái đó cũng thuộc rùi, còn di-dép-le á, tớ
cũng đã bảo là cái nguyên lí này hồi học, mấy cái ví dụ trên kia mà gặp
thì ...ko bao h bởi nó quá dễ, có ngay, còn mấy cái bài khó á, toàn phải
qua mấy bước trung gian thui, ghét dạng này
tớ ko hề bảo dễ, tớ chỉ bảo mí cái ví dụ của cậu đưa ra rất dễ, còn các bài khó thì ôi dời, hồi học nhức đầu!
"này nhé, ami, đừng có lớn bắt nạt bé nha~!!, coi chừng mai tui học hết cho bít tay!!!"
tớ đâu có bắt nạt, tớ chỉ bảo ai ko hiểu cứ lên tiếng, tớ sẽ giải thích nếu có thể.
thì em xin bái phục, khéo giờ này pà chị đang học lớp chuyên toán của đại học khoa học tự nhiên rồi đóa, đâu phải ngồi đây!
hồi
đoá, tớ ko thi khtn, tớ thi sư phạm, còn tại sao tớ phải học qo thì cậu
ko hỉu, và sẽ ko bao h hỉu, đừng nhắc đến nữa mà làm tớ bực mình.
hết!
nói nhé: tớ đọc hết rùi, mí cái đó cũng thuộc rùi, còn di-dép-le á, tớ
cũng đã bảo là cái nguyên lí này hồi học, mấy cái ví dụ trên kia mà gặp
thì ...ko bao h bởi nó quá dễ, có ngay, còn mấy cái bài khó á, toàn phải
qua mấy bước trung gian thui, ghét dạng này
tớ ko hề bảo dễ, tớ chỉ bảo mí cái ví dụ của cậu đưa ra rất dễ, còn các bài khó thì ôi dời, hồi học nhức đầu!
"này nhé, ami, đừng có lớn bắt nạt bé nha~!!, coi chừng mai tui học hết cho bít tay!!!"
tớ đâu có bắt nạt, tớ chỉ bảo ai ko hiểu cứ lên tiếng, tớ sẽ giải thích nếu có thể.
thì em xin bái phục, khéo giờ này pà chị đang học lớp chuyên toán của đại học khoa học tự nhiên rồi đóa, đâu phải ngồi đây!
hồi
đoá, tớ ko thi khtn, tớ thi sư phạm, còn tại sao tớ phải học qo thì cậu
ko hỉu, và sẽ ko bao h hỉu, đừng nhắc đến nữa mà làm tớ bực mình.
hết!
I.Định nghĩa:
Nguyên
lý Đirichlê còn gọi là "nguyên tắc nhốt thỏ vào lồng " hoặc "nguyên tắc
xếp đồ vật vào ngăn kéo" hoặc nguyên tắc lổ chuồng câu".
nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán.
Nhiều
khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học
để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Đirichlê mà bài
toán trở nên dễ dàng giải quyết.
Nguyên tắc Đirichlê được phát biểu dưới dạng bài toán sau đây:
1.
Nếu đem nhốt m con thỏ vào n chiếc lồng, với m>n (nghĩa là số thỏ
nhiều hơn số lồng) thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.
Hoặc là:
2.
Nếu đem xếp m đồ vật vào n ô ngăn kéo, với m>n (nghĩa là số đồ vật
nhiều hơn số ngăn kéo), thì ít nhất cũng phải có một ô ngăn kéo chứa
không ít hơn 2 đồ vật.
Nguyên
lý Đirichlê còn gọi là "nguyên tắc nhốt thỏ vào lồng " hoặc "nguyên tắc
xếp đồ vật vào ngăn kéo" hoặc nguyên tắc lổ chuồng câu".
nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán.
Nhiều
khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học
để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Đirichlê mà bài
toán trở nên dễ dàng giải quyết.
Nguyên tắc Đirichlê được phát biểu dưới dạng bài toán sau đây:
1.
Nếu đem nhốt m con thỏ vào n chiếc lồng, với m>n (nghĩa là số thỏ
nhiều hơn số lồng) thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.
Hoặc là:
2.
Nếu đem xếp m đồ vật vào n ô ngăn kéo, với m>n (nghĩa là số đồ vật
nhiều hơn số ngăn kéo), thì ít nhất cũng phải có một ô ngăn kéo chứa
không ít hơn 2 đồ vật.
Chứng minh (dùng phương pháp phản chứng):
1/Giả sử không có lồng nào (trong n cái lồng ) nhốt từ 2 thỏ trở nên.
Thế thì cho dù mỗi lồng đều có nhốt một thỏ thì tổng số thỏ bị nhốt cũng chỉ là n thỏ
Trong khi đó tổng số thỏ là m.
Điều này vô lý.
Vậy ít nhất cũng phải có 1 lồng nhốt từ 2 thỏ trở nên.(đpcm)
2/Nguyên lí Dirichlet là một định lí về tập hợp hữu hạn.Phát biểu chính xác nguyên lí này như sau
Cho A và B là 2 tập không rỗng có số phần tử hữu hạn.
Số phần tử ở A lớn hơn số lượng phần tử của B .
Nếu với quy tắc nào đấy, mỗi phần tử của A tương ứng với 1 phần tử của B
Thì tồn tại 2 phần tử khác nhau của A mà chúng tương ứng với cùng 1 phần tử của B.
Hiểu một cách đơn giản:
Nếu nhốt 7 chú thỏ vào 3 cái lồng thì có ít nhất 1 lồng có không ít hơn 3 thỏ
1/Giả sử không có lồng nào (trong n cái lồng ) nhốt từ 2 thỏ trở nên.
Thế thì cho dù mỗi lồng đều có nhốt một thỏ thì tổng số thỏ bị nhốt cũng chỉ là n thỏ
Trong khi đó tổng số thỏ là m.
Điều này vô lý.
Vậy ít nhất cũng phải có 1 lồng nhốt từ 2 thỏ trở nên.(đpcm)
2/Nguyên lí Dirichlet là một định lí về tập hợp hữu hạn.Phát biểu chính xác nguyên lí này như sau
Cho A và B là 2 tập không rỗng có số phần tử hữu hạn.
Số phần tử ở A lớn hơn số lượng phần tử của B .
Nếu với quy tắc nào đấy, mỗi phần tử của A tương ứng với 1 phần tử của B
Thì tồn tại 2 phần tử khác nhau của A mà chúng tương ứng với cùng 1 phần tử của B.
Hiểu một cách đơn giản:
Nếu nhốt 7 chú thỏ vào 3 cái lồng thì có ít nhất 1 lồng có không ít hơn 3 thỏ
Nguyên
lý Dirichlet do nhà toán học người Đức, Peter Gustav Dirichlet
(1805-1059) đề xuất, tuy đơn giản nhưng có nhiều ứng dụng trong lập luận
giải toán.
Nguyên lý Dirichlet thường áp dụng để giải một số bài
toán về sự tồn tại với các dạng toán về số học, hình học và tô màu đồ
thị ............
Một số dạng thường gặp là:
I)Các dạng toán số học
1/Dạng suy luận
2/Sự chia hết
3/Toán về tổng, hiệu, chữ số tận cùng...các loại
II)Các dang toán về hình học
1. Đánh giá các điểm, các đường thẳng
2. Đánh giá góc và độ dài
III)Các bài toán về tô màu:Thường là những bài rất hay và khó.
IV)Nguyên lí dirichlet cho diện tích
lý Dirichlet do nhà toán học người Đức, Peter Gustav Dirichlet
(1805-1059) đề xuất, tuy đơn giản nhưng có nhiều ứng dụng trong lập luận
giải toán.
Nguyên lý Dirichlet thường áp dụng để giải một số bài
toán về sự tồn tại với các dạng toán về số học, hình học và tô màu đồ
thị ............
Một số dạng thường gặp là:
I)Các dạng toán số học
1/Dạng suy luận
2/Sự chia hết
3/Toán về tổng, hiệu, chữ số tận cùng...các loại
II)Các dang toán về hình học
1. Đánh giá các điểm, các đường thẳng
2. Đánh giá góc và độ dài
III)Các bài toán về tô màu:Thường là những bài rất hay và khó.
IV)Nguyên lí dirichlet cho diện tích
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 nếu các đội đã đấu với nhau thì số trân mà mỗi đội đã đá 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..
Nghĩa là:
10 đội mối đội là 1 cái lồng .
Số
trận đấu có thể của các đội lần lượt là 0,1,2,3,4,5,6,7,8 (9 giá trị)
mỗi giá trị là một con thỏ .Vậy có ít nhất 2 lồng có số giá trị như nhau
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 nếu các đội đã đấu với nhau thì số trân mà mỗi đội đã đá 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..
Nghĩa là:
10 đội mối đội là 1 cái lồng .
Số
trận đấu có thể của các đội lần lượt là 0,1,2,3,4,5,6,7,8 (9 giá trị)
mỗi giá trị là một con thỏ .Vậy có ít nhất 2 lồng có số giá trị như nhau
Nguyên lí Dirichlet mở rộng: "Nếu nhốt m con thỏ vào vào n cái chuồng
(m, n là các số nguyên dương) thì tồn tại 1 chuồng chứa ít nhất
[(m+n-1)/n] con thỏ"; ở đây kí hiệu [a] được dùng để chỉ số nguyên lớn
nhất ko vượt quá a, a là số thực, đọc là phần nguyên của a.
Nói về nguyên lí Dirichlet mình có 1 số bài khá hay:
1) cm trong 9 số tự nhiên bất kì, ta luôn có thể chọn ra 5 số mà tổng của chúng là 1 số chia hết cho 5.
2) cm trong 7 số tự nhiên bất kì, ta ta luôn có thể chọn ra 4 số mà tổng của chúng là 1 số chia hết cho 4.