Nguyên lý Dirichlet và ứng dụng

Nguyên lý Dirichlet. Nguyên lý Dirichlet (còn gọi là nguyên lý chuồng chim bồ câu) là một nguyên lý cơ bản trong toán học tổ hợp, phát biểu rằng:
 

 
Giải thích chi tiết:
 
Tên gọi: Nguyên lý này được đặt tên dựa trên phép ẩn dụ:
“Chim bồ câu” đại diện cho các vật thể cần xếp.

“Chuồng” đại diện cho các ngăn chứa hoặc nhóm phân loại.
 
Phát biểu toán học:

 
Trong đó, $\lceil\dfrac{n}{k}\rceil$ là phép làm tròn lên (tức là giá trị trần của $\dfrac{n}{k}$ ) (ví dụ: $\lceil 2,1 \rceil=3)$. (chú ý không có móc ở dưới).

Ví dụ minh họa:

Ví dụ 1:

Bài toán: Có 10 con chim bồ câu và 9 cái chuồng. Hỏi có ít nhất bao nhiêu con chim phải ở chung một chuồng?

Giải:

Vì $10>9$, theo nguyên lý Dirichlet, ít nhất 1 chuồng chứa ít nhất 2 con chim (vì $\lceil \dfrac{10}{9}\rceil =2$).
 
Ví dụ 2:

Bài toán: Trong một nhóm 13 người, chứng minh rằng ít nhất 2 người có sinh nhật cùng tháng.

Giải:
 
Coi “tháng” là 12 chuồng và “người” là 13 vật thể. Vì $13>12$, theo nguyên lý Dirichlet, ít nhất 2 người sinh cùng tháng.
 
 

Ứng dụng: Bây giờ ta ứng dụng Nguyên lý Dirichlet để giải bài toán sau đây:
 

Ta xét 7 số nguyên $a_1, a_2, a_3, a_4, a_5, a_6, a_7$. Gọi dư của chúng khi chia cho 4 lần lượt là $r_1, r_2, r_3, r_4, r_5, r_6, r_7$.

($0 \leqslant r_i \leqslant 3\ (i=1,2,3,4,5,6,7)$).
 
Trường hợp 1. Tồn tại (có ít nhất) 4 số bằng nhau trong các số $r_1, r_2, r_3, r_4, r_5, r_6, r_7$. Ta giả sử 4 số này là $R_1, R_2, R_3, R_4$. Khi đó $$A_1+A_2+A_3+A_4 \equiv R_1+R_2+R_3+R_4=4R_1 \equiv 0\ (\text{mod} \ 4)$$

Ở đây $A_i$ là số nguyên thuộc tập hợp $\left\{a_1, a_2, a_3, a_4, a_5, a_6, a_7\right\}$ ứng với số dư $R_i \ (i=1,2,3,4)$.
 
Vậy tồn tại 4 số sao cho tổng của chúng chia hết cho 4.
 
Trường hợp 2. Không tồn tại 4 số bằng nhau trong các số $r_1, r_2, r_3, r_4, r_5, r_6, r_7$.
 
Ta sử dụng Nguyên lý Dirichlet, bằng cách đem các số có cùng một dư bỏ vào một “chuồng”. Chuồng thứ nhất chứa các số có cùng một dư, chuồng thứ hai chứa các số có cùng một dư khác, chuồng thứ ba chứa các số có cùng một dư thứ ba và chuồng thứ tư chứa các số có cùng một dư còn lại.
 
Ta ký hiệu
 
$\fbox{$x$}$ là chuồng thứ nhất chứa $x$ số, (khung màu đỏ (red))

$\fbox{$x$}$ là chuồng thứ hai chứa $x$ số, (khung màu xanh lá (green))

$\fbox{$x$}$ là chuồng thứ ba chứa $x$ số, (khung màu xanh dương (blue))

$\fbox{$x$}$ là chuồng thứ tư chứa $x$ số. (khung màu đen (black))
 

Ta xét 4 trường hợp:
 

Trường hợp 2a. $\fbox{$3$}$ $\fbox{$3$}$ $\fbox{$1$}$ $\fbox{$0$}$, nghĩa là 3 số cùng một dư, 3 số cùng một dư khác, 1 số dư thứ ba, và 0 số dư thứ tư.

Ví dụ: 3 số dư $0$ , 3 số dư 1, 1 số dư $2$, 0 số dư $3$ . Khi đó Ta chọn $2$ số thuộc chuồng dư 1, $1$ số thuộc chuồng dư $2$ và $1$ số thuộc chuồng dư $0$. Tổng của chúng đồng dư với:
$$1+1+2+0\equiv 0\ (\text{mod}\ 4)$$

Trường hợp 2b. $\fbox{$3$}$ $\fbox{$2$}$ $\fbox{$2$}$ $\fbox{$0$}$, nghĩa là 3 số cùng một dư, 2 số cùng một dư khác, 2 số cùng một dư thứ ba, và 0 số dư thứ tư.

Ví dụ: 3 số dư $0$ , 2 số dư 1, 2 số dư $2$, 0 số dư $3$ . Khi đó Ta chọn $1$ số thuộc chuồng dư 0, $2$ số thuộc chuồng dư $1$ và $1$ số thuộc chuồng dư $2$. Tổng của chúng đồng dư với:
$$0+1+1+2\equiv 0\ (\text{mod}\ 4)$$

Trường hợp 2c. $\fbox{$3$}$ $\fbox{$2$}$ $\fbox{$1$}$ $\fbox{$1$}$, nghĩa là 3 số cùng một dư, 2 số cùng một dư khác, 1 số dư thứ ba, và 1 số dư thứ tư.

Ví dụ: 3 số dư $0$ , 2 số dư 1, 1 số dư $2$, 1 số dư $3$ . Khi đó Ta chọn $2$ số thuộc chuồng dư 0, $1$ số thuộc chuồng dư $1$ và $1$ số thuộc chuồng dư $3$. Tổng của chúng đồng dư với:
$$0+0+1+3\equiv 0\ (\text{mod}\ 4)$$

Trường hợp 2d. $\fbox{$2$}$ $\fbox{$2$}$ $\fbox{$2$}$ $\fbox{$1$}$, nghĩa là 2 số cùng một dư, 2 số cùng một dư khác, 2 số cùng một dư thứ ba, và 1 số dư thứ tư.

Ví dụ: 2 số dư $0$ , 2 số dư 1, 1 số dư $2$, 1 số dư $3$ . Khi đó Ta chọn $2$ số thuộc chuồng dư 0, $2$ số thuộc chuồng dư $2$. Tổng của chúng đồng dư với:
$$0+0+2+2\equiv 0\ (\text{mod}\ 4)$$

Nhận xét: Không còn trường hợp nào khác.
 

Vậy trong 7 số nguyên bất kỳ luôn luôn tồn tại 4 số sao cho tổng của chúng chia hết cho 4.
 
 

Mở rộng:
 

Chứng minh định lý này (chỉ dành cho GV Chuyên THPT) có thể đọc tại

Sau đó áp dụng định lý với $n=4$ ta có bài toán đã nêu.
 

About TS. Nguyễn Thái Sơn

Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013).