TRẦN BÍCH NGỌC
NGUYÊN LÍ DIRICHLET VÀ ỨNG DỤNG VÀO BÀI TOÁN
HÌNH HỌC Tổ H0P
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Hình học
TRẦN BÍCH NGỌC
NGUYÊN LÍ DIRICHLET VÀ ỨNG DỤNG VÀO BÀI TOÁN
HÌNH HỌC Tổ H0P
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học
Người hướng dẫn khoa học Th.s PHẠM THANH
TÂM
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
KHOA TOÁN
HÀ NỘI, 5/2014
LỜI CẢM ƠN
Trước khi trình bày nội dung của đề tài, tôi xin gửi lời cảm ơn và sự tri ân sâu sắc
đến thầy giáo Th.s. Phạm Thanh Tâm - người đã chỉ bảo và hướng dẫn tận tình cho tôi,
giúp tôi hoàn thành đề tài khóa luận tốt nghiệp.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo của trường Đại học
Sư phạm Hà Nội 2, đặc biệt là các quý thầy cô giáo của khoa Toán đã tận tình chỉ bảo
tôi trong suốt quá trình học tập tại khoa.
Lời cảm ơn chân thành và sâu sắc, tôi xin gửi tới gia đình, bạn bè
- những người đã luôn động viên và giúp đỡ tôi trong suốt quá trình học tập tại trường.
Tôi xin chân thành cảm ơn!
Hà Nội, tháng 5 năm 2014 Sinh viên thực hiện
Trần Bích Ngọc
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
KHOA TOÁN
HÀ NỘI, 5/2014
LỜI CAM ĐOAN
Sau một thời gian nghiên cứu với sự cố gắng, nỗ lực của bản thân

học tổ hợp.
Vì vậy để thấy được cái hay, cái hiệu quả cũng như làm
thành một cách thức mới để vận dụng vào quá trình giảng
dạy sau này và giúp
các em học sinh có được phương pháp giải bài tập hình học tổ hợp
hiệu quả, tôi lựa chọn nghiên cứu đề tài "Nguyên l í Dirichlet và
ứng dụng vào bài t o á n hình học tổ hợp" dưới sự hướng dẫn của
thầy giáo Th.s. Phạm Thanh Tâm.
2. Mục đích nghiên cứu
Nghiên cứu các cơ sở lý luận và dựa vào thực tiễn trong quá trình
giảng dạy bộ môn hình học để tổng hợp và đưa ra các ứng dụng của
nguyên lí Dirichlet vào việc giải các bài toán hình học tổ hợp.
3. Đối tượng nghiên cứu
Nguyên lí Dirichlet và những bài toán hình học tổ hợp có ứng dụng
nguyên lí Dirichlet để giải.
4. Nhiệm vụ nghiên cứu
Nêu nội dung cơ bản của nguyên lí Dirichlet.
Nêu ứng dụng của nguyên lí Dirichlet vào việc giải các bài toán hình
học tổ hợp.
Hệ thống lại một số dạng bài tập có sử dụng nguyên lí Dirichlet
4 -2 • 7 •
đê giai.
5. Phạm vi nghiên cứu
Một số bài toán hình học tổ hợp giải được bằng nguyên lí Dirichlet.
6. Phương pháp nghiên cứu
Đọc tài liệu và trao đổi nghiên cứu nhằm đưa ra cái nhìn tổng quát
về nội dung nguyên lí Dirichlet và nhận diện được các bài tập hình học
CÓ thể giải quyết một cách đơn giản bằng nguyên lí Dirichlet.
Khóa luận tốt nghiệp đại học Chuyên ngành:
SVTH: Trần Bích Ngọc 5 K36CNT-ĐHSP Hà Nội 2

Nếu nhốt N + 1 con thỏ vào N cái chuồng thì bao giờ cũng có một
chuồng chứa ít nhất hai con thỏ. Ta có thể phát biểu nguyên lí
Dirichlet tổng quát như sau:
Mệnh đề 1.1.1. Nếu có N đồ vật được đặt vào trong K hộp thì sẽ
~N'"
đồ vật. (ở đây, |"af| là số nguyên
tồn tại một hộp chứa ít nhất nhỏ nhất có giá trị lớn hơn hoặc bằng X).
Chứng minh. Giả sử mọi hộp đều chứa ít hơn tổng số đồ vật là:
Điều này mâu thuẫn với giả thiết là có N đồ vật cần xếp.
k
'

đồ vật. Khi đó
'N
'
'N
'
k
-1) < k
=
1.2 Nguyên lí Dirichlet mở rộng
Mệnh đề 1.2.1. Nếu nhốt N con thỏ vào M > 2 cái chuồng thì tồn
"n + m — V
tại một chuồng có ít nhất chỉ phần nguyên của số A.
Chứng minh. Giả sử trái lại, mọi chuồng thỏ không có
đến
1.3 Nguyên lí Dirichlet dạng tập hợp
Mệnh đ ề 1.3.1. Cho A và B là hai tập hợp khác rỗng. Kí hiệu S(A),
S(B) lần lượt là số lượng phần tử của A và B, với S(B) < S(A) < +oo.
Khi đó, xét ánh xạ /, với:

n
+
m
Giả sử có một số tự nhiên K nào đó mà SỤ4) > K.S(B) và ta có
quy tắc cho tương ứng với mỗi phần tử của Ả với một phần tử của B.
Khi đó tồn tại ít nhất K + 1 phần tử của A mà chúng tương ứng với
cùng một phần tử của B.
Chứng minh. Với mọi tập con c gồm một phần tử của B ỊC c B)
thì S(C) = 1.
Ta có: S(C) = 1 < S(B) suy ra S(A) > K.S(C) = K. Hay S(A)
>K+L.
Suy ra tồn tại ít nhất K + 1 phần tử của A tương ứng với một phần
tử của B. Vì c là tập bất kì nên nguyên lí được chứng minh. CHÚ Ý:
Khi A; = 1, ta có ngay lại nguyên lí Dirichlet.
1.5 Nguyên lí Dirichlet vô hạn
Nếu chia một tập hợp vô hạn các quả táo vào hữu hạn ngăn kéo,
thì phải có ít nhất một ngăn kéo chứa vô hạn các quả táo.
Nguyên lí Dirichlet mở rộng cho trường hợp vô hạn này cũng
đóng vai trò hết sức quan trọng trong lí thuyết số nói riêng và toán
học rời rạc nói chung.
Chương 2 ứng dụng nguyên lí Dirichlet
vào một số bài toán hình học tổ hợp
Chương này dành để trình bày phương pháp sử dụng nguyên lí
Dirichlet để giải các bài toán hình học tổ hợp, nguyên lí Dirichlet áp
dụng cho độ dài các đoạn thẳng, diện tích các hình phẳng hay được
sử dụng đến trong nhiều bài toán hình học tổ hợp.
2.1 Bài toán tô màu hình
Bài toán 2.1. Trong mặt phẳng cho 6 điểm, 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

Nếu một đoạn nào đó được tô màu đỏ, ví dụ QR thì ta nhận được
tam giác PQR màu đỏ (H. 2.3).
Theo như lập luận trên thì ta có ít nhất một tam giác đồng màu. Ta
cho tam giác đó là tam giác PQR màu đỏ.
B
1
H. 2.3
Bây giờ ta thử xây dựng tam giác đồng màu mới theo phương pháp
trên. Ta bắt đầu từ điểm S, khác với P, Q, R. Kí hiệu 2 điểm còn lại là
T và U. Ta lại xét những đoạn thẳng SP, SQ, SR, ST và SU. Nếu ít
nhất ba trong chúng là màu đỏ thì theo lí luận như với tam giác PQR,
ta sẽ có tam giác đỏ với đỉnh S, hoặc tam giác xanh và trong cả hai
trường hợp, tam giác này đều khác tam giác PQR. Theo phương pháp
như vậy, ta có thể nhận được ít nhất ba trong những đoạn này màu
xanh. Nếu ngược lại, một trong những đoạn ST, SU là xanh thì ta sẽ
có tam giác xanh với đỉnh S hoặc tam giác đỏ với đỉnh T và cả hai
trường hợp tam giác này đều khác tam giác PQR.
p
H.
2.2 p
1
Suy ra, ta có thể cho rằng SP, SQ , SR là xanh, còn ST và sumàu
đỏ. Nếu ta lí luận tương tự cho đỉnh T thì cũng chỉ ra rằng tồn tại hai
tam giác đồng màu khác tam giác PQR bằng việc loại trừ khi TP, TQ,
TR xanh, còn TS và TU là đỏ. Trong trường hợp đó, tam giác STU là
đỏ.
Từ đó bài toán đã được chứng minh.
Bài toán 2.3. Từ bài toán 2.1 ta đưa ra một ví dụ minh họa đẹp mắt
cho bài toán như sau: chứng minh rằng từ sáu số vô tỉ tùy ý có thể
chọn ra được ba số (ta gọi ba số đó là A, 6, c) sao cho A + B, B + C,

SB, SC, SD, SE được bôi cùng màu đỏ, và các điểm A, B, C, D, E
xếp theo ngược chiều kim đồng hồ. Xét đa giác ABCDE.
Có hai khả năng xảy ra:
1) Nếu AB là đường chéo của đáy. Khi đó dĩ nhiên BD, DA cũng là các
đường chéo của đáy.
Khi đó, lại có các trường hợp sau:
a) Nếu cả ba đoạn AB, BD, DA cùng bôi màu xanh. Khi đó A, B, D là ba
đỉnh cần tìm, vì ABD là tam giác với ba cạnh xanh.
b) Nếu một trong các đoạn AB, BD, DA là đỏ. Giả sử BD đỏ, thì tam
giác SBD là tam giác với ba cạnh đỏ. Lúc này S, B, D là ba đỉnh cần
tìm.
2) Nếu AB là cạnh đáy. Khi đó dĩ nhiên AC, CE chắc chắn là đường chéo
đáy.
a) Nếu AE là đường chéo đáy thì ta quay lại trường hợp 1 vừa xét, với
ACE là tam giác với ba cạnh là 3 đường chéo đáy.
b) Nếu AE là cạnh đáy. Khi đó rõ ràng AC
:
AD là các đường chéo đáy.
- Nếu CD là đường chéo đáy, ta quay về trường hợp 1.
- Nếu CD là cạnh đáy. Lại xét các trường hợp sau:
+ Nếu BC là đường chéo đáy, thì tam giác BCE là tam giác với ba
đường chéo đáy, quay về trường hợp 1.
1
+ Nếu BC là cạnh đáy thì khi đó xét tam giác BDE và quay về trường
hợp 1.
Như vậy, bài toán đã giải quyết hoàn toàn.
Bài toán 2.5. Cho hình đa giác đều 9 cạnh. Mỗi đỉnh của nó được tô
màu bằng một trong hai màu đỏ hoặc xanh. Chứng minh rằng tồn tại
hai tam giác phân biệt có diện tích bằng nhau, mà các đỉnh của mỗi
tam giác được tô cùng một màu.

đỉnh và trọng tâm cùng màu.
Chứng minh. Lấy năm điểm tùy ý sao cho không có ba điểm nào
thẳng hàng trên mặt phẳng. Khi đó vì chỉ dùng có hai màu để tô các
đỉnh, mà theo nguyên lí Dirichlet phải tồn tại ba điểm trong số đó
cùng màu. Giả sử đó là ba điểm A, B, c có màu đỏ. Như vậy ta có tam
giác ABC với ba đỉnh màu đỏ. Gọi G là trọng tâm tam giác ABC. Chỉ
có hai khả năng xảy ra:
1) Nếu G có màu đỏ. Khi đó A, B, C, G cùng đỏ và bài toán đã được
chứng minh.
2) Nếu G có màu xanh. Kéo dài GA, GB, GC sao cho:
'
AA' = 3 GA
i
BB' = 3GB ■
Cơ = 3 GC
1
H. 2.7
Khi đó, nếu gọi M, N, P tương ứng là các trung điểm của BC, CA,
AB thì A là trọng tâm của tam giác ABC.
Tương tự ta cũng có:
B là trọng tâm của tam giác B'AC. C
là trọng tâm của tam giác C'AB.
Vậy các tam giác A'BC, B'AC, C'AB tương ứng nhận A, B, c là
trọng tâm. Mặt khác, ta cũng có các tam giác ABC và A'B'C' có cùng
trọng tâm G. Có hai trường hợp sau có thể xảy ra:
a) Nếu A
1
, B', C' cùng xanh. Khi đó tam giác A'B'C' và trọng tâm G có
cùng màu xanh.
b) Nếu ít nhất một trong các điểm A', B', C' có màu đỏ. Không mất tính

Vậy luôn tồn tại hình chữ nhật thỏa mãn điều kiện đề bài.
Bài toán 2.8. Trên mặt phẳng cho 18 điểm, sao cho không có ba điểm
nào thẳng hàng. Nối từng cặp điểm với nhau và tô màu cho mọi đoạn
thẳng thu được một trong hai màu xanh và đỏ. Chứng minh rằng luôn
tìm được một tứ giác mà các đỉnh của nó nằm trong tập điểm đã cho
sao cho cạnh và đường chéo của nó cùng màu.
Chứng minh. Giả sử AI (Ỉ = 1,18) là 18 điểm đã cho. Xuất phát từ AI
có 17 đoạn thẳng AỊAỊ (I = 2,18). Mười bảy đoạn thẳng đó chỉ có hai
màu xanh hoặc đỏ, nên theo nguyên lí Dirichlet tồn tại ít nhất chín
đoạn thẳng cùng màu. Không giảm tổng quát, giả sử đó là các đoạn
thẳng A
1
A
2
, AIA
3
, AIAI
Ữ Ì
và chúng có cùng màu đỏ.
1
Xét chín điểm A
2
,AỊ, . . . AI
Ữ
chỉ có thể xảy ra các khả năng hai
trường hợp sau:
1) Hoặc là tồn tại điểm AJ (2 ^ ^ 10) sao cho trong tám đoạn
thẳng AJA
K
(2 ^ K ^ 10, K 7^ J) có ít nhất bốn đoạn thẳng màu đỏ.

đoạn A
2
AỴ (3 ^ K ^10, K Ỷ 3)
c
° tối đa hai đoạn màu đỏ thôi
(thật vậy, nếu với mọi AJ (2 ^ J ^ 10) mà có đúng 3
đoạn AJAỴ
(2 ^ K ^ 10, Ả; 7^ J) màu đỏ, thì số đoạn thẳng màu đỏ nối trong
J ỉ 9 x 3
Ả
2
H.
2.9
2
nội bộ 9 điếm đó là là số nguyên, điều này vô lí). Vì A
2
AK (3
^ K ^ 10, K Ỷ J) có tối đa hai đoạn màu đỏ mà thôi, nên trong số các
đoạn A
2
A
3:
A2A4, A
2
A
5
, A
2
^4io có ít nhất sáu đoạn màu xanh.
Không giảm tổng quát, ta cho ^42^4-5, • • • A

cầu bài toán.
b) Nếu tồn tại tam giác AỊAJAỴ (5^I<J<K^ 10) màu đỏ thì AIAỊAJA
K
là
tứ giác cần tìm.
Như vậy ta luôn chứng minh được tồn tại một tứ giác mà các đỉnh
của nó nằm trong tập điểm đã cho sao cho cạnh và đường chéo cùng
màu.
Bài toán 2.9. Giả sử mỗi điểm trong mặt phẳng được tô bằng một
trong 2 màu xanh hoặc đỏ. Chứng minh tồn tại một hình chữ nhật có
các đỉnh cùng màu.
Chứng minh. Vẽ ba đường thẳng song song DỊ, D
2
, D
3
(DỊ//D
2
//D
3
).
Lấy trên DỊ bất kì bảy điểm. Do mỗi điểm chỉ được bôi bằng một
trong hai màu xanh hoặc đỏ nên theo nguyên lí Dirichlet trên D\ luôn
tồn tại bốn điểm cùng màu. Không giảm tổng quát, giả sử bốn điểm
PỊ, P2, P3, -P4 cùng màu đỏ.
Gọi Q11Q21 QZ, Q4 là hình chiếu vuông góc của PI, P25 PZI -P4
xuống D
2
. Gọi R
U
R

hình chữ nhật có bốn đỉnh cùng màu.
Vậy trong mọi trường hợp đều tồn tại một hình chữ nhật có các
đỉnh cùng màu.
Bài toán 2.10. Cho đa giác đều 2013 cạnh. Người ta sơn các đỉnh của
đa giác bằng hai màu xanh và đỏ. Chứng minh rằng phải tồn tại 3 đỉnh
được sơn cùng một màu tạo thành một tam giác cân.
Chứng minh. Ta có đa giác 2013 cạnh nên có 2013 đỉnh. Do đó theo
nguyên lí Dirichlet phải tồn tại hai đỉnh kề nhau là P và Q được sơn
bởi cùng một màu (chẳng hạn màu xanh).
Vì đa giác đã cho là đa giác đều có một số lẻ đỉnh, cho nên phải
tồn tại một đỉnh nào đó nằm trên đường trung trực của đoạn thẳng
PQ. Giả sử đỉnh đó là A.
Nếu A được tô màu xanh thì ta có tam giác APQ là tam giác có ba
đỉnh A, P, Q được tô màu xanh.
Nếu Ả tô màu đỏ. Lúc đó gọi B và C là các đỉnh khác của đa giác
kề với P và Q.
P\ P2 p3 Pị1

c
Q 3 QA
PL
H. 2.10
P2
P* P4 -
RI R2

]> c

Nếu I được tô màu đen thì tam giác BHI có ba đỉnh được tô bằng màu
đen, thỏa mãn.
Ta lại giả sử I được tô bằng màu đỏ thì xét tam giác IDF. Dễ thấy
tam giác IDF đều, theo trên ta có I, D, F được tô bởi cùng màu đỏ,
thỏa mãn.
Như vậy, ta chứng tỏ được rằng tồn tại một tam giác đều mà ba
đỉnh được tô bởi cùng một màu.
Bài toán 2.12. Cho hình lăng trụ có hai đáy là các ngũ giác đều đáy
trên AỊA
2
A
3
A4 A
5
và đáy dưới Mỗi cạnh của hai
2
ngũ giác này và các đoạn thẳng AỊBJ với Ỉ,J = 1, 5 được tô màu đỏ
hoặc màu xanh. Biết rằng mọi tam giác mà các đỉnh của nó là đỉnh
của lăng trụ và tất cả các cạnh của nó được tô màu, có hai cạnh màu
khác nhau. Chứng minh rằng tất cả 10 cạnh ở đáy trên và đáy dưới
đều có cùng một màu.
Chứng minh. Trước tiên, ta chứng minh rằng tất cả các cạnh A1 A2,
A2 A3, A^AỊ, A4A5, A§AỊ đều có cùng một màu. Chứng minh bằng
phản chứng. Giả sử ngược lại, có các cạnh AỊA
2
màu đỏ và A
2
A3 màu
xanh. Theo nguyên lí Dirichlet thì trong số 5 đoạn thẳng A
2

phải là màu xanh. Bây
giờ, đoạn AIB
R
và AIB
S
cũng phải màu xanh, nếu ngược lại ta phải có
AỊA
2
B
R
hoặc AIA
2
B
S
là những tam giác đỏ. Do đó, AỊB
R
B
S
là tam giác
xanh. Điều này vô lí nên suy ra A1A2 và ^2^4 3 có cùng màu.
Làm tương tự như vậy cho tất cả các cạnh của đáy có cùng màu.
Bây giờ ta giả sử tất cả các cạnh đáy trên màu đỏ và tất cả các
cạnh đáy dưới màu xanh. Theo nguyên lí Dirichlet thì có ít nhất ba
trong năm cạnh AỊBỊ, Ỉ = 1,5 phải có cùng màu. Không giảm tổng
quát giả sử đó là màu xanh, lí luận như trên thì hai trong số ba đỉnh
BỊ đó phải là hai đỉnh kề nhau, từ đó hai đỉnh này tạo với AI thành
tam giác có ba cạnh màu xanh (vô lí). Vì thế, ba trong năm cạnh
AỊBI, * = 1 , 5 phải cùng màu đỏ. Lập luận tương tự, ba trong năm
cạnh A
2

được xác định
theo công thức truy hồi sau:
í
I U i = 3
[U
n+
1 = ( r a + 1 ) m „ - 7 1 + l , n = 1,2
Giả sử N là số tự nhiên bất kì và tập M gồm U
N
đ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ácnhau
trong M được tô 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.
Chứng minh. Ta chứng minh bằng quy nạp theo N.
1) Với N = 1 ta có UỊ = 3 và kết luận của bài toán hiển nhiên đúng (vì ở
đây chỉ có một màu do N = 1).
Với N = 2 ta có U2 — 2UI — 1 + 1. Ta có bài toán với sáu điểm
và dùng hai màu. (Giải như bài toán 2.1). Vậy kết luận bài toán đúng
với N = 2.
2