CÁC BÀI TẬP ÁP DỤNG NGUYÊN LÝ DIRICHLET

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ỏ.

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), thì sẽ tồn tại một hộp chứa ít nhất $\left\lceil \frac{n}{k} \right\rceil$ viên bi, với $\left\lceil x \right\rceil$ là số nguyên bé nhất không nhỏ hơn $x$.

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

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

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ó năm 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.

Giải:

Gọi $N$ là số sinh viên, khi đó:
$\left\lceil \frac{N}{5} \right\rceil =6 \Rightarrow 5 < \frac{N}{5}≤ 6$ hay  $25 < N ≤ 30$.
Vậy số N bé nhất thỏa mãn là $26$.
 

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)

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)

Giải:
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 $2$ 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.

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ị $-1, 0$ hoặc $1$, 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.

Giải:

Gọi các tổng lần lượt là $S_1, S_2,..S_{12}$.
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à $\{ -5, -4…0,…4, 5\}$. 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.

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 đề.