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.

Nguyên lý Dirichlet là công cụ hiệu quả để chứng minh nhiều kết quả sâu sắc
trong nhiều lĩnh vực khác nhau của toán học. Trong nhiều trường hợp sử dụng
nguyên lý này người ta chứng minh được sự tồn tại một cách dễ dàng và cụ thể
mà không đưa ra được phương pháp tìm một vật cụ thể, đối với những bài toán
chỉ cần chỉ ra sự tồn tại là đủ rồi.
Nội dung của nguyên lý này rất đơn giản, dễ hiểu nhưng có tác dụng rất lớn,
có nhiều ứng dụng trong lập luận giải toán.
Nguyên lý Dirichlet có ứng dụng trong rất nhiều dạng bài tập của nhiều lĩnh
vực khác nhau trong toán học, tuy nhiên trong phạm vi đề tài chúng em chỉ chú
trọng khai thác “Các ứng dụng của nguyên lý Dirichlet trong các bài toán tổ hợp,
số học và hình học”.
Ngoài phần giới thiệu, tiểu luận gồm ba chương và danh mục tài liệu tham
khảo.
Chương 1. Giới thiệu đại cương về bộ môn lý thuyết tổ hợp.
Chương 2. Các kiến thức cơ bản về nguyên lý Dirichlet dung để giải toán
trong các chương sau.
Chương 3. Trình bày các ứng dụng của nguyện lý Dirichlet trong việc giải bài
tập.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Giới thiệu về nhóm
STT Họ tên Công việc
(theo mục
lục)
Chữ
ký
Nhận xét
của giáo viên
1 Vũ Hứa Hạnh
Nguyên
Chương 1

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

trước Công nguyên, nhà triết học Kxenokrat đã biết cách tính số các từ khác nhau
lập từ bảng chữ cái cho trước. Nhà toán học Pitagor và học trò đã tìm ra được
nhiều số có tính chất đặc biệt. Ví dụ, 36 không những là tổng của 4 số chẵn và 4
số lẻ đầu tiên, mà còn là tổng lập phương của 3 số tự nhiên đầu tiên

Từ định lý Pitagor người ta cũng đã tìm ra những số mà bình phương của nó
bằng tổng bình phương của 2 số khác. Các bài toán như vậy đòi hỏi phải có nghệ
thuật tổ hợp nhất định. Tuy nhiên có thể nói rằng, lý thuyết tổ hợp được hình
thành như một ngành toán học mới vào thế kỉ 17 bằng một loạt công trình nghiên
cứu của các nhà toán học xuất sắc như Pascal, Fermat, Euler, Leibnitz, …
Các bài toán tổ hợp có đặc trưng bùng nổ tổ hợp với số cấu hình tổ hợp khổng
lồ. Việc giải chúng đòi hỏi một khối lượng tính toán khổng lồ (có trường hợp mất
hàng chục năm). Vì vậy trong thời gian dài, khi mà các ngành toán học như phép
tính vi phân, phép tính tích phân, phương trình vi phân, …phát triển như vũ bão,
thì dường như nó nằm ngoài sự phát triển và ứng dụng của toán học. Tình thế
thay đổi từ khi xuất hiện máy tính và sự phát triển của toán học hữu hạn. Nhiều
vấn đề tổ hợp đã được giải quyết trên máy tính. Từ chỗ chỉ nghiên cứu các trò
chơi, tổ hợp đã trở thành ngành toán học phát triển mạnh mẽ, có nhiều ứng dụng
trong các lĩnh vực toán học, tin học,…
Chúng ta sẽ đi vào nghiên cứu, tìm hiểu một số bài toán nổi tiếng trong lịch
sử.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
1.1.1 Bài toán tháp Hà Nội
Bài toán này do Edouard Lucas đưa ra vào cuối thế kỉ 19(ông cũng là người
đưa ra dãy Fibonacci). Bài toán phát biểu như sau: Có 3 cọc, cọc thứ nhất có n
đĩa kích thước khác nhau, xếp chồng nhau, đĩa nhỏ nằm trên đĩa lớn. Hãy chuyển
các đĩa từ cọc thứ nhất sang cọc thứ ba, sử dụng cọc trung gian thứ hai sao cho
luôn đảm bảo đĩa nhỏ nằm trên đĩa lớn. Hãy đếm số lần di chuyển đĩa. Tìm
phương án di chuyển tối ưu.
Số lần di chuyển là

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

44 55 36 61 42 49 34 59
63 38 53 46 57 40 51 48
54 45 64 39 52 47 58 33
1
26 15 20
7
32 13 22
16 19
8
25 14 21
6
31
27
2
17 10 29
4
23 12
18
9
28
3
24 11 30
5
Đường đi của Beverle (1848) có tính chất: tổng các ô trên cột và hàng bằng
260.
1
30 47 52
5
28 43 54
48 51

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

7
2
3
4 5 6
7
1
3
4
5 6 7
1
2
4
5
6 7 1
2
3
5
6
7 1 2
3
4
6
7
1 2 3
4
5
7
1
2 3 4
5

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

5
8
6
11
18
17
3
19
16
12
10
13
15
14
9
1.2 Bài toán tổ hợp
Qua các bài toán trên ta thấy bài toán tổ hợp rất đa dạng, liên quan đến nhiều
lĩnh vực khoa học và đời sống khác nhau.
Có thể nói một cách tổng quát rằng lý thuyết tổ hợp nghiên cứu việc phân
bố,sắp xếp các phần tử của một hoặc nhiều tập hợp, thỏa mãn một số điều kiện
nào đó.
Mỗi cách phân bố sắp xếp như thế gọi là một cấu hình tổ hợp.
1.2.1 Cấu hình tổ hợp
Cho các tập hợp . Giả sử S là sơ đồ sắp xếp các phần tử của
, được mô tả bằng các quy tắc sắp xếp và là các điều kiện ràng buộc lên
mỗi sắp xếp theo sơ đồ S. Khi đó mỗi sắp xếp các phần tử của thỏa mãn
các điều kiện gọi là một cấu hình tổ hợp trên các tập .
Ví dụ: Xét sự bố trí các quân cờ trên bàn cờ vua. Mỗi thế cờ có thể coi là một
cấu hình tổ hợp. Ở đây ta có thể định nghĩa
A là tập hợp các quân cờ trắng

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

dạng đàn xét?”. Phương pháp đếm cấu hình tổ hợp thường dựa vào một số quy
tắc, nguyên lý đếm và phân rã đưa về các cấu hình tổ hợp đơn giản. Khi việc xác
định chính xác số cấu hình tổ hợp gặp khó khăn, có thể ước lượng cận trên và cận
dưới của nó. Bài toán đếm được áp dụng vào những công việc như tính xác suất
hay tính độ phức tạp thuật toán.
Ví dụ: Đếm số tập con của một tập hợp.
Hoặc đếm số nghiệm nguyên dương của phương trình x + y + z = 10
Bài toán liệt kê
các bài toán loại này nghiên cứu những thuật toán hiệu quả để xây dựng tất cả
các cấu hình tổ hợp đã cho. Nhiều vấn đề trong lĩnh vực khác nhau thường được
đưa về bài toán liệt kê và kiểm tra xem các cấu hình tổ hợp có thỏa mãn tính chất
cho trước hay không.
Ví dụ: Liệt kê tất cả các hoán vị của n phần tử.
Bài toán tối ưu tổ hợp
Trong nhiều vấn đề, mỗi cấu hình tổ hợp được gán một giá trị bằng số (chẳng
hạn như hiệu quả sử dụng, hay chi phí thực hiện). Khi đó bài toán tối ưu tổ hợp
nghiên cứu những thuật toán tìm cấu hình tổ hợp có giá trị tối ưu (lớn nhất hoặc
nhỏ nhất).
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Ví dụ: (Bài toán ba lô). Một nhà thám hiểm dùng một cái ba lô trọng lượng
không quá b để mang đồ vật. Có n đồ vật 1, 2,…,n. Đồ vật thứ j có trọng lượng
và giá trị sử dụng là j = 1, 2, …n. Hỏi nhà thám hiểm cần mang theo
những đồ vật nào để tổng giá trị sử dụng là lớn nhất?
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:
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

thỏ). Vậy giả sử sai. Nên nguyên lý được chứng minh.
Ví dụ minh họa:
Một trạm y tế có 150 bệnh nhân thì trong đó có ít nhất Vậy
có 6 người có tên bắt đầu bằng một chữ cái giống nhau.
2.1.3 Nguyên lý Dirichlet mở rộng
Giả sử tập hữu hạn S có các tập con .
a.Nếu mỗi phần tử của S chứa trong ít nhất r tập con , thì
≥
b. Nếu mỗi phần tử của S chứa đúng trong r tập con , thì
=
Chứng minh:
a. Gọi P là tập tát cả các cặp ∈S.{1,…,k} thỏa s ∈ .
Để đếm được P, ta có:
Mặt khác
Từ đó suy ra điều phải chứng minh.
b. Chứng minh tương tự.
Ví dụ minh họa:
Xếp ngẫu nhiên các số 1, 2, , 12 trên vòng tròn. Chứng minh rằng luôn
tìm được 3 số kề nhau có tổng lớn hơn hoặc bằng 20.
Lời giải:
Đánh số các vị trí từ 0 đến 11 và kí hiệu là số ở vị trí i. Đặt quả bóng
vào vị trí i và kí hiệu là tập hợp các quả bóng ở vị trí , ở đây
được lấy theo modun 12, kí hiệu S là tập hợp tất cả các quả bóng,
.
Khi đó mỗi quả bóng chứa đúng trong ba tập . Theo nguyên lý Dirichlet
mở rông, ta có: .
Ta có:
Tồn tại tập có ít nhất 20 quả bóng.
2.2 Nguyên lý Dirichlet đối ngẫu.
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng

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

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.
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 thỏ (học sinh) vào một chuồng mang số đúng bằng số lỗi mà học sinh đó

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ọ

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.
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á
Lồng 2 ứng với cây có 2 lá
……
Mà số thỏ > số lồng. Theo nguyên lý Dirichlet có ít nhất một lồng nhốt không
dưới 2 con thỏ hay có ít nhất 2 cây thông có cùng số lá.

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.

Ta chỉ cần chứng minh đồng thời P và P .
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ố 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à: 3
Tương tự ta xét 4 số lại có hai số có hiệu chia hết cho 3, như vậy
trong P có ít nhất hai hiệu khác nhau cùng 3.
Do đó P .(1)
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Mặc khác, theo nguyên lí Dirichlet trong 5 số đã cho có ít nhất ba số có cùng
tính chẵn, lẻ. Có hai trường hợp xảy ra:
a. Nếu ít nhất có 4 số có cùng tính chẵn lẻ, thì từ 4 số này có thể lập nên 6
hiệu khác nhau cùng chia hết cho 2, do đó tích của chúng chia hết cho hay
P .
b. Nếu có đúng 3 số có cùng tính chẵn lẻ. Không giảm tính tổng quát, có thể
cho đó là . Khi đó hai số còn lại cũng có tính chẵn lẻ giống nhau
nhưng khác với tính chẵn lẻ của . Vậy bốn hiệu
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ố có ít nhất một hiệu chia hết cho 4. Do đó:
.Tức là P .
Tóm lại trong mọi trường hợp ta luôn có P .(2)
Từ (1) và (2) ta suy ra P 288
Bài toán 2.4 Chứng minh rằng trong 12 số nguyên tố phân biệt luôn luôn
chọn ra được 6 số, gọi là sao cho 1800
Lời giải:
Vì ba số nguyên tố đầu tiên là 2, 3, 5, do đó trong 12 số nguyên tố phân biệt
đã cho luôn có ít nhất 9 số lớn hơn 5. Vì là số nguyên tố lớn hơn 5 nên:
a. Chín số trên khi chia cho 3 có dư 1 hoặc 2. Theo nguyên lí Dirichlet phải
tồn tại ít nhất 5 số đồng dư với nhau theo mod 3. Năm số này lại không chia hết
cho 5. Vì thế trong năm số ấy lại có ít nhất hai số mà ta có thể giả sử là sao

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ó

không ít hơn 15 phần tử, nên ta nhận được không ít hơn hiệu, (tức là
không ít hơn 105 hiệu).
Do các số của tập con đều thuộc tập hợp {1, 2, . . . , 100} nên các hiệu nói
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:
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
Giả sử với một tập hợp nào đó chứa các số mà không thoả mãn bài
toán.Khi đó không có số nào trong các số : chia
hết cho n. Vì số các số dư khác không trong phép chia cho n là n−1, nên theo
nguyên lí Dirichlet ta tìm được hai số Si và Sj(1 ≤ i ≤ j ≤ n) có cùng số dư.
Suy ra hiệu chia hết cho n. Điều này mâu thuẫn với giả sử
nói trên. Vậy bài toán được chứng minh.
Bài toán 2.8 Cho là những số nguyên khác nhau trong [100, 200],

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

số có cùng số dư. Giả sử các số đó là:
Khi đó: 1 ≤ n < m ≤ p. Vậy:
tích này chia hết cho p vì (p, 10) = 1, suy ra 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
B
3
B
2
B
1
A
Hình 3.1
Xét A là một trong số sáu điểm đã cho. Khi đó xét năm đoạn thẳng (mỗi đoạn
thẳng nối điểm A với năm điểm còn lại). Vì mỗi đoạn thẳng được bôi chỉ màu
đỏ hoặc xanh, nên theo nguyên lí Dirichlet có it nhất ba trong năm đoạn nói trên
cùng màu. Giả sử là các đoạn và có thể cho rằng chúng cùng màu
xanh.
Có hai khả năng xảy ra:

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

3
A
2
A
1
S
Hình 3.2
b. Nếu là cạnh đáy. Khi đó dĩ nhiên chắc chắn là đường chéo
đáy.
i. Nếu là đường chéo đáy thì ta quay về trường hợp a. vừa xét, với
Lý thuyết tổ hợp Nguyên lý Dirichlet và ứng dụng
là tam giác với ba cạnh là ba đường chéo đáy.
ii. Nếu là cạnh đáy. Khi đó rõ ràng là các đường chéo đáy.
Nếu là đường chéo đáy, ta quay về trường hợp a., nếu là cạnh bên.
Ta xét hai khả năng sau:
ii1. Nếu là đường chéo đáy, thì tam giác là tam giác với ba cạnh
là ba đường chéo đáy, ta quay về trường hợp a.
A
5
A
4
A
3
A
2
A
1
A
5
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
.

Do nên đường tròn đồng tâm với đường tròn ngoại tiếp trên
và có bán kính chứa ít nhất năm điểm nói trên.

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

B
A
Hình 3.5
Lấy A là một trong số 25 điểm đã cho. Xét hình tròn 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 thì kết luận của bài toán hiển
nhiênđúng.
b. Tồn tại điểm (B thuộc trong số 25 điểm đã cho), sao cho
. Vì , nên AB > 1. Xét hình tròn tâm B, bán kính bằng 1. Lấy C
là điểm bất kì trong số 25 điểm đã cho sao cho C A,C B. Theo giả thiết (và
dựa vào AB > 1), nên min {CA,CB} < 1. Vì thế C∈ hoặc C∈
Khẳng định này chứng tỏ rằng các hình tròn và chứa tất cả 25
điểm đã cho. Vì thế theo nguyên lí Dirichlet, có ít nhất một trong hai hình
tròn nói trên chứa không ít hơn 13 điểm trong 25 điểm đã cho.
Chú ý: Bài toán có dạng tổng quát như sau (cách giải hoàn toàn tương tự):
Cho 2n + 1 điểm trên mặt phẳng(với n ≥ 3). Biết rằng ba điểm bất kì
trong số 2n + 1 điểm đó luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Khi đó,
tồn 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.
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

2
M
1
S
2
S
1
Hình 3.7
Xét đường kính tùy ý của đường tròn, ở đây là hai đầu của đường
kính. Vì nên ta có:
≥
≥
…
≥
Cộng từng vế của 1000 bất đẳng thức trên ta có:
(*)
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ử:
Khi đó chọn S chính là . 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
tổng độ dài các đoạn thẳng được tô không lớn hơn 0,5.
Lời giải:
Chia đoạn thẳng trên thành 10 đoạn bằng nhau có độ dài 0,1; đặt chúng theo
một cột và chiếu xuống một đoạn thẳng như vậy. Vì khoảng cách giữa hai điểm
được tô bất kì không bằng 0,1; nên các điểm được tô của các đoạn thẳng cạnh
nhau không thể cùng chiếu xuống 1 điểm. Do đó không có điểm nào có thể là
hình chiếu của các điểm được tô nhiều hơn 5 đoạn thẳng. Suy ra tổng độ dài các
hình chiếu của các đoạn thẳng được tô không lớn hơn 5 × 0,1 = 0,5.

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.