TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
==***==

NGUYỄN THỊ HOA

ỨNG DỤNG TÍNH CHẤT CỦA TẬP LỒI
GIẢI MỘT SỐ BÀI TOÁN
HÌNH HỌC TỔ HỢP
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Hình học

HÀ NỘI - 2012


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
==***==

NGUYỄN THỊ HOA

ỨNG DỤNG TÍNH CHẤT CỦA TẬP LỒI
GIẢI MỘT SỐ BÀI TOÁN
HÌNH HỌC TỔ HỢP
TÓM TẮT KHOÁ 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
ThS.GVC. Phan Hồng Trường

HÀ NỘI - 2012


MC LC
Mở đầu............................................................................................................... 1
Chng 1: Hình lồi............................................................................................ 2
1.1. Các định nghĩa: ...................................................................................... 2
1.2. Bao lồi và bao lồi đóng. .......................................................................... 3
1.3. Nón lồi .................................................................................................... 5
Chương 2: Một số vấn đề của hình học tổ hợp.................................................. 7
2.1. Định lí Kelli trong không gian một chiều R1. ...................................... 7
2.2. Định lí Kelli trong không gian hai chiều R2. ....................................... 8
2.3. Ví dụ: ................................................................................................. 10
Chng 3: Một số bài toán của hình học tổ hợp ............................................. 13
3.1. Một số phương pháp giải thông thường ................................................ 13
3.1.1. Phương pháp sử dụng định lí Kelli................................................. 13
3.1.2. Phương pháp lấy bao lồi. ............................................................... 16
3.2. Một số bài toán thường gặp. ................................................................. 28
Kết luận ........................................................................................................... 39
Tài liệu tham khảo........................................................................................... 40



Mở đầu
1. Lí do chọn đề tài
Hình học là một môn học quan trọng, tương đối khó trong chương trình
Toán phổ thông và có rất nhiều ứng dụng trong đời sống con người, để hiểu
được nó người học cần tưởng tượng tư duy cao. Đặc biệt, hình học tổ hợp là
một nhánh của hình học mà chúng ta thường gặp trong các kì thi chọn học
sinh giỏi toán trong nước và quốc tế. Trong hình học tổ hợp có rất nhiều kết
quả nghiên cứu được các nhà toán học các ngành khác quan tâm. Với mong
muốn được nghiên cứu sâu hơn về hình học tổ hợp và tìm hiểu được nhiều
phương pháp giải toán hình học tổ hợp hay hơn, cụ thể hơn, trực quan hơn,

a(a1,a2,,an), b(b1, b2, , bn); O(0, 0, , 0) thì đoạn nối ab là tập hợp các
điểm y(y1, y2, , yn) thỏa mãn:
yi tai (1 t )bi , i 1, n với t 0;1 .

Ví dụ 1.1.1: Trong mặt phẳng tọa độ Oxy có a(5;2), b(3;1). Khi đó x a; b
nếu x(x1; x2) có tọa độ thỏa mãn:
x1 t.5 (1 t ).3
với t 0;1

x2 t.2 (1 t ).1

Định nghĩa 1.1.2: Tập hợp P X , P được gọi là tập lồi nếu
a, b P, x X thỏa mãn: x ta (1 t )b thì x P .

Quy ước: Tập là tập lồi.
Ví dụ 1.1.2: Đoạn thẳng a; b là tập lồi.
Định lí 1.1.1: Giao của các tập lồi bất kì là tập lồi, tức: Nếu Pi X (i I ) là
các tập lồi, với I là tập chỉ số bất kì thì P Pi cũng là tập lồi.
iI

Chứng minh:
Lấy x1 , x2 Pi (i I )
Với i I do Pi lồi nên tx1+(1 - t)x2 Pi t 0;1
tx1 (1 t ) x2 P (điều phải chứng minh).

Nhận xét 1.1.2: Nếu P1, P2 là tập lồi thì P1 P2 chưa chắc đã là tập lồi.
2


Thật vậy: H1 A, H 2 a với a là đường thẳng không qua A.

k

Bởi vì


i 1

ti
0 (i 1, k ) .
1 tk 1

ti
1 cho nên theo giả thiết quy nạp ta có:
1 tk 1
y

t1
tk
x1 ...
xk A
1 t k 1
1 t k 1

Với các điểm y A ; xk 1 A , ta có 1 tk 1 0; (1 tk 1 ) tk 1 1 , do đó:
x (1 tk 1 ) y t k 1 xk 1 A (điều phải chứng minh).

1.2. Bao lồi và bao lồi đóng.
Định nghĩa 1.2.1: Giả sử là tập lồi tùy ý thuộc X, Pi iI là họ tất cả các tập
lồi chứa , với I là tập chỉ số. Khi đó P i được gọi là bao lồi của tập .
iI


Mặt khác co co bởi vì co là giao của tất cả các tập lồi (không cần
đóng) chứa . Vì vậy co co .

(2)

Từ (1) và (2) suy ra co co .
4


1.3. Nón lồi
Giả sử X là không gian tuyến tính.
Định nghĩa 1.3.1: Cho tập K X , thỏa mãn: x K , 0 x K được gọi
là nón có đỉnh tại O.
Tập K được gọi là nón có đỉnh tại x0, nếu K - x0 là nón có đỉnh tại O.
Định nghĩa 1.3.2: Nón K có đỉnh tại O được gọi là nón lồi nếu K là tập lồi, có
nghĩa là:
x, y K , , 0 x y K .

Nhận xét 1.3.1: Khi xét trong En.
Tập K E n thỏa mãn: a K , t 0 VOt (a) K , với VOt là phép vị tự
tâm O tỉ số k, với O E n được gọi là nón có đỉnh tại O.
Mệnh đề 1.3.1: Giả sử K i i I là các nón lồi có đỉnh tại O, với I là tập chỉ số
bất kì. Khi đó

K

i

là nón lồi có đỉnh tại O.


mà

a K
i i

thì K là nón lồi nhỏ nhất chứa A.

i 1

Định nghĩa 1.3.3: Ta gọi là nón lồi sinh bởi A là một tập hợp là giao của tất
cả các nón lồi (có đỉnh tại O) chứa A và điểm O. Kí hiệu là KA.
Mệnh đề 1.3.2:
a) KA = KcoA.
b) Nếu A là tập lồi thì K A A a X : a b, 0, b A.
0

6


Chương 2: một số vấn đề của hình học tổ hợp
Một câu hỏi được đặt ra là nếu cho trước một họ các hình lồi thì khi nào
họ hình lồi này khác rỗng ?
Trong không gian một chiều, câu hỏi này được trả lời bằng việc chứng
minh định lí sau:
2.1. Định lí Kelli trong không gian một chiều R1.
Định lí 2.1: Trên đường thẳng cho n hình lồi (n 3). Biết rằng giao của hai
hình lồi bất kì trong chúng khác rỗng. Khi đó giao của cả n hình lồi cũng khác
rỗng.
Chứng minh:


Từ (1) suy ra ai c bi c ai; bi
aj c bj c aj; bj
ai; bi aj; bj . Bổ đề được chứng minh.
7


Từ bổ đề trên suy ra min
bi max ai
1i n

(2)

1 i n

Từ (2) suy ra tồn tại c sao cho min
bi c max ai
1i n

(3)

1i n

n

c ai; bi,i = 1, n

hay

a ; b


Do A1 F2 F3 F4 nên A1 F3
A2 F1 F3 F4 nên A2 F3
Vì F3 lồi, mà A1 F3, A2 F3 nên [A1,A2] F3. Do đó O F3
Lập luận tương tự suy ra O F1, O F2 , O F4
4

Nghĩa là O

4

F . Do đó F
i

i

i 1



i 1

b2) Bao lồi của chúng là tam giác chứa một điểm còn lại bên trong.
Không giảm tính tổng quát ta có thể giả sử A1A2A3 thuộc F4
Vì A1, A2, A3 đều thuộc F4, mà F4 lồi.
Mặt khác: A4 F1 F2 F3
4

A4




Nếu trong chúng có Fn = Fn Fn+1. Khi đó, giả sử Fk = Fn
Từ đó Fi Fj Fk = Fi Fj Fn Fn+1.
Vì giao của 3 hình lồi trong các hình lồi Fi, Fj, Fn, Fn+1 là khác rỗng
(giả thiết) nên theo trường hợp n = 4, ta có Fi Fj Fn Fn+1
Vậy với hình lồi F1, F2,, Fn thỏa mãn điều kiện giao của 3 hình lồi
bất kì trong chúng khác rỗng nên theo giả thiết quy nạp suy ra
F1F2Fn . Nghĩa là: F1 F2 Fn Fn+1 .
Vậy định lí Kelli đúng trong trường hợp có n + 1 hình lồi.
Theo nguyên lí quy nạp suy ra định lí Kelli đúng với mọi n 4.
Định lí Kelli được chứng minh.
2.3. Ví dụ:
Ví dụ 2.3.1: Cho bốn nửa mặt phẳng lấp đầy mặt phẳng. Chứng minh rằng tồn
tại ba nửa mặt phẳng trong bốn nửa mặt phẳng ấy, sao cho chỉ riêng ba nửa
mặt phẳng này cũng lấp đầy mặt phẳng.
Giải:
Gọi P1, P2, P3, P4 là bốn nửa mặt phẳng. Từ giả thiết ta có:
P1 P2 P3 P4 =

2

(1)

Ta thấy Pi là lồi với mọi i = 1, 4
Từ (1) suy ra P1 P2 P3 P4

(2)

( A là phần bù của tập hợp A).

hình tròn tuỳ ý, luôn tồn tại một hình tròn bán kính R chứa cả 3 hình tròn.
Chứng minh rằng tồn tại một hình tròn bán kính R chứa cả n hình tròn đã cho.
Giải:
Gọi i là các hình tròn có tâm Oi, bán kính Ri, i = (Oi; Ri), i = 1, n .
Gọi Fi là các hình tròn có tâm Oi và bán kính R - Ri.
Fi = (Oi; R - Ri), i = 1, n .
Lấy i, j, k tuỳ ý (1 i < j < k n), ta sẽ chứng minh: Fi Fj Fk .
Thật vậy, theo giả thiết tồn tại hình tròn (Oi,j,k; R) phủ i, j, k, tức là:
i j k (Oi,j,k; R).

2

1

3

(Oi,j,k; R)

Nói riêng ta có: i (Oi,j,k; R).
nên OiOi,j,k R - Ri hay (Oi; R - Ri) chứa Oi,j,k.
Do đó Oi,j,k Fi.

11


Lập luận tương tự, ta có Oi,j,k Fj , Oi,j,k Fk.
Do vậy Fi Fj Fk .
Từ đó theo định lí Kelli suy ra: F1 F2 Fn .
Giả sử O* F1 F2 Fn .
n

3.1.1. Phương pháp sử dụng định lí Kelli
Ví dụ 3.1.1: Cho một số hữu hạn n 4 các đường thẳng. Biết rằng với ba
đường thẳng tuỳ ý luôn tồn tại hình tròn có bán kính R cắt cả ba đường thẳng.
Chứng minh rằng tồn tại một hình tròn có bán kính R cắt cả n đường thẳng đó.
Giải:
R
R
di

Fi
R

Giả sử d1, d2, , dn là họ hữu hạn các đường thẳng (n 4).
Với mỗi đường thẳng di ta xét Fi là hình tạo bởi hai đường thẳng
song song với di và cách di một khoảng bằng R. Tâm các đường tròn bán kính
R mà cắt di thì phải nằm trong Fi. Rõ ràng Fi là hình lồi với mọi i 1, n .
Như thế ta có một họ hữu hạn các tập hợp lồi F1, F2, , Fn. Theo giả
thiết với mọi i, j, k {1, 2, 3, , n} ta luôn có Fi Fj Fk (vì với mọi i,
j, k luôn tồn tại một hình tròn cắt cả di, dj, dk). Theo định lí Kelli suy ra
F1 F2 Fn .
Lấy O* F1 F2 Fn. Hình tròn tâm O*, bán kính R, (O*; R) sẽ
cắt tất cả các đường thẳng d1, d2, , dn. Đó là điều phải chứng minh.
13


Ví dụ 3.1.2: Trên mặt phẳng có một họ hữu hạn các hình chữ nhật có các cạnh
tương ứng song song với hai trục toạ độ. Chứng minh rằng nếu hai hình bất kì
trong chúng có giao khác rỗng thì cả họ có giao khác rỗng.
Giải:
y

ta đã chứng minh được sự tồn tại a*

i 1

n

[a ; b ] .
i

i

i 1

Tương tự ta cũng chứng minh được sự tồn tại b*

n

[c ; d ] .
i

i 1

Điều đó chứng tỏ rằng (a*; b*)

n

F . Điều phải chứng minh.
i

i 1

O
M3

M2

Xét đường tròn ngoại tiếp tam giác M1M2M3 có tâm là O và bán kính R (O
nằm trong tam giác do tam giác không tù). Ta có thể giả sử M 1OM 3 1200 .
1
1
M 1M 3
1
2
R = OM1 2
(do M1M3
0
sin 60
3
3
2

OM1 = OM2 = OM3

1).

1
O F1 F2 F3 F1 F2 F3
3

b) M1M2M3 lập thành tam giác tù
15


1
.
3

Vì O*Fi nên O*Mi

1
. Từ đó suy ra hình tròn tâm O* và bán kính
3

1
3

chứa Mi.
Vậy hình tròn tâm O* phủ n điểm.
3.1.2. Phương pháp lấy bao lồi.
Giải bài toán hình học tổ hợp bằng phương pháp lấy bao lồi tức là ta sẽ
bao một số hữu hạn điểm bởi một đa giác, gọi là đa giác bao, đó cũng chính là
bao lồi của họ hữu hạn điểm đó. Trước khi xét một số ví dụ cụ thể ta sẽ chứng
minh bổ đề sau:

16


Bổ đề (về đa giác bao): Trong mặt phẳng, bao lồi của n điểm tuỳ ý là một đa
giác lồi (hoặc là đoạn thẳng) với đỉnh là một số điểm trong các điểm đã cho.
Chứng minh:
Nếu cả hệ điểm thẳng hàng thì hiển nhiên bao lồi của chúng là một
đoạn thẳng.

17


2. Nếu bao lồi của là một đa giác lồi. Chọn A là một đỉnh của bao lồi của .
B1

A
d

B2

A

d

Bi

B3

Bj

B4

Giả sử gần A nhất có quá 3 điểm có khoảng cách bằng d tới A. Theo
định nghĩa của d, thì với mọi i j, BiBj d (ở đây B1, B2, B3, B4, là các điểm
có khoảng cách tới A đều là d). Xét tam giác BiABj có ABi = ABj = d, còn BiBj
d, từ đó suy ra Bi AB j 600 , nên B1 AB2 B2 AB3 B3 AB4 ... 1800 .
Do vậy A B1 AB2 B2 AB3 B3 AB4 ... 1800 ( A là góc của đa giác lồi). Rõ
ràng góc A < 1800, mâu thuẫn.
Do đó giả thiết phản chứng là sai. Vậy ta có điều phải chứng minh.

D

A

A

D

E

(H1)

(H2)

3. Bao lồi là tam giác (có thể cho là tam giác ABC). Khi đó hai điểm D, E nằm
hẳn bên trong tam giác ABC, ngoài ra E không nằm trên các đường thẳng AD,
BD, CD.
A

H

D

E

B

K

C