Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Mục lục
Trang
Mục lục 01
Giới thiệu
Giới thiệu đề tài 02
Giới thiệu nhóm 03
Nội dung đề tài
Chương 1. Đại cương về tổ hợp 04
Chương 2. Bài toán nguyên lý Dirichlet 05
2.1 Nguyên lý Dirichlet 05
2.2 Nguyên lý Dirichlet đối ngẫu 06
2.3 Những lưu ý khi giải bài toán áp dụng nguyên lý Dirichlet 07
Chương 3. Ứng dụng nguyên lí trong giải toán 09
3.1 Ứng dụng nguyên lí trong lĩnh vực lý thuyết tổ hợp 09
3.2 Ứng dụng nguyên lí trong lĩnh vực số học 11
3.3 Ứng dụng nguyên lí trong lĩnh vực hình học 16
3.4 Ứng dụng nguyên lí trong các bài toán khác 25
Kết luận 29
Tài liệu tham khảo 30
1
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Giới thiệu
Giới thiệu về đề tài
Nguyên lý Dirichlet còn goị là nguyên lý chim bồ câu (The Pigeonhole
Principle) hay nguyên lý những cái lồng nhốt thỏ hay nguyên lý xếp đồ vật vào
ngăn kéo (The Drawer Principle)- đưa ra nguyên tắc về sự phân chia, sắp xếp các
phần tử vào các lớp.
Nguyên lý Dirichlet được phát biểu vào năm 1834, do nhà toán học người
Đức - Johann Peter Gustav Lejeune Dirichlet (13/2/1805 - 1859) đề xuất.
Nguyên lý Dirichlet là công cụ hiệu quả để chứng minh nhiều kết quả sâu sắc

4 Lê Quang Huy Giới thiệu
Chương 3
3
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Nội dung đề tài
Chương 1. Đại cương về tổ hợp.
Tổ hợp là một lĩnh vực của toán học rời rạc, là ngành khoa học xuất hiện khá
sớm vào đầu thế kỷ 17. Hiện nay, lý thuyết tổ hợp được áp dụng rộng rãi trong
nhiều lĩnh vực khác nhau như lý thuyết số, hình học, đại số, xác suất thống kê,
khoa học máy tính, hóa học…Tổ hợp đụng chạm đến nhiều vấn đề khác nhau của
toán học nên khó có thể định nghĩa một cách tổng quan.
Nội dung của lý thuyết tổ hợp gắn liền với việc nghiên cứu, phân bố các phần
tử vào các tập hợp. Các phần tử này thường hữu hạn và việc phân bố phải thỏa
mãn những điều kiện nhất định nào đó.
Trong nhiều trường hợp, việc xác định sự tồn tại một cấu hình thỏa mãn tính
chất nào đó có ý nghĩa quan trọng về mặc lý thuyết cũng như thực tế. Vì vậy một
bài toán tổ hợp là một bài toán: “Xét sự tồn tại các cấu hình tổ hợp thỏa mãn tính
chất cho trước”.
Bài toán tồn tại nghiên cứu từ rất lâu và góp phần đáng kể thúc đẩy sự phát
triển của lý thuyết tổ hợp cũng như nhiều ngành toán học khác, các bài toan dưới
đây phần nào cho ta thấy rõ hơn điều đó.
4
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Chương II
Bài toán nguyên lý Dirichlet
2.1 Nguyên lý Dirichlet
2.1.1 Nguyên lý Dirichlet 1 (Nguyên lý chuồng và thỏ)
Nguyên lý Dirichlet khẳng định một sự kiên “hiển nhiên” rằng n+1 con thỏ
không thể xếp vào n chuồng sao cho mỗi con thỏ ở riêng một chuồng . Một cách
tổng quát, nguyên lý này khẳng đinh rằng:

 
 
 
con thỏ, ở đây kí hiệu
[ ]
α
để chỉ phần nguyên của số
α
.
5
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Chứng minh:
Giả sử mọi chuồng thỏ đều không có đến
1 1 1
1 1
n m n n
m m m
+ − − −
     
= + = +
     
     

con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng
1n
m
−
 
 
 

, ,
k
A A
.
a.Nếu mỗi phần tử của S chứa trong ít nhất r tập con
i
A
, thì
1
+ +
k
A A
≥
.r S
b. Nếu mỗi phần tử của S chứa đúng trong r tập con
i
A
, thì
1
+ +
k
A A
=
.r S
Chứng minh:
a. Gọi P là tập tát cả các cặp
( , )s i
∈S.{1,…,k} thỏa s ∈
i
A

i
a
quả bóng
vào vị trí i và kí hiệu
i
A
là tập hợp các quả bóng ở vị trí
, 1, 2i i i+ +
, ở đây
6
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
1, 2i i+ +
được lấy theo modun 12, kí hiệu S là tập hợp tất cả các quả bóng,
0 1 11
S A A A= ∪ ∪ ∪
.
Khi đó mỗi quả bóng chứa đúng trong ba tập
i
A
. Theo nguyên lý Dirichlet
mở rông, ta có:
0 1 11
| | | | | | 3.| |A A A S+ + + =
.
Ta có:
13
3.| | 3.(1 2 12) 3.12. 3.78 234
2
S = + + + = = =
⇒

I ⊂ ¡
Định lý 1: Cho A là một khoảng giới nội,
1 2
, , ,
n
A A A
là các khoảng sao cho
i
A A⊂
(i = 1,2,…n) và
1 2
( ) < ( ) + ( )+ + ( )
n
d A d A d A d A
. Khi đó, có ít nhất hai
khoảng trong số các khoảng trên có một điểm trong chung.
Chứng minh:
Giả sử không có cặp nào trong những khoảng đã cho có điểm trong chung.
Khi đó,
1 2 1 2
( ) = ( ) + ( ) + + ( ) > ( )
n n
d A A A d A d A d A d A∪ ∪ ∪
Mặc khác, từ
i
A A⊂
(i = 1,2,…n), suy ra
1 2
( )
n

Bài toán cơ thể xuất hiện sau khi biến đổi qua một số bược trung gian hay sau
khi thành lập các dãy số mới.
Kết hợp với các phương pháp chứng minh phản chứng để giải toán.
Phải biến đổi để xuất hiện khái niệm “thỏ và lồng” trong bài toán và khái
niệm nhốt thỏ vào lồng.
Trong một bài toán có thể phải sử dụng nguyên lý Dirichlet 2 hay 3 lần mới
giải được.
Phải sử dụng ngôn ngữ thông thường để diễn đạt cho dễ hiểu.
8
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Chương 3
Ứng dụng của nguyên lý Dirichlet
trong giải toán
3.1 Các ứng dụng của nguyên lý Dirichlet trong lĩnh vực lý thuyết tổ hợp
Bài toán 1.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 chuồng thỏ và
đánh số từ 1 đến 365(Chuồng thỏ cuối cùng là ngày 31 tháng 12 năm 1995), số
thanh niên tới dự là thỏ.Chúng ta đặt những thanh niên có cùng ngày sinh vào
cùng một chuồng có số đúng bằng ngày sinh.Vì số thỏ lớn hơn số chuồng nên
theo nguyên lý đirichlê có ít nhất hai con thỏ được đặt vào cùng một
chuồng.Điều đó có nghĩa là họ sinh cùng một ngày.
Bài toán 1.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 chuồng thỏ được đánh số từ 0 đến 14.Chúng ta đặt mỗi con

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í.
Bài toán 1.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 đượ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.
10
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Bài toán 1.6 Một lớp học có 40 học sinh. Chứng minh rằng có ít nhất 4 học
sinh có tháng sinh giống nhau.
Lời giải:
Một năm có 12 tháng (chuồng).
Chia 40 học sinh (con thỏ) vào 12 tháng. Nếu mỗi tháng không quá 3 học sinh
được sinh ra thì số học sinh trong lớp không vượt quá 3.12 = 36 học sinh.
Mà 36 < 40 vô lý.Vậy tồn tại tháng có ít nhất 4 học sinh được sinh ra.
Bài toán 7. Một rừng thông có 800000 cây, mỗi cây có không quá 500000 lá.
Chứng minh rằng tồn tại 2 cây có số lá bằng nhau.
Lời giải:
Số cây thông là thỏ, số lá là lồng.
Lồng 1 ứng với cây chỉ có 1 lá

i
≤ 2n (i= 1,2,…n+1) và trong đoạn [1,2n] chỉ có n số lẻ nên tồn tại hai
số
b =
i j
b
.
Khi đó, trong 2 số
à
i j
a v a
có một số là bội của số kia.
Bài toán 2.2 Biết rằng 3 số a, a + k, a+2k đều là các số nguyên tố lớn hơn 3.
Chứngminh rằng khi đó k chia hết cho 6.
Lời giải:
Do a, a+k, a+2k đều là các số nguyên tố lớn hơn 3, nên chúng đều là các số lẻ
và không chia hết cho 3.
Do a và a + k cùng lẻ nên k = (a + k) − a sẽ chia hết cho 2. (1)
11
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Do a, a + k, a + 2k đều không chia hết cho 3, nên khi chia cho 3 ít nhất hai số
có cùng số dư (theo nguyên Dirichlet). Xảy ra các khả năng sau:
a. Nếu a + k
≡
a(mod3) thì (a + k) − a
≡
0(mod3), suy ra k
M
3.
b. Nếu a + 2k

M
288.
Lời giải:
Ta có phân tích sau : 288 =
2 5
3 .2
và do (2, 3) = 1 nên để chứng minh P
M
288.
Ta chỉ cần chứng minh đồng thời P
M

2
3
và P
M

5
2
.
Theo nguyên lí Dirichlet thì trong n+1 số nguyên tùy ý, luôn tồn tại hai số có
hiệu chia hết cho n. Trong 4 số
1 2 3 4
, , ,a a a a
có hai số có hiệu chia hết cho 3,
không giảm tính tổng quát, có thể cho là:
1 2
-a a

M

. Khi đó hai số còn lại
4 5
,a a
cũng có tính chẵn lẻ giống nhau
nhưng khác với tính chẵn lẻ của
1 2 3
, ,a a a
. Vậy bốn hiệu
1 2 1 3 2 3 4 5
- , - , - , -a a a a a a a a

cũng chia hết cho 2.
Mặt khác, trong 5 số đã cho có ít nhất hai hiệu chia hết cho 4, vì thế trong
bốn số
1 2 1 3 2 3 4 5
- , - , - , -a a a a a a a a
có ít nhất một hiệu chia hết cho 4. Do đó:
1 2 1 3 2 3 4 5
( - )( - )( - )( - )a a a a a a a a

M
5
2
.Tức là P
M
5
2
.
12
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

≡
2
a
( mod 5). Ngoài ra ta có
1
a
≡
2
a
( mod 3). Từ đó ta có
1 2
a a−

M
15.
Mặt khác,
1 2
,a a
cùng lẻ nên
1 2
a a−

M
2.
Do (2,15) =1 nên
1 2
a a−

M
30.

3 4
-a a

M
30.
Lấy hai số
5 6
,a a
bất kì (ngoài
1 2 3 4
, , ,a a a a
đã chọn) thì
5 6
,a a
lẻ (do
5 6
,a a

nguyên tố), nên
5 6
+a a

M
2
Nên
1 2 3 4 5 6
( - )( - )( + )a a a a a a

M
30.30.2 = 1800

3 (theo cách chọn 4 số trên).
Do
3 4 5 6
, , ,a a a a
lẻ nên
5 6
+a a

M
2 và
3 4
-a a

M
2
Suy ra
5 6
+a a

M
10 và
3 4
-a a

M
6
Vậy
1 2 3 4 5 6
( - )( - )( + )a a a a a a


trên thuộc tập hợp {1, 2, . . . , 99}. Vì thế lại theo nguyên lí Dirichlet suy ra các
hiệu trên phải có ít nhất hai hiệu bằng nhau. Giả sử hai hiệu đó tương ứng với hai
cặp (a, b), (c, d), (a # c, b # d), sao cho b − a = d − c. Từ đó ta có: a + d = b + c .
Nếu a = d (hoặc b = c; chú ý những sự bằng nhau khác không thể xảy ra do a # c,
b # d), thì b + c = 2a hoặc d + a = 2b.
Bài toán 2.6 Chứng minh rằng từ 52 số nguyên bất kì luôn có thể chọn ra
được hai số mà tổng hoặc hiệu của chúng chia hết cho 100.
Lời giải:
Tất cả các số dư trong phép chia cho 100, được chia thành từng nhóm
như sau: {0} , {1, 99} , {2, 98} , . . . , {49, 51} , {50} .
Vì có tất cả 51 nhóm, mà lại có 52 số, nên theo nguyên lí Dirichlet giữa
chúng phải có hai số mà các số dư trong phép chia cho 100 rơi vào một nhóm.
Hai số này là hai số cần tìm vì nếu số dư của chúng bằng nhau thì hiệu của chúng
chia hết cho 100, còn nếu số dư của chúng khác nhau thì tổng của chúng chia hết
cho 100.
Bài toán 2.7 Chứng minh rằng từ tập hợp tùy ý gồm n số tự nhiên luôn tách
ra được một tập hợp con (khác rỗng) chứa các số mà tổng của chúng chia hết cho
n.
Lời giải:
Giả sử với một tập hợp nào đó chứa các số
1 2
, , ,
n
a a a
mà không thoả mãn bài
toán.Khi đó không có số nào trong các số :
1 1 2 1 2 1 2
= , = + , , = + + +
n n
S a S a a S a a a

nguyên trong đoạn [100, 200] là: 15150.Nếu trong những số đã cho là:
1 2
, , ,
n
a a a
không có số nào trong danh sách trên, thì
1 2
+ + + <15150-4050=11100
n
a a a
(vô lí).
Nghĩa là trong các số
1 2
, , ,
n
a a a
có ít nhất một số viết ở cơ số 10 có ít nhất
hai chữ số trùng nhau.
Bài toán 2.9 Chứng minh rằng với một số tự nhiên bất kì ,tồn tại một số có
dạng
111 000
n
142 43
mà chia hết cho n.
Lời giải:
Ta xét dãy số
1,11,111, ,111 111
n
14 2 43
và những số dư khi chia dãy số trên cho n.

số có cùng số dư. Giả sử các số đó là:
111 111 à111 111( > )
m n
v m n
14 2 43 142 43
Khi đó: 1 ≤ n < m ≤ p. Vậy:
sô' sô' - sô' sô' - sô'
111 111-111 111=111 111000 0=111 111.10
n
m n m n n m n
14 2 43 14 2 43 142 43 1 2 3 142 43
tích này chia hết cho p vì (p, 10) = 1, suy ra
- sô'
111 111
m n
14 2 43
chia hết cho p và nó cũng
nằm trong dãy trên. Mà 1 ≤ m − n ≤ p mâu thuẫn với giả thiết không có số nào
trong dãy chia hết cho p.
3.3 Các ứng dụng của nguyên lý Dirichlet trong lĩnh vực hình học.
Bài toán 3.1 Trong mặt phẳng cho sáu điểm, trong đó không có ba điểm nào
thẳng hàng. Mỗi đoạn thẳng nối từng cặp điểm được bôi màu đỏ hoặc xanh.
Chứng minh rằng tồn tại ba điểm trong số sáu điểm đã cho, sao cho chúng là ba
đỉnh của một tam giác mà các cạnh của nó được bôi cùng một màu.
Lời giải:

B
5
B
4

1 2 3
, ,B B B
và
1 2 3
, ,B B B
là tam giác với ba cạnh đỏ.
Bài toán 3.2 Cho hình chóp đáy là đa giác chín cạnh. Tất cả các cạnh bên và
27 đường chéo của đa giác đáy được bôi bằng một trong hai màu đỏ hoặc xanh.
Chứng minh rằng tồn tại ba đỉnh của hình chóp sao cho chúng là những đỉnh của
hình tam giác với các cạnh được bôi cùng màu.
Lời giải:
Xét chín cạnh bên. Vì 9 cạnh này chỉ được bôi bằng hai màu đỏ hoặc xanh,
nên theo nguyên lí Dirichlet tồn tại năm cạnh bên được bôi cùng màu. Không
giảm tính tổng quát có thể cho đó là các cạnh bên
1 2 3 4 5
, , , ,SA SA SA SA SA
được bôi
cùng màu đỏ, các điểm
1 2 3 4 5
, , , ,A A A A A
xếp ngược chiều kim đồng hồ.
Xét đa giác
1 2 3 4 5
, , , ,A A A A A
. Có hai khả năng xảy ra:
a. Nếu
1 2
A A
là đường chéo của đáy, khi đó dĩ nhiên
2 4 4 1

A
5
A
4
A
3
A
2
A
1
S
Hình 3.2
b. Nếu
1 2
A A
là cạnh đáy. Khi đó dĩ nhiên
1 3 3 5
,A A A A
chắc chắn là đường chéo
đáy.
i. Nếu
1 5
A A
là đường chéo đáy thì ta quay về trường hợp a. vừa xét, với
1 3 5
A A A
là tam giác với ba cạnh là ba đường chéo đáy.
ii. Nếu
1 5
A A

A
5
A
4
A
3
A
2
A
1
18
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

A
5
A
4
A
3
A
2
A
1
Hình 3.3
ii2. Nếu
2 3
A A
là cạnh đáy. Khi đó xét tam giác
2 3 5
A A A

Bài toán 3.4 Trên mặt phẳng cho 25 điểm. Biết rằng ba điểm bất kì trong 25
điểm đó luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình
tròn bán kính bằng 1 chứa không ít hơn 13 điểm đã cho.
Lời giải:

B
A
Hình 3.5
Lấy A là một trong số 25 điểm đã cho. Xét hình tròn
1
Ω ( ;1)A
tâm A, bán kính
bằng 1. Có hai khả năng xảy ra:
a. Nếu tất cả các điểm đã cho nằm trong
1
Ω
thì kết luận của bài toán hiển
nhiênđúng.
b. Tồn tại điểm
BA ≠
(B thuộc trong số 25 điểm đã cho), sao cho
B
∉

1
Ω
. Vì
B
∉
1

tại hình tròn bán kính 1 chứa không ít hơn n + 1 điểm đã cho.
Bài toán 3.5 Cho một bảng kích thước 2n×2n ô vuông. Người ta đánh dấu
vào 3n ô vuông bất kì của bảng. Chứng minh rằng có thể chọn ra n hàng và n cột
của bảng sao cho các ô được đánh dấu đều nằm trên n hàng và n cột này.
Lời giải:
Chọn ra n hàng có chứa ô được đánh dấu nhiều trên hàng đó nhất. Ta chứng
minh rằng số ô được đánh dấu còn lại nhỏ hơn hoặc bằng n.
Giả sử ngược lại, tức là giả sử số ô được đánh dấu còn lại lớn hơn hoặc bằng
n+1. Số các hàng còn lại chưa chọn là n. Vậy theo nguyên lí Dirichlet sẽ có ít
nhất một hàng (trong số n hàng còn lại) chứa ít nhất hai ô đánh dấu.

Hình 3.6
Chú ý rằng theo cách chọn thì n hàng đã chọn chứa số ô được đánh dấu nhiều
trên hàng đó nhất. Có một hàng còn lại chưa chọn có ít nhất hai ô đánh dấu, nên
suy ra mọi hàng trong số n hàng đã chọn đều có ít nhất hai ô được chọn, tức là
trên n hàng đã chọn có không ít hơn 2n ô đã được đánh dấu.
21
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Nếu vậy, số ô được đánh dấu lớn hơn hoặc bằng 2n+(n+1) > 3n. Vô lí (vì chỉ
có 3n ô được đánh dấu).
Như vậy, sau khi đã chọn ra n hàng (với cách chọn như trên), theo như chứng
minh trên còn lại không quá n ô được đánh dấu. Vì thế có nhiều lắm là n cột chứa
chúng.
Vì lẽ đó sẽ không thấy ô đánh dấu nào nằm ngoài các hàng hay cột đã chọn.
Bài toán 3.6 Cho 1000 điểm
1 2 1000
, , ,M M M
trên mặt phẳng. Vẽ một đường
tròn bán kính bằng 1 tùy ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao
cho:

1 2
=2S S
1 2 2 2
+S M S M
≥
1 2
=2S S
…
1 1000 2 1000
+S M S M
≥
1 2
=2S S
Cộng từng vế của 1000 bất đẳng thức trên ta có:
1 1 1 2 1 1000 2 1 2 2 2 1000
( + + +S )+( + + +S )>2000S M S M M S M S M M
(*)
22
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Từ bất đẳng thức (*) và theo nguyên lí Dirichlet suy ra trong hai tổng của vế
trái của (*) có ít nhất một tổng lớn hơn hoặc bằng 1000.
Giả sử:
1 1 1 2 1 1000
( + + +S )>1000S M S M M
Khi đó chọn S chính là
1
S
. Bài toán đã được chứng minh.
Bài toán 3.7 Trên đoạn thẳng có độ dài bằng 1 ta tô một số đoạn thẳng sao
cho khoảng cách giữa hai điểm được tô bất kì không bằng 0, 1. Chứng minh rằng

3
có cùng một màu sơn. Mặc khác, trên đường tròn đó luôn tìm được hai điểm
mà khoảng cách giữa chúng bằng 1. Mâu thuẫn với giả sử.
Vậy luôn tìm được hai điểm cùng màu mà khoảng cách giữa chúng bằng 1.
Bài toán 3.9 Cho dãy vô hạn các số tự nhiên
1 2
, , u u
được xác định theo
công
thức truy hồi sau:
1
+1
=3
=( +1) - +1
n n
u
u n u n
(n = 1,2,…)
Giả sử n là số tự nhiên bất kì và tập M gồm
n
u
điểm sao cho không có ba
điểm nào thẳng hàng. Mỗi đoạn thẳng nối hai điểm khác nhau trong M được tô
23
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
bằng một trong n màu cho trước. Chứng minh rằng tồn tại ba điểm trong M là
đỉnh của một tam giác cùng màu.
Lời giải:
Ta chứng minh bằng quy nạp theo n.
a. Với n = 1, ta có

n
u
đoạn thẳng bôi màu. Theo công thức
xác định dãy ta có:
+1
-1=( +1) - +1-1=( +1)( -1)+1
n n n
u n u n n u
Từ đẳng thức trên, theo nguyên lí Dirichlet có ít nhất
n
u
đoạn thẳng có chung
đỉnh A được bôi màu.Giả sử
1 2
, , ,
n
u
AB AB AB
được bôi cùng màu và giả sử đó là
màu
µ
, thì tam giác
i j
AB B
cùng màu
µ
, (
µ
thuộc vào một trong n + 1 màu
đã cho).

n
u
B B B
thì không có ba điểm nào thẳng hàng.
Dùng tối đa (n + 1) − 1 = n màu để tô (do không dùng màu
µ
).
Theo giả thiết quy nạp tồn tại tam giác cùng màu.
Vậy bài toán đúng với n + 1.
24
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
3.4 Các ứng dụng của nguyên lý Dirichlet trong các bài toán khác.
Bài toán 4.1 Đối với mỗi giá trị n
∈
¥
, hãy tìm số k lớn nhất k
∈
¥
thoả
mãn tính chất sau: Trong tập hợp gồm n phần tử có thể chọn ra k tập hợp con
khác nhau, sao cho hai tập con bất kì đều có giao khác
∅
?.
Lời giải:
Cố định phần tử
i
a
của tập
1 2
={ , , , }

cặp được tạo bởi từ một tập con của X và phần
bù của nó. Theo nguyên lí Dirichlet có ít nhất 2 tập con đã chọn tạo thành 1 cặp,
suy ra chúng không giao nhau. Vậy k =
-1
2
n
.
Bài toán 4.2 Cho
1 2 3
, , x x x
là dãy vô hạn các số nguyên và k là một số tự
nhiên bất kì. Chứng minh rằng tồn tại dãy số gồm những phần tử liên tiếp của
dãy, mà tổng của chúng chia hết cho k.
Lời giải:
Ta có thể giới hạn lại, trong mọi bộ k phần tử liên tiếp của dãy để đơn giản ta
xét dãy gồm k phần tử đầu tiên:
1 2
, , ,
k
x x x
. Bây giờ ta xét các tổng:
1 1 2 1 2 1 2
= , = + , , = + + +
k k
S x S x x S x x x
Nếu một tổng nào đó trong số các tổng trên chia hết cho k, thì bài toán được
giải. Ngược lại, các số
1 2
, , ,
k

, , ,
k
i i
u u u
nguyên tố cùng nhau.
25