Nguyễn Hữu Điển: http:// free.hostdepartment.com/n/nhdien Nguyên lí lồng và thỏ
Nguyên lý Đirichlê tổng quát
Nguyễn Hữu Điển
Viện Toán học

Nguyên lý những chiếc lồng và các chú
thỏ ngay trong trờng phổ thông cơ sở đều đã
đợc biết và đôi lần áp dụng giải bài tập toán.
Nguyên lý đó là ta nhốt một số thỏ vào một số
lồng, nếu số lồng ít hơn số thỏ thì ít nhất có hai
thỏ nhốt cùng một lồng. Rất nhiều bài tập toán
đợc giải bằng nguyên lý này, tôi đã tập hợp lại
thành cuốn sách "Phơng pháp Đirichlê và ứng
dụng", NXB Khoa học và kỹ thuật, 160 trang, đã
đợc phát hành vào tháng 3/1999. Trong cuốn
sách này bao gồm trên 200 bài toán điển hình về
việc dùng phơng pháp Đirichlê. Sách đợc chia ra
16 chơng mỗi chơng theo một chủ đề : Nguyên
lý Đirichlê và ví dụ, Số học, Dãy số, Hình học, Mở
rộng nguyên lý Đirichlê, Nguyên lý Đirichlê cho
diện tích, Toán tổ hợp, Một số đề thi vô địch quốc
tế,... Trong mỗi chơng trên có 10 bài tập đợc
giải kỹ theo chủ đề và cách áp dụng nguyên lý
Đirichlê, sau đó là khoảng 5 bài luyện tập nhng
cũng đợc giải ở chơng 15 nếu ngời đọc thấy
khó khăn. Nhiều bài toán giải bằng phơng pháp
này rất ngắn gọn, một số bài giải bằng phơng
pháp này mà ta không để ý tới khi áp dụng. Theo
tôi đây là cuốn sách tham khảo cho các thày cô
giáo và các bạn học sinh ham thích Toán học.


gồm tất cả các số chia
cho 5 còn d 1; M
3
gồm tất cả các số chia cho 5
còn d 2;... Nếu ta lấy 5 số trong các tập hợp con
khác nhau, thì hiệu của bất kỳ hai số trong các số
này đều không chia hết cho 5. Nếu ta lấy 6 số tự
nhiên bất kỳ, thì hai trong chúng phải nằm trong
cùng một tập hợp trên (nguyên lý Đirichlê). Suy ra
hiệu của chúng chia hết cho 5. Nh vậy số lợng
nhỏ nhất những số ta phải lấy là 6 số tự nhiên.
Bài 4. Một lần 20 ngời quyết định đi bơi thuyền
bằng 10 chiếc thuyền đôi. Một số ngời đã quen
nhau, một số ngời không quen nhau. Nhng biết
rằng mỗi cặp hai ngời A và B mà không quen
nhau, thì tổng những ngời quen của A và những
ngời quen của B không nhỏ hơn 19. Chứng minh
rằng có thể phân chia số ngời vào các thuyền đôi
sao cho trong mỗi thuyền đều là những ngời quen
nhau.
Lời giải. Dễ thấy rằng ít nhất có 1 thuyền mà
ngời ta xếp hai ngời quen nhau. Ta ký hiệu k số
lợng thuyền lớn nhất , mà trong đó ngời ta có
thể xếp những cặp quen nhau và để cụ thể ta ký
hiệu trong thuyền thứ nhất xếp hai ngời quen A
1

và B
1
, thuyền thứ hai là A

ta có thể giả thiết rằng trong thuyền này xếp hai
ngời A
k
và B
k
. Nhng khi đó ta có thể xếp lại :
trong k-1 thuyền đầu tiên vẫn giữ nguyên, còn
trong thuyền thứ k xếp A
k
và B, còn thuyền thứ
k+1 xếp A và B
k
. Theo cách xếp này ta tiếp tục
xếp đến hết 10 thuyền sao cho trong mỗi thuyền
hai ngời đều quen nhau.
Bài 5. Cho 12 số có hai chữ số . Chứng minh rằng
giữa chúng có hai số mà hiệu của chúng cũng là
hai chữ số, hai chữ số này trùng nhau.
Lời giải. Trong 12 số có hai chữ số có hai số cho
cùng số d khi chia cho 11 (nguyên lý Đirichlê).
Cho những số đó là a
i
, a
j
(a
i
> a
j
) . Khi đó a
i

chúng; trờng hợp thứ hai, hai số sẽ cùng tính
chẵn, lẻ và khi đó tổng của chúng là một số chẵn.
Trong trờng hợp này tổng của hai số ta lấy sẽ
chia hết cho hiệu của nó.
Nh vậy từ 1999 số dã cho không thể
chọn hơn 666 số sao cho thỏa mãn điều kiện đầu
bài. Ta cũng xây dựng đợc cách chọn 666 số. Suy
ra số lợng lớn nhất các số ta phải tìm là 666.
Bài 7. Cho S là tập hợp n phần tử
M
i


S , M
i



, i = 1, 2, 3,.....n+1
Chứng minh rằng tồn tại hai bộ số
1

i
1
< i
2
< .... < i
r



12

i
1
j
1
1
,
M
2
,....,M
n+1
sao cho tập hợp con { i
1
, i
2
, .... , i
r
}
trong {1, 2, ,... n+1}, là 2
n+1
-1. Nh vậy số lợng
những tập hợp khác trống của S là 2
n
-1 < 2
n+1
-1,
thì trong những tập hợp con ở trên có hai tập hợp
con đều là một tập hợp con của tập hợp S (nguyên
lý Đirichlê) :

3
, k
4
,
k
5
đi qua điểm chung C. Dễ thấy ba điểm A, B, C
không thể đồng thời khác nhau vì tất cả đều nằm
trên đờng tròn k
4
, cả trên k
5
, nhng đờng tròn
chỉ cắt nhay hai điểm. Suy ra, hai điểm nào đó
trong ba điểm A, B, C trùng nhau (nguyên lý

2
Nguyễn Hữu Điển: http:// free.hostdepartment.com/n/nhdien Nguyên lí lồng và thỏ
Đirichlê). Qua điểm trùng này sẽ đi qua tất cả 5
đờng tròn.
Bài 9. Cho A là tập hợp điểm trên đờng tròn sinh
ra bởi một điểm chuyển dịch liên tiếp (theo chiều
kim đồng hồ) trên đờng tròn một cung 1 radian.
Chứng minh rằng một cung bất kỳ trên đờng tròn
đều có chứa những điểm thuộc A.
Lời giải. Ta lấy một cung bất kỳ ký hiệu P
1
P
2
. Ta

0
) = { Q
0
, Q
1
, ...., Q
n
,....} là vô hạn. Thật vậy,
nếu ngợc lại, thì tồn tại hai chỉ số s và t sao cho
Q
s
= Q
t
(Nguyên lý Đirichlê cho dãy số). Nếu s <
t, thì suy ra điểm Q
s
dịch chuyển về chính mình
sau phép lặp t-s radian. Nh vậy, mà cả vòng tròn
có 2

radian, nghĩa là

=
ts
2
. Điều này trái
với tính chất số

là một số vô tỷ.
Nh vậy A( Q

t
bằng

<
2

m
. Nh lý luận phần trên, Q
s
Q

t
, nghĩa là


0. Bây giờ ta xét dãy các điểm R
0
= Q
s
, R
1

= Q
t
, ....., R
n
= Q
s+n(t-s)
,..... thuộc A(Q
0

R
1
R
2
, R
2
R
3
, ..., R
n
R
n+1
phủ kín đờng tròn. Nh
vậy P
1
nằm ở trong cung nào đó R
k
R
k+1
. Nhng vì
độ dài cung R
k
R
k+1
< P
1
P
2
, thì hoặc là R
k+1

n
lớn hơn độ dài của a. Khi đó ít nhất có hai
trong số những đoạn thẳng a
1
, a
2
, ..., a
n
có điểm
chung.
2. Cho những đa diện D
1
, D
2
, ..., D
n
nằm trong
đa diện D và tổng thể tích của D
1
, D
2
, ..., D
n
lớn
hơn thể tích D. Khi đó ít nhất có hai trong số D
1
,
D
2
, ..., D

, khi với mỗi phần tử A thuộc cho tơng
ứng với một số không âm


(A) sao cho thỏa mãn
đẳng thức sau

(A
1

A
2
)=

(A
1
) +

(A
2
)

3
Nguyễn Hữu Điển: http:// free.hostdepartment.com/n/nhdien Nguyên lí lồng và thỏ
với mọi hai phần tử A
1
và A
2
thuộc



, mà chúng thỏa mãn A
i


A (i
=1, 2, ....n) và

(A ) <

(A
1
) +

(A
2
)+ ....+

(A
n
),
thì hai trong số các tập A
1
, A
2
, ...., A
n
có điểm
chung.
Mệnh đề này ta gọi là Nguyên lý Đirichlê

....,M
k
, ở đây k
3
+1

n. Chứng minh rằng có k +1
số chẵn 2j
1
, 2j
2
,..., 2j
k+1
nằm trong cùng một tập
hợp M
i
(1

i

k), sao cho những số 2j
1
-1,
2j
2
-1, ..., 2j
k+1
-1 cũng nằm trong một tập hợp M
r