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
1.1 Sơ lược lịch sử 04
1.2 Bài toán tổ hợp 07
Chương 2. Bài toán nguyên lý Dirichlet 09
2.1 Nguyên lý Dirichlet 09
2.2 Nguyên lý Dirichlet đối ngẫu 10
2.3 Những lưu ý khi giải bài toán áp dụng nguyên lý Dirichlet 11
Chương 3. Ứng dụng nguyên lí trong giải toán 12
3.1 Ứng dụng nguyên lí trong lĩnh vực lý thuyết tổ hợp 12
3.2 Ứng dụng nguyên lí trong lĩnh vực số học 13
3.3 Ứng dụng nguyên lí trong lĩnh vực hình học 17
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
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.

Chương 3
2 Nguyễn Thị Kim
Thoa
Chương 2
Chương 3
3 Đinh Thị Thuỷ Chương 2
Chương 3
4 Lê Quang Huy Giới thiệu
Chương 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 đó.
1.1Sơ lược lịch sử
Có thể nói tư duy tổ hợp ra đời từ rất sớm. Vào thời nhà Chu – Trung Quốc
người ta đã biết đến những hình vuông thần bí. Thời cổ Hy Lạp – thế kỉ thứ 4

Khi n=64 ta có số lần di chuyển là 18 446 744 073 709 551 615
1.1.2 Bài toán xếp n cặp vợ chồng
Bài toán này cũng do Lucas đưa ra năm 1891. Bài toán phát biểu như sau: Có
n cặp vợ chồng cần xếp vào bàn tròn sao cho không có cặp nào ngồi gần nhau.
Có bao nhiêu cách xếp như vậy?
Bài toán này dẫn đến việc ngiên cứu một khái niệm quan trọng là số phân bố
và mãi đến năm 1934 mới có lời giải.
Số cách xếp là trong đó là số phân bố. Bảng sau cho thấy sự bùng
nổ tổ hợp ghê gớm của số phân bố.
n = 4 5 6 7 8 9 10 11

=
2
13 80 579
4
738
43
387
439
792
4 890
741
1.1.3 Bài toán đường đi quân ngựa trên bàn cờ
Cho bàn cờ vua với kích thước 8 x 8 = 64 ô. Tìm đường đi của quân ngựa qua
tất cả các ô, mỗi ô chỉ 1 lần, và quay về ô xuất phát. Người ta chứng minh tổng
quát được rằng: Trên bàn cờ vuông có số cạnh chẵn lớn hơn hoặc bằng 6 bao giờ
cũng tồn tại đường đi.
Đường đi của Euler (1759) có tính chất: hiệu các ô đối xứng qua tâm bàn cờ
bằng 32.
37 62 43 56 35 60 41 50

2
29 44 53
6
27
31 46 49
4
25
8
55 42
50
3
32 45 56 41 26
7
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
33 62 15 20
9
24 39 58
16 19 34 61 40 57 10 23
63 14 17 36 21 12 59 38
18 35 64 13 60 37 22 11
1.1.4 Hình vuông la tinh
Hình vuông la tinh cấp n là hình vuông gồm các số 1, 2, …, n – 1, n thỏa mãn
tổng mỗi hàng và tổng mỗi cột đều bằng nhau và bằng
Hình vuông la tinh chuẩn cấp n là hình vuông la tinh cấp n có dòng đầu và
cột đầu là 1, 2, …, n.
Bảng sau đây là hình vuông la tinh chuẩn cấp 7
1
2
3 4 5
6

6
Coonh thức tính số hình vuông la tinh đến nay vẫn còn bỏ ngỏ. Tuy nhiên, ta
có thể lập chương trình liệt kê tất cả hình vuông la tinh chuẩn. Dưới đây là một
số giá trị
n = 1
2
3 4 5 6 7
=
1
1
1 4
56
9
408
16 942
080
( là số hinh vuông la tinh chuẩn cấp n).
1.1.5 Hình lục giác thần bí
Năm 1910 Cifford Adams đưa ra bài toán hình lục giác thần bí sau: Trên 19
ô lục giác hãy điền các số từ 1 đến 19 sao cho tổng theo sáu hướng của lục giác
bằng nhau (= 38).
Sau 47 năm trời kiên nhẫn cuối cùng ông cũng tìm ra lời giải. Nhưng do sơ ý
đánh mất bản thảo ông đã tốn thêm 5 năm nữa để khôi phục lời giải. Năm 1962
Adams công bố lời giải. Đây cũng là lời giải duy nhất.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

2
1
7
4

B là tập hợp các quân cờ đen
S là sơ đồ sắp xếp các quân cờ trên bàn cờ
R là hệ thống các điều kiện được xác định bằng luật cờ vua
Ví dụ:Bài toán tháp Hà Nội
A là tập hợp n đĩa
S là sơ đồ sắp xếp các đĩa trên 3 cọc
là điều kiện mỗi lần chuyển 1 đĩa từ một cọc sang cọc khác
là điều kiện đĩa nằm dưới lớn hơn đĩa nằm trên
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Cấu hình tổ hợp là một cách sắp xếp các đĩa trên 3 cọc thỏa các điều kiện
và .
Ví dụ: Bài toán đường đi quân ngựa trên bàn cờ
A là tập hợp các ô trên bàn cờ, có thể biểu diễn như sau
S là sơ đồ sắp xếp tất cả các ô của A thành một vòng khép kín
R là điều kiện từ mỗi ô trên vòng có thể đi đén các ô kề theo quy tắc đi của
quân ngựa.
1.2.2 Các dạng bài toán tổ hợp
Bài toán tồn tại
Mục tiêu của bài toán tồn tại là chứng minh sự tồn tại hoặc không tồn tại của
cấu hình tổ hợp nào đó.
Có những bài toán loại này rất khó và việc cố gắng giải chúng đã thúc đẩy sự
phát triển nhiều hướng nghiên cứu toán học.
Ví dụ: Cho n nguyên dương
A là tập hợp n x n điểm
S là tập hợp 2n điểm trong A
R là điều kiện không có 3 điểm trong S thẳng hàng
Với cấu hình tổ hợp tồn tại. Nhưng bài toán chưa có lời giải với
.
Bài toán đếm
Nội dung bà toán đếm là trả lời câu hỏi: “Có bao nhiêu cấu hình tổ hợp thuộc

tổng quát, nguyên lý này khẳng đinh rằng:
Nếu có m đối tượng xếp vào n hộp và thì tồn tại hộp chứa ít nhất 2 đối
tượng.
Chứng minh:
Nguyên lý này rất dễ kiểm tra:
Nếu không có hộp nào chứa ít nhất 2 đối tượng, thì số đối tượng không lớn hợn
n, mâu thuẫn với giả thuyết số đối tượng m lớn hơn số hộp n.
Tuy rằng với nguyên lý này người ta chỉ chứng minh được sự tồn tại mà
không đưa ra phương pháp tìm được vật cụ thể,nhưng trong thực tế nhiều bài
toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Ngày nay chúng ta đã có những tổng
quát hóa rất mạnh của nguyên lý này trong các ứng dụng không tầm thường như
các định lý kiểu Ramsey, phương pháp xác suất…
Mặc dù nguyên lý Dirichlet được phát biểu rất đơn giản nhưng cái khó của nó
là phải xác định được xem thỏ là gì, chuồng là gì.
Ví dụ minh họa:
Một lớp có 30 học sinh. Chứng tỏ trong lớp tìm thấy ít nhất 2 học sinh có tên
bắt đầu bằng một chữ cái giống nhau.
Lời giải:
Bảng chữ cái tiếng Việt có 29 chữ cái (lồng).
Lớp có 30 học sinh (thỏ).
Số học sinh nhiều hơn số chữ cái nên có ít nhất 2 học sinh có tên bắt đầu bằng
một chữ cái giống nhau.
2.1.2 Nguyên lý Dirichlet 2
Nếu nhốt n con thỏ vào cái chuồng thì tồn tại một chuồng có ít nhất
con thỏ, ở đây kí hiệu để chỉ phần nguyên của số .
Chứng minh:
Giả sử mọi chuồng thỏ đều không có đến
con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng con.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Suy ra tổng số con thỏ không vượt quá con.(Vô lý vì có n con

2.2.1 Nguyên lý Dirichlet đối ngẫu hữu hạn phần tử.
Cho tập hữu hạn và là các tập con của S sao cho
≥ . Khi đó, tồn tại một phần tử x
∈
S sao cho x là phần tử
chung của k+1 tập (i = 1,2,…, n).
2.2.2 Nguyên lý Dirichlet đối ngẫu vô hạn phần tử.
a. Tập phần tử là một khoảng trên đường thẳng.
Kí hiệu d(I) là độ dài của khoảng
Định lý 1: Cho A là một khoảng giới nội, là các khoảng sao cho
(i = 1,2,…n) và . 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 đó,
Mặc khác, từ (i = 1,2,…n), suy ra ≤
Mâu thuẫn. Vậy ít nhất có hai khoảng trong số các khoảng trên có điểm trong
chung.
b. Tập phần tử là miền phẳng giới hạn bởi đường cong phẳng khép kín.
Kí hiệu S(A) là diện tích bề mặt A.
Định lý 2:
Nếu A là một bề mặt được giới hạn bởi đường cong phẳng khép
kín, còn là các bề mặt sao cho (i = 1,2,…n) và
thì ít nhất có 2 bề mặt trong số các bề mặt trên có
điểm trong chung.
Chứng minh: Chứng minh tương tự định lý 1
2.3 Những lưu ý khi giải bài toán áp dụng nguyên lý Dirichlet
Các bài toán áp dụng nguyên lý Dirichlet thường là bài toán chứng minh sự tồn
tại của sự vật, sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc
đó.

mắc.Nếu không có ba học sinh nào có số lỗi bằng nhau thì trong mỗi chuồng
mang số từ 0,…,13 sẽ có nhiều nhất hai học sinh.Khi đó số lượng của những học
sinh này nhiều nhất là 28 cộng với học sinh mắc 14 lỗi trong chuồng số 14 chúng
ta sẽ nhận được nhiều nhất là 29 học sinh viết chính tả,điều này dẫn đến sự mâu
thuẫn với giả thiết có 30 học sinh của bài toán.
Bài toán 1.3 Chứng minh rằng trong mỗi nhóm bạn 5 người có ít nhất hai
người có cùng số lượng người quen giữa những người trong nhóm đó.
Lời giải:
Chúng ta xét năm chuồng được đánh số từ 0 đến 4, mỗi người trong nhóm
được đặt vào một chuồng mang số trùng với số người trong nhóm mà người đó
quen.Ta xét hai trường hợp sau:
a. Nếu có một người không quen ai trong số những người còn lại thì chuồng
số 4 trống (vì ngược lại thì cả ngăn 0 và 4 đều không trống,dẫn đến vô lí).Như
vậy,mỗi người trong số 5 người được đặt vào các chuồng mang số 0,1,2,3 với
số lượng 4 chuồng.Từ nguyên lý Đirichlê suy ra ít nhất có hai người ở cùng một
chuồng.Hay là họ có chung số lượng người quen.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
b. Nếu mọi người ai cũng có người quen,mỗi người sẽ được đặt vào các
chuồng mang số 1,2,3,4 với số lượng 4 chuồng. Từ nguyên lý Đirichlê suy ra ít
nhất có hai người ở cùng một chuồng.Hay là họ có chung số lượng người quen.
Bài toán 1.4 Trong một khu tập thể sống 123 người. Tổng số tuổi của họ là
3813. chứng minh rằng có thể chọn 100 người sống ở khu tập thể này mà tổng số
tuổi của họ không nhỏ hơn 3100.
Lời giải:
Chúng ta hãy chọn 100 người nhiều tuổi nhất và giả sử tổng số tuổi của họ
nhỏ hơn 3100.Khi đó người trẻ nhất trong số người được chọn là 3100:100=31
tuổi.Mặt khác người này không trẻ hơn 23 người còn lại theo cách chọn.Khi đó
tổng số tuổi của 23 người này không lớn hơn 23.31=713.Suy ra tổng số tuổi của
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ọ

Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
3.2 Các ứng dụng của nguyên lý Dirichlet trong lĩnh vực số học.
Bài toán 2.1 Chứng minh rằng trong n+1 số thuộc {1,2,…,2n} luôn chọn
được 2 số mà số này là bội của số kia.
Lời giải:
Viết n+1 số đã cho dưới dạng
Trong đó là các số lẻ
là số nguyên không âm
Mà 1≤ ≤ 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ố .
Khi đó, trong 2 số 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)
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 3.
b. Nếu a + 2k a + k(mod3) thì (a + 2k) − (a + k) 0(mod3), suy ra k 3.
c. Nếu a + 2k a(mod3) thì (a + 2k) − a 0(mod3), suy ra 2k 3
Do (2,3) = 1 suy ra k 3.(2)
Tóm lại, trong mọi trường hợp ta đều thấy k 3. Lại do (2, 3) = 1 nên từ (1)
và (2) suy ra k 6.
Bài toán 2.3 Cho 5 số nguyên phân biệt tùy ý .
Xét tích:
Chứng minh rằng P 288.
Lời giải:
Ta có phân tích sau : 288 = và do (2, 3) = 1 nên để chứng minh P 288.

cho ( mod 5). Ngoài ra ta có ( mod 3). Từ đó ta có 15.
Mặt khác, cùng lẻ nên 2.
Do (2,15) =1 nên 30.
b. Xét 7 số còn lại: Theo nguyên lí Dirichlet tồn tại bốn số đồng dư với nhau
theo mod 3. Lấy 4 số này chia cho 5 có hai khả năng xảy ra:
i. Nếu có hai số chẳng hạn ( gọi là ) mà (mod5). Từ đó suy
ra 5
Mà 3, 2 và (2,3,5) =1 nên suy ra 30.
Lấy hai số bất kì (ngoài đã chọn) thì lẻ (do
nguyên tố), nên 2
Nên 30.30.2 = 1800
ii. Nếu 4 số này khi chia cho 5 các số dư khác nhau là {1, 2, 3, 4}.
Giả sử 1(mod5), 4(mod5) thì ta có:
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
5(mod5), suy ra 5
Với hai số còn lại thì rõ ràng 3 (theo cách chọn 4 số trên).
Do lẻ nên 2 và 2
Suy ra 10 và 6
Vậy 30.10.6=1800
Tóm lại, luôn tồn tại phân biệt sao cho
1800
Bài toán 2.5 Tập hợp các số 1, 2, 3, , . . . , 100 được chia thành 7 tập hợp con.
Chứng minh rằng ít nhất ở một trong các tập con ấy tìm được 4 số a, b, c, d sao
cho a + b = c + d hoặc ba số e, f, g sao cho e + f = 2g.
Lời giải:
Theo nguyên lí Dirichlet suy ra có ít nhất một tập hợp con chứa không ít hơn
15 phần tử (vì nếu trái lại tất cả các tập con chứa không nhiều hơn 7.14 = 98
phần tử. Do 98 < 100 nên sẽ dẫn đến mâu thuẫn).
Xét một cặp số (a, b) trong đó a > b của tập hợp này.
Ứng với mỗi cặp (a, b) này ta xét hiệu a − b (rõ ràng a − b > 0). Vì tập này có

mà chúng thoả mãn: ≥ 11100. Chứng minh rằng giữa các số này có ít
nhất một số, mà viết nó ở dạng thập phân có ít nhất hai chữ số giống nhau.
Lời giải:
Chúng ta lập danh sách các số trong [100, 200], mà chúng viết ở hệ thập phân
ít nhất có hai chữ số trùng nhau: 100, 101, 110, 111, 112, 113, 114, 115, 116,
117, 118, 119,121, 131, 141, 151, 161, 171, 181, 191, 199, 200.
Tổng của tất cả các số nói trên là 4050. Mặt khác tổng của tất
cả các số nguyên trong đoạn [100, 200] là: 15150.Nếu trong những
số đã cho là: không có số nào trong danh sách trên, thì
(vô lí).
Nghĩa là trong các số 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 mà chia hết cho n.
Lời giải:
Ta xét dãy số và những số dư khi chia dãy số trên cho n.
Vì dãy số đã cho gồm n phần tử, nên số dư dương khác nhau khi chia chúng cho
n có n−1 phần tử. Có thể giả thiết không có một số nào trong dãy trên chia hết
cho n vì nếu ngược lại thì bài toán đã được giải. Khi đó sẽ có hai số trong chúng,
ví dụ: mà khi chia chúng cho n sẽ cho cùng một số dư.
Do đó: sẽ chia hết cho n.
Bài toán 2.10 Cho p là số nguyên tố lớn hơn 5. Chứng minh rằng tồn tại một
số có dạng 111 . . . 11 mà chia hết cho p.
Lời giải:
Ta xét dãy số :
Nếu trong dãy trên không có số nào chia hết cho p, thì ta cho tương ứng mỗi
số với số dư của phép chia. Tập hợp các số dư chỉ có 1, 2, 3, . . . , p − 1 gồm p −
1 phần tử (vì số 0 không thể có trong tập này).
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Nhưng vì chúng ta có p số ở dạng trên, nên theo nguyên lí Dirichlet tồn tại hai

a. Nếu ít nhất một trong ba đoạn màu xanh thì tồn tại một
tam giác với ba cạnh xanh và kết luận của bài toán đúng trong trường hợp
này.
b. Nếu không phải như vậy, tức là màu đỏ, thì ba điểm phải
tìm là và 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.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
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 được bôi
cùng màu đỏ, các điểm xếp ngược chiều kim đồng hồ.
Xét đa giác . Có hai khả năng xảy ra:
a. Nếu là đường chéo của đáy, khi đó dĩ nhiên cũng là các
đường chéo của đáy.
Khi đó hai khả năng xảy ra:
i. Nếu cả ba đoạn cùng bôi màu xanh. Khi đó
là ba đỉnh cần tìm, vì tam giác là tam giác với ba cạnh xanh.
ii. Nếu một trong các đoạn là đỏ. Giả sử đỏ, thì
là tam giác với ba cạnh đỏ. Lúc này là ba đỉnh cần tìm.

A
5
A
4
A

4
A
3
A
2
A
1

A
5
A
4
A
3
A
2
A
1
Hình 3.3
ii2. Nếu là cạnh đáy. Khi đó xét tam giác và quay về trường hợp a.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Bài toán 3.3 Trong hình vuông đơn vị (cạnh bằng 1) có 101 điểm. Chứng
minh rằng có năm điểm trong các điểm đã chọn được phủ bởi một đường tròn
bán kính bằng .
Lời giải:
Chia hình vuông đơn vị thành 25 hình vuông nhỏ bằng nhau, mỗi cạnh
của hình vuông nhỏ là 0.2. Vì có 101 điểm, mà chỉ có 25 hình vuông nhỏ,
nên theo nguyên lí Dirichlet tồn tại hình vuông nhỏ chứa ít nhất năm điểm (
trong 101 điểm đã cho). Vì hình vuông này nội tiếp trong đường tròn bán kính
.

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.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

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.
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 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: ≥ 1000.
Lời giải:
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

M
1000
M

Bài toán 3.8 Những điểm trong mặt phẳng được sơn bằng một trong ba màu.