R
riverflowsinyou1
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
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.
Chứng minh (dùng phương pháp phản chứng):
Giả sử không có lồng nào 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)
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 mà 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
II)Mở rộng nguyên lí Dirichlet
Cho A là tập hữu hạn những phần tử , Kí hiệu s(A) là số lượng các phần tử thuộc A.Nguyên lý Dirichlet có thể phát biểu như sau
Nếu A và B là những tập hợp hữu hạn và s(A) > k.s(B) ở đây k là 1 số tự nhiên nào đó và nếu mỗi phần tử của A cho tương ứng với 1 phần tử nào đó của B thì tồn tại ít nhất k+1 phần tử của A mà chúng tương ứng với cùng một phần tử của B
II. 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.
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
Vì 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_1A_2B_2B_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
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):
Giả sử không có lồng nào 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)
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 mà 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
II)Mở rộng nguyên lí Dirichlet
Cho A là tập hữu hạn những phần tử , Kí hiệu s(A) là số lượng các phần tử thuộc A.Nguyên lý Dirichlet có thể phát biểu như sau
Nếu A và B là những tập hợp hữu hạn và s(A) > k.s(B) ở đây k là 1 số tự nhiên nào đó và nếu mỗi phần tử của A cho tương ứng với 1 phần tử nào đó của B thì tồn tại ít nhất k+1 phần tử của A mà chúng tương ứng với cùng một phần tử của B
II. 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.
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
Vì 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_1A_2B_2B_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
Last edited by a moderator:
