Chuyên đề: Nguyên lý Dirichle

ChuTieuThichHocToan xin giới thiệu với các cháu học sinh lớp 5,6 và các cháu THCS một số bài tập về Nguyên lý Dirichle (Nhốt thỏ vào chuồng). Đây là nguyên lý được phát biểu bởi nhà toán học Dirichle.  (Nếu để đến ngày nay, biết đâu lại có cháu nào phát biểu và lấy tên của mình đặt cho nguyên lý ấy cũng nên…)

I.      NGUYÊN LÝ DIRICHLET
Nguyên lí Dirichlet:

Không thể nhốt 7 chú thỏ vào 3 cái lồng sao cho mỗi lồng không quá 2 chú thỏ.

Có nhiều cách phát biểu, mở rộng nguyên lý này. Ví dụ nếu nhốt 3 con thỏ vào 2 chuồng thì bao giờ cũng tồn tại 1 chuồng chứa ít nhất 2 con thỏ…

Nguyên lí Dirichlet tổng quát:
Nếu đặt n viên bi vào k cái hộp (n,k nguyên dương), n = kq + r (với 0 < r < k) thì sẽ tồn tại một hộp chứa ít nhất q + 1 viên bi.

Chứng minh rất đơn giản: giả sử không hộp nào chứa nhiều hơn hoặc bằng q + 1 viên bi, khi đó k hộp sẽ chứa nhiều nhất k.q < n viên bi (vô lý)

Nguyên lí Dirichlet (còn gọi là nguyên lí chuồng bồ câu) tuy có phát biểu đơn giản nhưng lại được vận dụng rất nhiều trong thực tế. Nhờ nguyên lí này mà trong nhiều trường hợp, người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm kiếm cụ thể.

 

II.                BÀI TẬP CĂN BẢN

Bài 1:

Một trường học có 1000 học sinh gồm 23 lớp. Chứng minh rằng phải có ít nhất một lớp có từ 44 học sinh trở lên

Giải:
Giả sử 23 lớp mỗi lớp có không quá 43 học sinh.
Khi đó số học sinh là:
43.23=989 học sinh (ít hơn 1000–989=11 học sinh)
Theo nguyên lí Dirichlet phải có ít nhất một lớp có từ 44 học sinh trở lên

Nhận xét: Các cháu học sinh để ý, với dạng toán này, đề bài thường yêu cầu chứng minh có ít nhất 1 lớp, (hoặc tương tự) có ít nhất bao nhiêu học sinh.

Như vậy, với dạng này điều quan trọng là chúng ta cần chỉ ra, đâu là thỏ, đâu là chuồng. Với bài số 1, đọc đề xong cái là nhìn thấy ngày số học sinh (như là số thỏ. hihi) còn số lớp chính là số chuồng. (Hihi, ví von thôi nhé, cấm nghĩ linh tinh. Lớp là lớp, học sinh là học sinh đấy).

Nhận xét thêm về cách giải, thực ra nói là áp dụng nguyên lý Dirichle, nhưng các cháu có thể thấy chúng ta đang đi chứng minh nguyên lý này, bằng việc giả sử ngược lại (phương pháp phản chứng).

Để hiểu rõ hơn, chúng ta đi tiếp tục bài 2.

Bài 2:

Một lớp có 50 học sinh. Chứng minh rằng có ít nhất 5 học sinh có tháng sinh giống nhau

Phân tích:

Đọc đề chúng ta thấy có học sinh, đề bài yêu cầu chứng minh học sinh có cùng tháng sinh. Việc “cùng tháng sinh” ở đây có thể hiểu như “nhốt cùng chuồng”. Như vậy, chuồng ở đây chính là tháng sinh, còn học sinh là “thỏ”.

Giải:
Giả sử có không quá 4 học sinh có tháng sinh giống nhau
Một năm có 12 tháng, khi đó số học sinh của lớp có không quá: 12.4=48 (học sinh)
Theo nguyên lí Dirichlet phải có ít nhất 5 học sinh có tháng sinh giống nhau

Bài 3:

Có sáu loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau.

Phân tích:

Khó hơn rồi đây. Bài toán này, đề bài không yêu cầu chúng ta chứng mình có ít nhất bao nhiêu gì đấy trong một gì đấy nữa. Mà ngược lại, đề bài yêu cầu chúng ta tìm ít nhất số học sinh để thỏa mãn điều kiện có ít nhất như các bài trước.

Bây giờ chúng ta phân tích để nhận ra đâu là “thỏ”, đâu là “chuồng” nhé. Nào hãy chú ý yêu cầu đề bài “ít nhất 6 người cùng nhận học bổng như nhau”, như vậy, người ở đây chính là “thỏ” còn loại học bổng chính là “chuồng”. Để giải bài toán ngược này, chúng ta cũng làm tương tự, giả sử không thỏa mãn đề bài, tức mỗi loại học bổng chỉ có tối đa 5 người….

Giải:

Giả sử mỗi loại học bổng chỉ có 5 người => số người là 5×6 = 30 người.

Nếu ta lấy 31 người, khi đó theo nguyên lý Dirichle, tồn tại 1 loại học bổng mà có ít nhất 6 người nhận.

Nhận xét: Ta thấy 31 = 30 + 1, như vậy, ta chỉ việc tìm số lớn nhất để không thỏa mãn đề bài (chính là 5×6 = 30) cộng thêm 1 sẽ thành số nhỏ nhất thỏa mãn đề bài.

Bài khó làm thêm (Thi Toán Châu Á Thái Bình Dương 2012)

” Có 1 bài kiểm tra gồm 10 câu, mỗi câu có 2 phương án trả lời là ĐÚNG hoặc SAI. Hỏi phải có ít nhất bao nhiêu học sinh làm bài kiểm tra để tồn tại ít nhất 2 học sinh có cách làm bài giống hệt nhau. (giống hệt nhau tức là các câu trả lời cho các bài đều giống hệt nhau)

Phân tích:

Với bài toán này, chúng ta dễ dàng nhìn thấy số học sinh là “thỏ”, và cách làm bài chính là “chuồng”.

Số cách làm bài ở đây chúng ta chưa biết, ta đi tính số cách làm bài có thể.

Với mỗi câu hỏi, có 2 phương án trả lời Đ hoặc S. Có 10 câu => có 2x2x….x2 = 2^10 cách trả lời cho 10 câu hỏi đó. Hay nói cách khác có 2^10 cách làm bài.

Như vậy nếu mỗi học sinh đều có cách làm bài khác nhau => có tối đa 2^10 học sinh.

Vậy với 2^10 + 1 học sinh thì theo Nguyên Lý Dirrichle sẽ tồn tại ít nhất 2 học sinh có cách làm bài giống hệt nhau.

OK. Khó hơn đúng không nào? Thế mới là thi Toán châu Á TBD do Singapore tổ chức chứ.🙂
Bài 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. Chứng minh rằng í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)

Phân tích:

Đề bài cho 45 học sinh, (chính là số “thỏ”). Nhưng số chuồng thì chúng ta chưa biết chính xác. Chúng ta cần cẩn thận hơn với các dữ kiện “không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10”. Như vậy các điểm chỉ có thể từ 2 cho đến 10. Nhưng chỉ có 2 người được 10 tức là còn 43 người còn lại chỉ được điểm từ 2 cho đến 9. (có 8 số – tương ứng 8 “chuồng”)

Giải:
Có 43 học sinh phân thành 8 loại điểm (từ 2 đến 9)
Giả sử 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ó:
5.8=40 học sinh, ít hơn 3 học sinh so với 43.
Theo nguyên lý Dirichlet tồn tại 6 học sinh có điểm kiểm tra bằng nhau.

 

Bài 5:

Một lớp học có 50 học sinh, có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu 3 bài tập. Chứng minh rằng tồn tại 17 học sinh thiếu 1 số bài tập như nhau (trường hợp không thiếu bài tập coi như thiếu 0 bài)

Phân tích:

Bài này chúng ta để ý dữ kiện: “có duy nhất một học sinh thiếu nhiều bài tập nhất là thiếu 3 bài tập” => các học sinh còn lại chỉ thiếu 0, 1, hoặc 2 bài tập (tức là có 3 loại thiếu bài tập). Loại bỏ học sinh duy nhất thiếu 3 bài đi, còn lại 50 – 1 = 49 bạn.

Giải:

Ngoài bạn học sinh duy nhất thiếu 3 bài ta còn 49 bạn.
Giả sử mỗi loại bài tập có 16 học sinh.
Số học sinh không quá 16×3=48 (thiếu 1 học sinh).
Theo nguyên lí Dirichlet có ít nhất 17 học sinh thiếu một số bài tập như nhau

III.             BÀI TẬP NÂNG CAO

Bài 1:

Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau.

Phân tích:

Phòng họp có n người, có thể coi là n “thỏ” rồi này. Bây giờ chúng ta xác đinh đâu là “chuồng”. Hãy đọc kỹ đề bài yêu cầu gì, chúng ta sẽ nhìn ra “chuồng” ngay. “tìm được 2 người có số người quen trong số những người dự họp là như nhau” => số người quen giống nhau, hay chính là nhốt cùng “chuồn”. Như vậy, số người quen chính là số “chuồng”.

Ta thấy 1 người có thể quen với 0 người, 1 người, ….hoặc nhiều nhất là n-1 người trong cuộc họp….

Giải:

Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n–1. Rõ ràng trong phòng không thể đồng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là n–1 (tức là quen tất cả). Vì vậy theo số lượng người quen, ta chỉ có thể phân n người ra thành n–1 nhóm.

Vậy theo nguyên lí Dirichlet tồn tai một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có số người quen là như nhau.

Bài 2:

Trong một lưới ô vuông kích thước 5.5, người ta điền ngẫu nhiên vào các ô một trong các giá trị 0,1 hoặc 2, sau đó tính tổng tất cả các ô theo hàng ; theo cột và theo hai đường chéo. Chứng minh rằng tồn tại ít nhất hai tổng có giá trị bằng nhau.

Phân tích:

Hãy đọc kỹ đề bài yêu cầu, chúng ta sẽ thấy “thỏ” và “chuồng”🙂.

“Tồn tại ít nhất 2 tổng có giá trị bằng nhau” => thỏ chính là tổng (hàng ngang, dọc, chéo), còn giá trị chính là “chuồng”. Vấn đề của chúng ta là chúng ta cần đi tìm các giá trị có thể của tổng. Ta thấy một tổng 5 ô sẽ có giá trị nhỏ nhất là 0, lớn nhất là 10.

Giải:

Gọi các tổng lần lượt là S1,S2,..S12.
Có tất cả 12 tổng. Ta nhận thấy rằng các tổng này chỉ có thể nhận các giá trị là {0, 1, 2…., 9, 10}. Có tất cả 11 giá trị khác nhau. Từ đó, theo nguyên lý Dirichlet ta suy ra điều cần chứng minh.

 

Bài 3:

Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.

Giải:

Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ thù của A, điều này suy ra từ nguyên lí Dirichlet, vì những người khác chỉ có thể là bạn hoặc thù của A.
Trong trường hợp đầu ta gọi B,C,D là bạn của A. nếu trong ba người này có hai người là bạn thì họ cùng với A lập thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B,C,D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba người là kẻ thù của A. (ĐPCM)

 

Bài 4:

Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.

Giải:

Ta có số trận đã đấu của mỗi người có thể là 0,1,2,3,4. Nhưng vì không thể có cùng lúc một người đã đấu 4 trận và một người chưa đấu trận nào, nên có tối đa 4 loại số trận đã đấu.

Vận dụng nguyên lý Dirichlet ta có ít nhất có 2 người có cùng số trận đã đấu.

Bài 5: (Thi chuyên AMS cấp 2 năm 2011) (hi vọng ChuTieu không nhớ nhầm)

Có 6 học sinh làm một bài thi gồm 6 câu hỏi. Nếu trả lời đúng được 2 điểm, trả lời sai bị trừ 1 điểm. Nếu số điểm bị trừ nhiều hơn số điểm đạt được thì tính bị 0 điểm.

Hỏi có thể luôn có 2 học sinh bằng điểm nhau được hay không???

Phân tích và gợi ý giải:

Bài này đề bài lại hỏi theo kiểu có hay không, nhưng chúng ta hãy bình tình. Nếu một khi chúng ta đã hiểu bản chất của bài toán dạng này thì sẽ không gì làm chúng ta sợ hay mất tự tin được cả.

“Hai học sinh bằng điểm nhau” => Học sinh chính là “thỏ”, điểm chính là “chuồng”.

Vấn đề bài toán trở thành đi tìm số điểm có thể (số chuồng), từ đó sẽ giúp chúng ta trả lời được câu hỏi của đề bài.

Đề thi gồm 6 bài, xảy ra các trường hợp sau:

– Đúng hết 6 câu => 12 điểm

– Đúng 5 câu, sai 1 câu => 5×2 -1 = 9 điểm

– Đúng 4 câu, sai 2 câu => 4×2 -2×1 = 6 điểm

– Đúng 3 câu, sai 3 câu => 3×2 – 3×1 = 3 điểm

– Đúng 2 câu, sai 4 câu => 2×2 – 4x 1 = 0 điểm

– Đúng dưới 2 câu => dễ thấy sẽ bị 0 điểm.

Nhìn lại ta thấy chỉ có 0,3,6,9,12 điểm tức là chỉ có 5 loại điểm, trong khi có 6 học sinh => có 2 học sinh cùng điểm.

OK rồi. Bây giờ mời các cháu làm 1 số bài tập tự giải dưới đây. ChuTieu sẽ post chuyên đề Dirichle và bài toán chia hết trong thời gian tới đây, mời các cháu chú ý theo dõi…

IV.             BÀI TẬP TỰ GIẢI

Bài 1:

Chia 50 kẹo cho 10 em bé (em nào cũng được chia kẹo). Chứng minh rằng dù chia cách nào đi nữa cũng tồn tại hai em có số kẹo bằng nhau.

Bài 2:

Bốn lớp 11A,11B,11C,11D có tất cả 44 học sinh giỏi, trong đó số học sinh giỏi của lớp 11D không quá 10 người. Chứng minh rằng ít nhất một trong 3 lớp 11A,11B,11C có số học sinh giỏi từ 12 em trở lên.

Bài 3:

Có 33 con chim đậu trên một sân vuông hình vuông cạnh 4m.

Chứng minh rằng có ít nhất 3 con đậu trong một đường tròn có bán kính 1m

Bài 4:

Một cuộc họp gồm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểu về vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III. Ngoài ra, có đúng 1 người không phát biểu vấn đề nào.

Hỏi nhiều nhất là có bao nhiêu người phát biểu cả 3 vấn đề.

Bài 5:

Có 17 nhà bác học viết thư cho nhau trao đổi 3 vấn đề. Chứng minh rằng luôn tìm được 3 người cùng trao đổi một vấn đề.

Leave a comment

5 Comments

  1. Minh Đức

     /  March 29, 2013

    Thầy giải giúp con bài số 4 phần nâng cao với ạ.

    Reply
  2. Quang Nam

     /  March 29, 2013

    Chuyên đề rất hay với cả học sinh lớp 6 thầy ạ.

    Reply
  3. Các cháu thi AMS, cố gắng học tốt dạng này sẽ làm được bài suy luận logic. 2,5 điểm đút túi rồi…

    Reply
  4. Thầy giải giúp con bài 3 và bài 5 phần bài tập tự giải với ạ

    Reply
  5. Trung

     /  June 26, 2015

    Nhờ thầy chỉ con cách giải bài sau: “bài trắc nghiệm có 30 câu, mỗi câu trả lời đúng được 3đ, mỗi câu sai trừ 1đ, câu không trả lời 0đ. Hỏi cần có mấy thí sinh tham gia làm bài (mỗi thí sinh chỉ làm 1 bài) để đảm bảo luôn có 2 thí sinh trùng điểm nhau. Biết rằng thang điểm có điểm thấp nhất là 0đ.” Bài này giống bài 5 của thầy nhưng có thêm tình huống không trả lời không điểm thì con chịu, con tính không ra. Thầy chỉ cho con nha thầy.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: