BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN TUẤN KHẢI

BÀI TỐN ĐẾM, PHỦ VÀ TƠ MÀU
TRONG HÌNH HỌC TỔ HỢP

CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP
MÃ SỐ: 8460113

Quy Nhơn - Năm 2021


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN TUẤN KHẢI

BÀI TỐN ĐẾM, PHỦ VÀ TƠ MÀU
TRONG HÌNH HỌC TỔ HỢP

CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP
MÃ SỐ: 8460113

Người hướng dẫn khoa học
PGS.TS. LÊ CƠNG TRÌNH

Quy Nhơn - Năm 2021

i

Mục lục

Mở đầu

1

1 Bài tốn đếm trong hình học tổ hợp

3

1.1

Một số tính chất tổ hợp của đa giác lồi . . . . . . . . . . . . . . . .

3

1.2

Đếm số giao điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3

Đếm tam giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4


Đếm đa giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5

Hệ điểm và đường thẳng . . . . . . . . . . . . . . . . . . . . . . . . 18

1.6

Hệ đoạn thẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.7

Một số tính chất tổ hợp của đa giác không lồi . . . . . . . . . . . . 25

2 Hệ đường cong và miền

29

2.1

Chia mặt phẳng bởi các đường thẳng . . . . . . . . . . . . . . . . . 30

2.2

Chia mặt phẳng bởi các đường cong khép kín . . . . . . . . . . . . 34

2.3

Chia đa giác lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36


2.4

Chia không gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3 Phủ hình và bao hình

44

3.1

Phủ hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2

Phủ hình với hệ các hình trịn tương đẳng . . . . . . . . . . . . . . 49


ii

3.3

Bao hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4

Bài toán xếp chồng . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4 Bài tốn tơ màu

61


4.1

Tô màu điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.2

Tô màu miền . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3

Tô màu bàn cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.4

Tô màu phụ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Kết luận

76


1

Mở đầu
Việc nghiên cứu bài toán đếm một số đối tượng trong hình học, chẳng hạn
như đếm số giao điểm, đếm số tam giác, đếm số tứ giác, . . . thỏa mãn một số
tính chất nào đó; việc nghiên cứu các tính chất tổ hợp của mặt phẳng, đa giác,
hoặc không gian khi bị chi ra thành nhiều miền bởi các hệ đường thẳng hoặc
đường cong; việc nghiên cứu những bài tốn phủ hình, bao hình, bài tốn tơ

màu, . . . là những vấn đề được quan tâm nghiên cứu trong hình học tổ hợp.
Luận văn tập trung nghiên cứu các bài tốn cơ bản nói trên trong hình học tổ
hợp. Các kết quả trong luận này được chúng tơi tổng hợp và trình bày lại từ tài
liệu [1] và [2], các bài toán tham khảo trong các tài liệu [3], [4], [5], [6], [7].
Ngoài mở đầu, kết luận và tài liệu tham khảo, luận văn được bố cục thành
4 chương:
Chương 1: Bài tốn đếm trong hình học tổ hợp
Trong chương này tác giả trình bày một số tính chất tổ hợp của các đa giác lồi
và các đa giác khơng lồi, cùng với một số bài tốn đếm một số đối tượng hình
học.
Chương 2: Hệ đường cong và miền.
Trong chương này tác giả trình bày một số bài toán tổ hợp liên quan đến việc
chia một đối tượng hình học cho trước thành nhiều phần có "hình dạng" khác
nhau bởi một họ đường thẳng hoặc đường cong.


2

Chương 3: Phủ hình và bao hình.
Trong chương này tác giả trình bày các bài tốn phủ hình (covering) và bao
hình (parking), đồng thời nghiên cứu các tình huống một đối tượng hình học
cho trước chứa một số đối tượng khác bên trong nó.
Chương 4: Bài tốn tơ màu.
Trong chương này tác giả trình bày một số bài tốn tơ màu các đối tượng hình
học, gồm tơ màu điểm, tơ màu miền, tô màu bàn cờ, . . .
Luận văn được hồn thành dưới sự hướng dẫn tận tình của thầy PGS.TS. Lê
Cơng Trình, người ln nhắc nhở, động viên, giúp đỡ tơi trong q trình nghiên
cứu để tơi có thể hồn thành luận văn này. Tơi cũng xin bày tỏ lịng biết ơn đối
với q thầy cơ trong khoa Tốn và Thống kê, phịng Sau đại học trường Đại
học Quy Nhơn, đặc biệt là quý thầy cô đã trực tiếp giảng dạy cho lớp Cao học

Tốn khóa 22. Cuối cùng tơi tỏ lịng biết ơn đến gia đình, người thân và bạn bè
đã luôn ủng hộ, giúp đỡ, tạo điều kiện cho tôi về mọi mặt trong suốt thời gian
tơi học thạc sĩ cũng như hồn thành luận văn này.
Trong thời gian ngắn hoàn thành luận văn này, chắc khơng tránh được sai
sót. Chúng tơi rất mong nhận được những góp ý, phê bình q báu của q
thầy cơ và các bạn đồng nghiệp.
Quy Nhơn, tháng 7 năm 2021
Học viên: Nguyễn Tuấn Khải


3

Chương 1
Bài tốn đếm trong hình học tổ hợp
Trong chương này chúng tơi trình bày một số tính chất tổ hợp của các đa
giác lồi và các đa giác không lồi, cùng với một số bài toán đếm một số đối tượng
hình học thỏa mãn một số tính chất nào đó: Đếm số giao điểm, đếm số tam
giác, . . .

1.1

Một số tính chất tổ hợp của đa giác lồi

Trong phần này chúng tơi trình bày một số tính chất tổ hợp của các đa giác
lồi. Đầu tiên chúng tôi định nghĩa tập lồi.
Định nghĩa 1.1.1. Tập lồi trong mặt phẳng (trên đường thẳng, trong không
gian) là tập hợp U các điểm trong mặt phẳng (trên đường thẳng, trong không
gian) có tính chất sau: Với hai điểm phân biệt bất kì X , Y thuộc U thì mọi điểm
của đoạn thẳng XY cũng thuộc U .
Tập lồi trên đường thẳng có cấu trúc đơn giản: Ngoại trừ đường thẳng, tập

rỗng, các điểm thì các tập lồi là các tia và đoạn thẳng, có hoặc khơng có điểm
biên. Việc phân loại các tập lồi trong mặt phẳng rõ ràng là khó khăn, nhưng
một công cụ đáng kể trong việc xây dựng các tập lồi là giao của các tập lồi là


4

một tập lồi. Một khái niệm quan trọng đó chính là bao lồi K của U : nó là giao
của tất cả các tập lồi M thỏa mãn U ⊆ M (vì vậy K là tập lồi nhỏ nhất chứa
U ).

Định nghĩa 1.1.2. Cho K = {A1 , A2 , . . . , An } là tập gồm n điểm phân biệt
trong mặt phẳng (n ≥ 3). Tập M được gọi là n-giác lồi A1 A2 . . . An nếu M là
giao của n nửa mặt phẳng α1 , α2 , . . . ., αn sao cho với mỗi i = 1, 2, . . . , n đường
thẳng Ai Ai+1 (trong đó An+1 = A1 ) là biên của nửa mặt phẳng αi và mỗi điểm
Aj ∈ K\{Ai ; Ai+1 } đều nằm trong αi .

Nếu U là một tập hợp hữu hạn gồm n điểm (n ≥3) trong mặt phẳng sao cho
n điểm không cùng nằm trên một đường thẳng thì bao lồi của U là một đa giác

lồi có các đỉnh là một số (hoặc có thể là tất cả) phần tử của tập U .
Một kết quả quan trọng khác trong lý thuyết tập lồi đó là Định lý Helly.
Định lý 1.1.3 (Helly). Giả sử S là một hệ bất kì (hữu hạn hoặc vô hạn) các
tập con lồi của một mặt phẳng cho trước sao cho ba tập hợp bất kì có ít nhất
một điểm chung. Khi đó tất cả các tập con trong S đều có điểm chung.
Hai tính chất cơ bản sau đây của đa giác lồi sẽ được sử dụng thường xuyên
ở chương này.
Tính chất 1.1.4. Số đường chéo un của n-giác lồi M thỏa mãn
un =


n(n − 3)
.
2

Chứng minh. Thật vậy, n đỉnh của đa giác M được nối với nhau bởi

n
2




=

n(n−1)
2

đoạn thẳng, trong đó có đúng n đoạn là các cạnh của đa giác M . Do đó ta có
un =

n(n−1)
2

−n=

n(n−3)
.
2


5


Một cách tính khác: Mỗi đỉnh của đa giác M là điểm cuối của n − 3 đường
chéo. Nếu chúng ta cộng tất cả n đỉnh của M thì các đường chéo này đã được
đếm hai lần, chúng ta cũng có được un =

n(n−3)
.
2

Tính chất 1.1.5. Tổng Sn các góc trong một n-giác lồi thỏa mãn
Sn = (n − 2) · 180◦ .

(1.1.1)

Chứng minh. Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán
học. Với n = 3, (1.1.1) là công thức đã biết về tổng các góc trong của một tam
giác. Bây giờ chúng ta giả sử rằng công thức (1.1.1) đúng với i = n (n > 3), ta sẽ
chứng minh (1.1.1) đúng với i = n + 1. Ta chia nhỏ (n + 1)-giác lồi A1 A2 . . . An+1
theo đường chéo A1 A3 thành tam giác A1 A2 A3 và n-giác lồi A1 A3 . . . An+1 . Khi
đó n-giác lồi A1 A3 . . . An+1 có tổng các góc trong là Sn = (n − 2) · 180◦ . Vì
tổng Sn+1 các góc trong của đa giác A1 A2 . . . An+1 bằng tổng các góc trong
của tam giác A1 A2 A3 cộng với tổng các góc trong của n-giác A1 A3 . . . An+1 , suy
ra Sn+1 = 180◦ + (n − 2) · 180◦ = (n − 1) · 180◦ .
Một cách tính khác: Đa giác M = A1 A2 . . . An có thể chia bởi n − 3 cạnh
A1 Ak (k = 3, 4, . . . , n − 1) thành n − 2 tam giác, và tổng các góc trong của n − 2

tam giác này bằng Sn .
Mệnh đề 1.1.6. Tồn tại một n-giác lồi M (n ≥ 3) sao cho ba đường chéo bất
kì của M khơng đồng quy.
Chứng minh. Ta sẽ chứng minh bằng phương pháp quy nạp toán học theo n

rằng tồn tại n-giác lồi M nội tiếp một đường trịn và khơng có ba đường chéo
nào đồng quy.
Với n ≤ 5, n-giác lồi đang xét là n-giác lồi thơng thường, do đó khẳng định của
mệnh đề đã đưa ra là đúng. Với n > 6 ta giả sử rằng n-giác lồi Mn = A1 A2 . . . An


6

nội tiếp đường trịn C và khơng có ba đường chéo nào đồng quy. Ta xét tập
hợp P gồm tất cả các đường thẳng nối các giao điểm của tất cả các đường chéo
của đa giác Mn . Khi đó có hữu hạn đường thẳng thuộc P và cũng có hữu hạn
giao điểm của các đường thẳng này với đường trịn C . Do đó tồn tại một điểm
An+1 nằm trên đường trịn C và khơng nằm trên bất kì đường thẳng nào thuộc
P . Hơn nữa An+1 có thể được chọn nằm trên cung tròn giới hạn bởi A1 , An và

không chứa A2 , A3 , . . . An−1 . Khi đó A1 A2 . . . An An+1 là một (n + 1)-giác lồi khơng
có ba đường chéo nào đồng quy.
Mệnh đề 1.1.7. Cho n (n ≥ 4) điểm nằm trên mặt phẳng sao cho không có ba
điểm nào thẳng hàng và bốn điểm bất kì là đỉnh của một tứ giác lồi. Khi đó n
điểm đã cho là đỉnh của một n-giác lồi.
Chứng minh. Gọi S là tập hợp các điểm đã cho và giả sử bao lồi của S là k -giác
M . Ta sẽ chứng minh mọi điểm X ∈ S là đỉnh của M . Phản chứng rằng tồn tại

một điểm Y ∈ S nằm bên trong k -giác M . Từ một đỉnh Z tùy ý của M ta vẽ tất
cả các đường chéo nối với đỉnh Z , khi đó k -giác M được chia thành k − 2 tam
giác và điểm Y sẽ nằm trong một tam giác nào đó. Giả sử tam giác đó là ABC ,
khi đó bốn điểm A, B, C, Y không tạo thành tứ giác lồi, điều này mâu thuẫn với
giả thiết.
Mệnh đề 1.1.8. Chọn một điểm P tùy ý nằm trong đa giác lồi M và dựng các
hình chiếu vng góc từ P lên các đường thẳng chứa cạnh của M . Khi đó có ít

nhất một trong các hình chiếu này nằm trên cạnh của M .
Chứng minh. Trong tất cả các đường thẳng chứa cạnh của M , ta chọn đường
thẳng có khoảng cách đến P là nhỏ nhất, giả sử đường thẳng ấy là ` (Nếu có
nhiều đường thẳng như vậy thì ta chọn một đường bất kì). Giả sử cạnh AB nằm


7

trên `, ta sẽ chứng minh hình chiếu vng góc Q của P lên ` nằm trên đoạn
thẳng AB . Giả sử Q ∈ ` \ AB (Hình 1.1), khi đó đoạn thẳng P Q nối một điểm
trong với một điểm ngoài đa giác M , và giả sử P Q cắt CD tại R. Vì |P R| < |P Q|

Hình 1.1:

nên khoảng cách từ P đến CD nhỏ hơn khoảng cách từ P đến `, điều này mâu
thuẫn với cách chọn `. (Kí hiệu |P Q| là độ dài đoạn thẳng P Q).
Bài toán 1.1.9. Cho n-giác đều (n ∈ N, n ≥ 3). Tìm n biết rằng số đường chéo
của n-giác đều là 27.
Lời giải. Từ Tính chất 1.1.4 ta được

 n=9

n(n − 3)

= 27 ⇔ n2 − 3n − 54 = 0 ⇔ 
un =
2


(nhận)


n = −6 (loại)

Vậy n-giác đều cần tìm là 9-giác đều.

1.2

Đếm số giao điểm

Trong phần này chúng tơi trình bày một số bài toán về xác định số giao điểm
trong hệ đoạn thẳng, đường thẳng và đường tròn.


8

Mệnh đề 1.2.1. Một đường gấp khúc khép kín gồm 2n + 1 đoạn thẳng (n ≥ 1)
có thể tự cắt nhau tại nhiều nhất (2n + 1)(n − 1) điểm.
Chứng minh. Ta xét một đoạn AB tùy ý thuộc đường gấp khúc. Nó có thể có
nhiều nhất 2n − 2 giao điểm, vì AB sẽ khơng bị cắt bởi hai đoạn kề của nó. Điều
này đưa ra ước tính cho số k các giao điểm là: k ≤

(2n+1)(2n−2)
2

= (2n + 1)(n − 1).

Ta có thể dựng một đường gấp khúc khép kín với chính xác (2n + 1)(n − 1) giao
điểm: Xét đa giác A1 A2 . . . A2n+1 trong đó khơng có ba đường chéo đồng quy bên
trong đa giác. Khi đó đường gấp khúc A1 An+1 A2n+1 An A2n An−1 . . . A2 An+2 A1 là
đường gấp khúc có chính xác (2n + 1)(n − 1) giao điểm.

Mệnh đề 1.2.2. Cho n-giác lồi A1 A2 . . . An khơng có ba đường chéo nào đồng
quy. Khi đó số giao điểm của các đường chéo trong n-giác lồi là
 
n
4

=

n(n − 1)(n − 2)(n − 3)
.
24

Chứng minh. Ta xét đường chéo cố định A1 Ak (k = 3, 4, . . . , n − 1) và xác định số
giao điểm của đường chéo này với các đường chéo khác. Đường thẳng A1 Ak chia
mặt phẳng thành hai nửa mặt phẳng, một nửa mặt phẳng chứa (k − 2) đỉnh của
đa giác, nửa mặt phẳng cịn lại chứa (n − k) đỉnh. Do đó đường chéo A1 Ak cắt
các đường chéo khác tại (n − k)(k − 2) điểm, và a1 (n) là số giao điểm trên tất cả
các đường chéo xuất phát từ A1 thỏa mãn
a1 (n) =

n−1
X

n−1
X

k=3

k=3


(n − k)(k − 2) =

[(n + 2)k − k 2 − 2n] =

(n − 1)(n − 2)(n − 3)
.
6

Nếu chúng ta cộng số này cho tất cả các đỉnh của đa giác thì chúng ta đã đếm
mỗi giao điểm 4 lần. Do đó tổng số giao điểm A(n) của các đường chéo là
1
n(n − 1)(n − 2)(n − 3)
A(n) = · n · a1 (n) =
=
4
24

 

n
.
4


9

Một cách tính khác: Bất kì giao điểm nào của hai đường chéo cũng tương
ứng với bốn đỉnh của n-giác. Do đó số giao điểm của các đường chéo chính là số


cách chọn bốn trong số n đỉnh của n-giác, tức là có n4 giao điểm.

Bài tốn 1.2.3. Cho năm điểm nằm trong mặt phẳng và trong số tất cả các
đoạn thẳng nối hai điểm bất kì khơng có hai đoạn nào song song hoặc vng
góc với nhau. Từ mỗi điểm đã cho dựng đường vng góc với tất cả các đoạn
thẳng kể trên. Khi đó số giao điểm của hệ này không vượt quá 310.
Lời giải. Số đoạn thẳng tạo bởi năm điểm đã cho là

5
2




= 10 và mỗi điểm là

điểm đầu của bốn đoạn thẳng. Do đó từ mỗi điểm có sáu đường thẳng vng
góc với các đường thẳng nối các điểm khác. Trước tiên chúng ta xét hai điểm
bất kì trong năm điểm đã cho, giả sử là A, B và ta đếm số giao điểm của các
đường thẳng vng góc kẻ từ A với các đường vng góc kẻ từ các điểm khác.
Giả sử các điểm còn lại là C, D, E . Chúng ta chia sáu đường vng góc kẻ từ A
thành hai nhóm:
Ba đường thẳng p1 , p2 , p3 vng góc với các đường thẳng BC, BD, BE ; Các đường
thẳng này cắt sáu đường vng góc kẻ từ B tại 3 · 6 = 18 giao điểm.
Ba đường thẳng q1 , q2 , q3 kẻ từ A vng góc với CD, CE, DE giao với năm trong
số sáu đường thẳng vng góc kẻ từ B (vì có một đường vng góc kẻ từ B song
song với q1 , q2 hoặc q3 (xem Hình 1.2). Từ đó ta có thêm 3 · 5 = 15 giao điểm
khác.
Suy ra các đường vng góc từ A và B cắt nhau tại 18 + 15 = 33 giao điểm.


Người ta có thể chọn hai trong năm điểm đã cho theo 52 = 10 cách, vì vậy số
giao điểm p không được vượt quá 10 · 33 = 330. Chú ý rằng năm điểm đã cho tạo



thành đỉnh của 53 = 10 tam giác, trong đó ba đường cao đồng quy. Vì vậy ta
được p ≤ 330 − 2 · 10 = 310.


10

Hình 1.2:

Mệnh đề 1.2.4. Cho n ≥ 3 điểm nằm trong mặt phẳng và trong số tất cả các
đoạn thẳng nối hai điểm bất kì khơng có hai đoạn nào song song hoặc vng
góc với nhau. Từ mỗi điểm đã cho dựng đường vng góc với tất cả các đoạn
thẳng kể trên. Khi đó số giao điểm của hệ này không vượt quá
3n6 − 21n5 + 51n4 − 47n3 + 6n2 + 8n
.
24
n(n−1)
2

Chứng minh. Số đoạn thẳng tạo bởi n điểm đã cho là

n
2

điểm đầu của (n−1) đoạn thẳng. Do đó từ mỗi điểm có

n(n−1)
−(n−1)
2





=

và mỗi điểm là
=

(n−1)(n−2)
2

đường thẳng vng góc với các đường thẳng nối các điểm khác. Trước tiên chúng
ta xét hai điểm bất kì trong n điểm đã cho, giả sử là A, B và ta đếm số giao
điểm của các đường thẳng vng góc kẻ từ A với các đường vng góc kẻ từ các
điểm khác. Giả sử các điểm còn lại là X1 , X2 , . . . , Xn−2 . Chúng ta chia

(n−1)(n−2)
2

đường vng góc kẻ từ A thành hai nhóm:
Các đường thẳng p1 , p2 , . . . , pn−2 vuông góc với các đường thẳng
BX1 , BX2 , . . . , BXn−2 ; (n − 2) đường thẳng này cắt

kẻ từ B tại (n − 2) · (n−1)(n−2)
=
2
(n−1)(n−2)
−(n−2)
2

1=


n2 −3n
2

=

n2 −5n+6
2

n3 −5n2 +8n−4
2

(n−1)(n−2)
2

đường vng góc

giao điểm.

đường vng góc cịn lại kẻ từ A giao với

đường thẳng vng góc kẻ từ B . Từ đó ta có thêm

(n−1)(n−2)
−
2

n2 −5n+6
2

·


n2 −3n
2

=


11
n4 −8n3 +21n2 −18n
4

giao điểm khác.

Suy ra các đường vuông góc từ A và B cắt nhau tại
n3 −5n2 +8n−4
2

4

+n

−8n3 +21n2 −18n
4

=

hai trong n điểm đã cho theo
quá

n4 −6n3 +11n2 −2n−8 n(n−1)

· 2
4

tạo thành đỉnh của

n
3




=

n4 −6n3 +11n2 −2n−8
4

n(n−1)
2

=

giao điểm. Người ta có thể chọn

cách, vì vậy số giao điểm p không được vượt

n6 −7n5 +17n4 −13n3 −6n2 +8n
.
8

n3 −3n2 +2n
6


Chú ý rằng n điểm đã cho

tam giác, trong đó ba đường cao đồng quy.

Vì vậy ta được
n6 − 7n5 + 17n4 − 13n3 − 6n2 + 8n
n3 − 3n2 + 2n
−2·
8
6
6
5
4
3
2
3n − 21n + 51n − 47n + 6n + 8n
=
.
24

p ≤

1.3

Đếm tam giác

Một trong những bài toán cổ điển của hình học tổ hợp là xác định số tam
giác có đỉnh hoặc cạnh nằm trong tập hợp n phần tử cho trước.
Mệnh đề 1.3.1. Trên mỗi cạnh của một tứ giác lồi chọn n điểm phân biệt. Khi

đó có 2n2 (5n − 3) tam giác có đỉnh thuộc 4n điểm ấy.


Chứng minh. Từ 4n điểm đã cho ta có thể chọn được 4n
3 bộ ba điểm phân biệt,


tuy nhiên có 4 · n4 trường hợp bộ ba điểm nằm trên cùng một cạnh của tứ giác.




n
2
Do đó số tam giác chọn được là 4n
3 − 4 · 3 = 2n (5n − 3).
Một cách tính khác: Mỗi tam giác thuộc một trong hai loại sau: Mỗi đỉnh
của tam giác nằm trên ba cạnh khác nhau của tứ giác hoặc hai đỉnh của tam
giác nằm trên cùng một cạnh của tứ giác và đỉnh thứ ba nằm trên một cạnh


khác. Có 4n3 tam giác thuộc loại thứ nhất và 4 · 3 · n2 · n tam giác thuộc loại


thứ hai. Vì vậy ta có tất cả là 4n3 + 4 · 3 · 42 · n = 2n2 (n − 3) tam giác.


12

Mệnh đề 1.3.2. Cho n-giác lồi M (n ≥ 6). Khi đó có

n(n−4)(n−5)
6

tam giác có


đỉnh là đỉnh của M và cạnh là đường chéo của M .
Chứng minh. Từ số tam giác có đỉnh thuộc M ta trừ đi những tam giác có cạnh
là một hoặc hai cạnh của M . Có n(n − 4) tam giác có một cạnh là cạnh của
đa giác, vì với mỗi cạnh trong số n cạnh của M ta có thể chọn đỉnh thứ ba
theo n − 4 cách. Có n tam giác có hai cạnh là cạnh của M vì mỗi tam giác như
thế gồm hai cạnh kề của M và xác định duy nhất bởi đỉnh chung của hai cạnh
ấy. Vì vậy số tam giác có đỉnh là đỉnh của M và cạnh là đường chéo của M là


n(n−4)(n−5)
.
N = n3 − n(n − 4) − n =
6
Mệnh đề 1.3.3. Cho n-giác lồi M khơng có ba đường chéo nào đồng quy. Khi
đó có

n(n−1)(n−2) n3 +18n2 −43n+60
·
6
120

tam giác có cạnh nằm trên các cạnh hoặc đường

chéo của M .
Chứng minh. Ta chia tất cả P (n) tam giác thỏa yêu cầu bài toán thành các
lớp S0 , S1 , S2 , S3 sao cho Si chứa các tam giác có đúng i đỉnh trong số các đỉnh


của M, (i = 0, 1, 2, 3). Dễ dàng thấy rằng |S3 | = n3 . Mỗi tam giác trong lớp S2

Hình 1.3:


có hai đỉnh thuộc M , giả sử B1 , B2 , và đỉnh thứ ba của tam giác là giao điểm
của hai đường chéo B1 B3 và B2 B4 (Hình 1.3(a)). Nếu chúng ta chọn bốn đỉnh


13
B1 , B2 , B3 , B4 từ các đỉnh của M thì ta được chính xác bốn hình tam giác thuộc
n
4




S2 ; do đó |S2 | = 4 ·

1.3(b)) và |S0 | =

n
6




. Bằng cách lập luận tương tự ta được |S1 | = 5 ·

n
5




(Hình

(Hình 1.3(c)).


Vì vậy
P (n) =

3
X
i=0

 
|Si | =

n
3

 
+4·

n
4

 
+5·

n
5

 
+

n

6

n(n − 1)(n − 2) n3 + 18n2 − 43n + 60
·
.
=
6
120

Mệnh đề 1.3.4. Cho tập hợp S gồm n ≥ 3 điểm phân biệt trên mặt phẳng sao
cho khơng có ba điểm nào thẳng hàng. Khi đó có ít nhất

n(n−2)
3

tam giác có đỉnh

thuộc S và khơng chứa bất kì điểm nào khác thuộc S .
Chứng minh. Từ tập S ta chọn hai điểm bất kì, giả sử là X, Y . Ta xét nửa mặt
phẳng α có bờ là đường thẳng XY sao cho α chứa nhiều hơn một điểm của S .
Trong nửa mặt phẳng α gọi Z là điểm có khoảng cách ngắn nhất tới XY (nếu
có nhiều điểm thì ta chọn một điểm bất kì). Khi đó tam giác 4XY Z là "rỗng",
tức là nó khơng chứa bất kì điểm nào thuộc S . Để chứng minh điều này ta phản

Hình 1.4:

chứng rằng tồn tại A ∈ S chứa trong 4XY Z . Giả sử dA , dZ lần lượt là khoảng


14


cách từ A và Z đến XY . Khi đó diện tích 4AXY nhỏ hơn diện tích 4ZXY , tức
là dA < dZ (Hình 1.4(a)), điều này mâu thuẫn với cách chọn Z .
Chú ý rằng tồn tại nhiều nhất n cặp điểm X, Y thuộc S sao cho toàn bộ tập S
nằm hoàn toàn ở một trong hai nửa mặt phẳng có bờ là đường thẳng XY (điều
này xảy ra khi X, Y là hai đỉnh kề của bao lồi tập S ). Với mỗi cặp X, Y như vậy
ta chỉ ra có ít nhất một tam giác 4XY Z (Z ∈ S) là "rỗng". Với mỗi cặp X, Y



khác (ít nhất n2 − n cặp) có ít nhất hai tam giác "rỗng". Nếu chúng ta cộng
h

i
n
các số này với tất cả các cặp X, Y ta được ít nhất n + 2 2 − n = n(n − 2) tam
giác "rỗng", và mỗi tam giác được tính ít nhất ba lần. Vậy ta có ít nhất

n(n−2)
3

tam giác thỏa yêu cầu bài toán.
Mệnh đề 1.3.5. Trong mặt phẳng cho 3n điểm (n ≥ 1) sao cho không có ba
điểm nào thẳng hàng. Khi đó các điểm này là đỉnh của n tam giác rời nhau.
Chứng minh. Sử dụng phương pháp quy nạp toán học theo n. Với n = 1 khẳng
định của mệnh đề là đúng. Giả sử khẳng định của mệnh đề đúng với n = k , ta
chứng minh khẳng định của mệnh đề đúng với n = k + 1. Chúng ta xét 3k + 3
điểm trong mặt phẳng thỏa khơng có ba điểm nào thẳng hàng và giả sử bao lồi
của những điểm này là đa giác A1 A2 . . . As (3 ≤ s ≤ 3k + 3). Ta chia thành hai
trường hợp:
a) Tam giác 4A1 A2 A3 và 3k điểm cịn lại. Khi đó giả sử tất cả các điểm cịn lại
nằm trong nửa mặt phẳng có bờ là đường thẳng A1 A3 và không chứa điểm A2 .

Theo giả thiết quy nạp, 3k điểm này tạo thành k tam giác rời nhau. Cùng với
4A1 A2 A3 ta có (k + 1) tam giác rời nhau.

b) Tam giác 4A1 A2 A3 và 3k điểm còn lại. Chọn một điểm B từ 3k điểm sao cho
\
góc BA
1 A2 là nhỏ nhất, giả sử điểm B là duy nhất (Hình 1.4(b)). Khi đó nửa
mặt phẳng có bờ là đường thẳng A1 B và không chứa điểm A2 sẽ chứa 3k điểm,


15

mà theo giả thiết 3k điểm này tạo thành k tam giác rời nhau. Cùng với 4A1 A2 B
ta có (k + 1) tam giác rời nhau.
Một cách chứng minh khác: Vẽ tất cả các đường thẳng nối hai điểm bất
kì thuộc 3n điểm đã cho và chọn một hướng bất kì khác với tất cả các hướng
của các đường đã vẽ. Qua mỗi điểm của 3n điểm đã cho ta kẻ một đường thẳng
với hướng đã chọn; như vậy chúng ta thu được một hệ gồm 3n đường thẳng song
song phân biệt. Chúng ta chia nhỏ các đường song song này thành n bộ ba của
các đường gần nhau; các điểm đã cho trên các đường thuộc cùng một bộ ba tạo
thành đỉnh của một trong các tam giác rời nhau.

Hình 1.5:

Chú ý 1.3.6. Phương pháp song song này cũng có thể được dùng để giải bài
tốn sau: Giả sử rằng tổng các số nguyên dương k1 , k2 , . . . , kn bằng N . Chứng
minh rằng mọi tập hợp N phần tử của điểm trong mặt phẳng có thể được chia
ta thành n lớp với k1 , k2 , . . . , kn phần tử sao cho các bao lồi của các lớp riêng lẻ
là rời rạc.



16

1.4

Đếm đa giác

Trong phần này chúng tơi trình bày bài tốn đếm số k -giác có đỉnh từ n điểm
đã cho (4 ≤ k ≤ n) thỏa mãn một số điều kiện nào đó. Đặc biệt là bài tốn
Cayley về số k -giác lồi có đỉnh là đỉnh của một n-giác lồi và cạnh là đường chéo
của n-giác lồi đó.
Mệnh đề 1.4.1 (Cayley). Cho n-giác lồi M và số k thỏa 3 ≤ k ≤ n2 . Khi đó có
n(n−k−1)!
k!(n−2k)!

k -giác lồi có đỉnh là đỉnh của M và cạnh là đường chéo của M .

Chứng minh. Giả sử M là n-giác A1 A2 . . . An và ta sẽ xác định có bao nhiêu
k -giác có đỉnh là An−1 . Kí hiệu các đỉnh cịn lại của k -giác là Ai1 , Ai2 , . . . , Aik−1

trong đó các chỉ số i1 , i2 , . . . , ik−1 thỏa mãn các bất đẳng thức 1 ≤ i1 < i2 < . . . <
ik−1 ≤ n − 3; i2 − i1 ≥ 2, i3 − i2 ≥ 2, . . . , ik−1 − ik−2 ≥ 2. Như vậy (k − 1) chỉ số có



thể được chọn theo n−k−1
cách và do đó số k -giác thỏa yêu cầu với đỉnh An−1
k−1


là n−k−1
k−1 . Cộng số này cho tất cả các đỉnh của M thì mỗi k -giác đã được đếm

k lần, vậy số c(k, n) k -giác thỏa yêu cầu là
n
c(k, n) = ·
k





n−k−1
k−1

Chú ý 1.4.2. Với k = 3 thì c(3, n) =

=

n(n−4)!
3!(n−6)!

n(n − k − 1)!
.
k!(n − 2k)!

=

n(n−4)(n−5)
,
6

điều này đã được


chứng minh ở Mệnh đề 1.3.2.
Khi giải các bài tốn về Hình học tổ hợp, trong nhiều trường hợp chúng tôi
sử dụng phương pháp Tạo đa giác bao dùng để bao một số hữu hạn điểm bởi
một đa giác hoặc một góc.
Bổ đề 1.4.3 (Bổ đề về đa giác bao). Cho n (hữu hạn) điểm khơng cùng thuộc
một đường thẳng. Khi đó tồn tại một đa giác lồi có mỗi đỉnh là một trong n
điểm đã cho, sao cho các điểm còn lại khơng nằm ngồi đa giác.


17

Chứng minh. Vì số điểm đã cho là hữu hạn nên tồn tại một đường trịn có bán
kính đủ lớn chứa tất cả n điễm ấy. Lấy đường thẳng l nằm ngồi đường trịn.
Gọi A1 là điểm gần l nhất (nếu có nhiều điểm thì chọn A1 là điểm cuối dùng ở
bên phải). Qua A1 kẻ đường thẳng d k l.
Quay đường thẳng d quanh A1 ngược chiều kim đồng hồ cho đến khi gặp một
điểm đã cho, ta được đường thẳng d1 , gọi điểm vừa gặp là A2 (nếu có nhiều điểm
thuộc d1 thì chọn A2 là điểm xa A1 nhất).
Quay d1 quanh A2 như cách làm trên, ta được đường thẳng d2 , và cứ tiếp tục
như vậy cho đến khi được đường thẳng đi qua A1 gọi là dm , ta nhận được đa
giác lồi A1 A2 . . . Am thỏa mãn đề bài.
Chú ý 1.4.4. Đa giác lồi được tạo thành theo cách trên gọi là đa giác bao n
điểm đã cho.
Bổ đề 1.4.5 (Bổ đề về góc bao). Cho n (hữu hạn) điểm khơng cùng thuộc một
đường thẳng. Khi đó tồn tại một góc nhỏ hơn góc bẹt có đỉnh là một trong n
điểm đã cho, sao cho các điểm cịn lại khơng thuộc miền ngồi của góc đó.
Chứng minh. Lập luận cách giải tương tự Bổ đề 1.4.3, ta thu được góc A\
2 A1 Am
là góc phải tìm.

Bài tốn 1.4.6. Cho năm điểm trên mặt phẳng sao cho khơng có ba điểm nào
thẳng hàng. Chọn bốn trong số năm điểm đó để tạo thành một tứ giác lồi. Khi
đó có nhiều nhất năm tứ giác lồi được tạo thành.
Lời giải. Kí hiệu S là tập hợp các điểm đã cho và K là bao lồi của S . Ta có các
trường hợp sau:
a) K là một ngũ giác. Khi đó mỗi tứ giác có đỉnh thuộc S đều là tứ giác lồi và


có 54 = 5 tứ giác lồi.


18

b) K là tứ giác lồi A1 A2 A3 A4 trong khi đỉnh A5 ∈ S nằm phía trong của K .
Giả sử P là giao điểm của hai đường chéo của tứ giác A1 A2 A3 A4 . Khi đó A5
là điểm trong của một trong bốn tam giác A1 A2 P, A2 A3 P, A3 A4 P, A1 A4 P , giả sử
A5 ∈ 4A1 A2 P . Khi đó ta có chính xác ba tứ giác lồi đó là A1 A2 A3 A4 , A1 A5 A3 A4

Hình 1.6:

và A2 A3 A4 A5 (Hình 1.6(a)).
c) K là tam giác A1 A2 A3 trong khi hai đỉnh A4 , A5 ∈ S nằm trong K . Các đường
thẳng A1 A4 , A2 A4 , A3 A4 lần lượt cắt các cạnh của K tại B1 , B2 , B3 và chia K
thành sáu tam giác và điểm A5 là điểm trong của một trong sáu tam giác ấy.
Không mất tính tổng quát giả sử A5 ∈ 4A1 A4 B3 , khi đó bốn điểm A1 , A3 , A4 , A5
theo thứ tự ấy là đỉnh của một tứ giác lồi (Hình 1.6(b)).

1.5

Hệ điểm và đường thẳng


Trong phần này chúng tôi nghiên cứu một số vấn đề liên quan đến các hệ
hữu hạn điểm và đường thẳng trong mặt phẳng. Một trong nhiều phương pháp
được chúng tôi sử dụng trong luận văn này là Nguyên lý cực hạn: Trong một
tập hợp hữu hạn (khác rỗng) các số thực, tồn tại số nhỏ nhất và số lớn nhất.


19

Nhờ nguyên lý này ta có thể xét các phần tử mà một đại lượng nào đó có giá
trị nhỏ nhất hoặc lớn nhất.
Mệnh đề 1.5.1 (Sylvester - Gallai). Cho S là tập hợp hữu hạn điểm nằm trên
mặt phẳng sao cho các điểm này không cùng nằm trên một đường thẳng. Khi
đó tồn tại một đường thẳng chỉ chứa hai điểm thuộc S .
Chứng minh. Gọi L là tập hợp (hữu hạn) các đường thẳng đi qua ít nhất hai
điểm thuộc S . Xét các khoảng cách từ một điểm thuộc S đến một đường thẳng

Hình 1.7:

thuộc L, ta xét khoảng cách dương nhỏ nhất và giả sử đó là khoảng cách từ
A ∈ S đến l ∈ L. Gọi B là hình chiếu của A lên l, khi đó đường thẳng l chia

thành hai tia gốc B . Ta sẽ chứng minh trên mỗi tia có nhiều nhất một điểm
thuộc S . Thật vậy, giả sử một trong hai tia gốc B chứa hai điểm C1 , C2 ∈ S và
0 ≤ |BC1 | ≤ |BC2 |. Khi đó tam giác 4AC1 C2 là tam giác tù hoặc tam giác vng

(khi B ≡ C1 ) với góc lớn nhất là C1 . Do đó |C1 C2 | < |AC2 |, và thơng qua việc
tính diện tích 4AC1 C2 theo hai cách khác nhau ta suy ra rằng khoảng cách từ
C1 đến AC2 nhỏ hơn khoảng cách từ A đến l. Điều này mâu thuẫn với cách chọn
A và l. Vì vậy có đúng hai điểm thuộc S trên đường thẳng l.


Bài toán 1.5.2. Cho 10 đường thẳng trong đó khơng có hai đường thẳng nào
song song. Biết rằng qua giao điểm của hai đường thẳng bất kỳ trong 10 đường


20

thẳng ấy cịn có ít nhất một trong các đường thẳng cịn lại đi qua. Khi đó tất
cả 10 đường thẳng đó đồng quy.
Lời giải. Giả sử phản chứng rằng 10 đường thẳng khơng đồng quy. Xét đường
thẳng d, có một hoặc nhiều giao điểm của hai đường thẳng đã cho không nằm
trên d, ta gọi A là điểm nằm gần d nhất. Theo giả thiết qua A có ít nhất ba

Hình 1.8:

đường thẳng đi qua. Do khơng có hai đường thẳng nào song song nên ba đường
thẳng này cắt d tại ba điểm, gọi là B, C, D và giả sử C nằm giữa B và D (Hình
1.8).
Cũng theo giả thiết, qua C cịn có một đường thẳng nữa, đường thẳng này phải
cắt một trong hai đoạn thẳng AB, AD, chẳng hạn nó cắt AD tại E nằm giữa A
và D. Khi đó dễ thấy khoảng cách từ E đến d nhỏ hơn khoảng cách từ A đến
d, điều này mâu thuẫn với cách chọn điểm A và đường thẳng d. Vậy 10 đường

thẳng này đồng quy.
Mệnh đề 1.5.3. Cho tập hữu hạn S gồm n ≥ 3 điểm không thẳng hàng trong
mặt phẳng. Xét các đường thẳng nối hai điểm thuộc S . Khi đó có ít nhất n
đường thẳng phân biệt.
Chứng minh. Ta chứng minh bằng phương pháp quy nạp toán học theo n. Với
n = 3, khẳng định của mệnh đề là đúng, giả sử khẳng định của mệnh đề đúng



21

với n = k (k ≥ 4), ta sẽ chứng minh khẳng định của mệnh đề đúng với n = k + 1.
Theo Mệnh đề 1.5.1, trong số các đường thẳng nối hai điểm thuộc S tồn tại một
đường thẳng chỉ chứa hai điểm A, B ∈ S . Xét điểm A và đặt S 0 = S\{A}. Khi
đó ta có hai trường hợp: Nếu tất cả k điểm thuộc S 0 cùng nằm trên một đường
thẳng l thì ta có hệ gồm (k + 1) đường thẳng phân biệt {AX : X ∈ S 0 } ∪ {l};
Trong trường hợp ngược lại, theo giả thiết quy nạp có ít nhất k đường thẳng
phân biệt trong các đường thẳng nối hai điểm thuộc S 0 và khơng có đường thẳng
nào trong đó trùng với đường thẳng AB vì theo cách chọn đường thẳng AB chỉ
chứa hai điểm thuộc S .
Bài tốn 1.5.4. Cho bốn điểm khơng thẳng hàng trong mặt phẳng.
i) Từ bốn điểm ấy ta có thể chọn ra một tam giác có một góc khơng vượt q
45◦ .

ii) Tồn tại một hệ bốn điểm như vậy sao cho khơng có tam giác nào có góc nhỏ
hơn 45◦ .
Lời giải. i) Ta xét hai trường hợp bao lồi của bốn điểm đã cho.
Trường hợp 1: Bao lồi là tam giác 4A1 A2 A3 và điểm A4 nằm bên trong 4A1 A2 A3
(Hình 1.9(a)). Khi đó các đoạn thẳng A1 A4 , A2 A4 , A3 A4 chia các góc trong của

Hình 1.9:
4A1 A2 A3 thành sáu góc nhỏ, trong đó có ít nhất một góc khơng lớn hơn

180◦
6

=