Bạn mathvn ơi mình nghĩ bài này nên dùng phương pháp tô màu.Bạn có thể trình bày cách làm của bạn ra được ko.
Còn dưới đây là nguyên lý đirich lê và 1 số ví dụ mình post lên các bạn cùng đọc nhé:
Nguyên lý đirichlê:Cho m phần tử chia vào n tập hợp :
+)m>n thì tồn tại ít nhất 1 tập hợp chứa 2 phần tử .
+)m>kn thì tồn tại ít nhất 1 tập hợp chứa k+1 phần tử.
Ví dụ 1.Để kỷ niệm 20 năm ngày giải phóng Miền Nam,tại một thành phố người ta tổ chức buổi lễ gặp mặt những người 20 tuổi.Ngày 30 tháng 4 năm đó có 400 thanh niên đến dự lễ. Chứng minh rằng có ít nhất hai người trong số người tới dự cùng chung một ngày sinh.
Lời giải: Năm 1995 có 365 ngày.Chúng ta coi mỗi ngày như là một ngăn kéo và đánh số từ 1 đến 365(Ngăn kéo cuối cùng là ngày 31 tháng 12 năm 1995).Chúng ta đặt những thanh niên có cùng ngày sinh vào cùng một ngăn kéo có số đúng bằng ngày sinh.Vì số thanh niên đến dự lễ lớn hơn số ngăn kéo nên theo nguyên lý đirichlê có ít nhất hai người được đặt vào cùng một ngăn kéo.Điều đó có nghĩa là họ sinh cùng một ngày.
Ví dụ 2. Ba mươi học sinh làm bài viết chính tả.Một trong số học sinh đó bị 14 lỗi,còn các học sinh khác mặc số lỗi ít hơn.Chứng minh rằng có ít nhất ba người mắc số lỗi bằng nhau.
Lời giải:Chúng ta xét 15 ngăn kéo được đánh số từ 0 đến 14.Chúng ta đặt mỗi học sinh vào một ngăn kéo mang số đúng bằng số lỗi mà học sinh đó mắc.Nếu không có ba học sinh nào có số lỗi bằng nhau thì trong mỗi ngăn kéo mang số từ 0,…,13 sẽ có nhiều nhất hai học sinh.Khi đó số lượng của những học sinh này nhiều nhất là 28 cộng với học sinh mắc 14 lỗi trong ngăn kéo số 14 chúng ta sẽ nhận được nhiều nhất là 29 học sinh viết chính tả,điều này dẫn đến sự mâu thuẫn với giả thiết bài toán.
Ví dụ 3.Chứng minh rằng trong mỗi nhóm bạn 5 người có ít nhất hai người có cùng số lượng người quen giữa những người trong nhóm đó.
Lời giải:Chúng ta xét năm ngăn kéo được đánh số từ 0 đến 4.mỗi người trong hóm được đặt vào một ngăn kéo mang số trùng với số người trong nhóm mà người đó quen.Ta xét hai trường hợp sau:
a)Nếu có một người không quen ai trong số những người còn lại thì ngăn 4 trống (vì ngược lại thì cả ngăn 0 và 4 đều không trống,dẫn đến vô lí).Như vậy,mỗi người trong số 5 người được đặt vào các ngăn kéo mang số 0,1,2,3 với số lượng 4 ngăn.Từ nguyên lý Đirichlê suy ra ít nhất có hai người ở cùng một ngăn.Hay là họ có chung số lượng người quen.
b)Nếu mọi người có ít nhất một người quen,mỗi người sẽ được đặt vào các ngăn mang số 1,2,3,4 với số lượng 4 ngăn. Từ nguyên lý Đirichlê suy ra ít nhất có hai người ở cùng một ngăn.Hay là họ có chung số lượng người quen.
Ví dụ 4.Trong một khu tập thể sống 123 người. Tổng số tuổi của họ là 3813. chứng minh rằng có thể chọn 100 người sống ở khu tập thể này mà tổng số tuổi của họ không nhỏ hơn 3100.
Lời giải: Chúng ta hãy chọn 100 người nhiều tuổi nhất và giả sử tổng số tuổi của họ nhỏ hơn 3100.Khi đó người trẻ nhất trong số người được chọn là 3100:100=31 tuổi.Mặt khác người này không trẻ hơn 23 người còn lại theo cách chọn.Khi đó tổng số tuổi của 23 người này không lớn hơn 23.31=713.Suy ra tổng số tuổi của tất cả mọi người sống trong khu tập thể nhỏ hơn 3100+713=3813 dẫn đến vô lí.
Ví dụ 5. Năm cặp vợ chồng tổ chức một buổi gặp mặt. Khi gặp nhau họ bắt tay nhau, nhưng không ai tự bắt tay người trong gia đình và người mà vợ hoặc chồng mình đã bắt tay rồi. Cũng không ai bắt tay cùng một người nhiều hơn một lần. Sau cuộc gặp chúc mừng ban đầu,một người đàn ông tên Hùng hỏi tất cả những người có mặt,kể cả vợ mình, là họ đã bắt tay được bao nhiêu lần. Họ nhận thấy rằng 9 người đwợc hỏi đều trả lời những con số khác nhau.Như vậy vợ của Hùng đã bắt tay bao nhiêu lần?
Lời giải: Mỗi một người khách bắt tay không quá 8 lần.Vì câu trả lời của 9 người là 9 số khác nhau nên các số đó phải là 0,1,2,3,4,5,6,7 và 8. Người bắt tay 8 lần phải là vợ hoặc chồng của người không bắt tay lần nào(Vì nếu ngược lại thì người đó chỉ bắt tay nhiều nhất là 7 lần mà thôi). Tương tự như vậy người bắt tay 7 lần có vợ hoặc chồng bắt tay 1 lần, người bắt tay 6 lần có vợ hoặc chồng bắt tay 2 lần, người bắt tay 5 lần có vợ hoặc chồng bắt tay 3 lần.Chỉ còn lại một người bắt tay 4 lần, đó chính là vợ của Hùng.
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
