Định lí Helly và ứng dụng

Chia sẻ: AndromedaShun _AndromedaShun | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

90
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Định lí Helly là một định lí rất quan trong phần hình học tổ hợp. Định lí này cho ta một điều kiện đủ để nhận biết khi nào một họ các hình lồi có giao khác rỗng. Đối với một lớp tập hợp cụ thể như hình bình hành, đoạn thẳng thì có giảm nhẹ điều kiện của định lí Helly. Và ở đây, ta còn xét sự mở rộng của định lý, đặc biệt đối với tập hợp có thể không lồi như cung đường tròn chẳng hạn. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Định lí Helly và ứng dụng

Hội thảo khoa học, Hưng Yên 25-26/02/2017 ĐỊNH LÍ HELLY VÀ ỨNG DỤNG Nguyễn Thị Tâm - Hoàng Thị Nhung - Trần Thi Hằng THPT Chuyên Hưng Yên Tóm tắt nội dung Định lí Helly là một định lí rất quan trong phần hình học tổ hợp. Định lí này cho ta một điều kiện đủ để nhận biết khi nào một họ các hình lồi có giao khác rỗng. Đối với một lớp tập hợp cụ thể như hình bình hành, đoạn thẳng thì có giảm nhẹ điều kiện của định lí Helly. Và ở đây, ta còn xét sự mở rộng của định lý, đặc biệt đối với tập hợp có thể không lồi như cung đường tròn chẳng hạn. 1 Cơ sở lý thuyết 1.1 Các định lí Helly Định lý 1 (Định lí Helly trong không gian một chiều). Trên đường thẳng cho n hình lồi (n ≥ 3). Biết rằng giao của hai hình bất kì trong chúng khác rỗng. Khi đó, giao của n hình lồi đã cho khác rỗng. Định lý 2 (Định lí Helly trong không gian hai chiều). Cho trước n hình lồi trên mặt phẳng (n ≥ 4). Biết rằng giao của ba hình lồi bất kì trong chúng khác rỗng. Khi đó, giao của các hình lồi đã cho khác rỗng. Định lý 3 (Định lí Helly trong không gian ba chiều). Cho trước n hình lồi trong không gian (n ≥ 5).Biết rằng giao của bốn hình bất kì trong chúng khác rỗng. Khi đó giao của các hình lồi đã cho khác rỗng. Định lý 4 (Định lí Helly trong không gian n chiều). Cho trước n hình lồi trong không gian k - chiều Rk (n ≥ k + 1, k ∈ N ∗ ). Biết rằng (k + 1) hình lồi bất kì trong chúng có giao khác rỗng. Khi đó, giao của các hình lồi đã cho khác rỗng. 1.2 Một số hệ quả của định lí Helly Hệ quả 1. Cho trước n đoạn thẳng [ ai ; bi ] (i = 1,2,3,. . . ,n) trên cùng một đường thẳng. Khi đó giao của các đoạn thẳng này khác rỗng khi chỉ và chỉ khi giao của hai đoạn thẳng bất kỳ trong chúng khác rỗng. Chứng minh. Ta chú ý mọi tập lồi A trên đường thẳng thể hiện hoặc là đoạn thẳng, hoặc là một tia hoặc là cả đường thẳng. Định lí Helly với giả thiết trong trường hợp này thực sự có ý nghĩa khi các tệp A1 , A2 , . . . , An là những đoạn thẳng (còn những trường hợp khác như trong số những tập hợp này tia và đường thẳng thì ta cũng đưa về trường hợp 205
Hội thảo khoa học, Hưng Yên 25-26/02/2017 tất cả là đoạn thẳng). Mỗi đoạn thẳng Ai trên đường thẳng số được xác định bởi hai số tại hai điểm cuối ai , bi và ai ≤ bi . Số ai gọi là đầu trái của Ai , còn bi gọi là đầu phải của Ai . Lấy b là số nhỏ nhất của bi , i = 1, 2, . . . , n; a là số lớn nhất của ai , i = 1, 2, . . . , n. Ta chứng minh rằng a ≤ b. Thật vậy, giả sử a > b. Vì a trùng với một trong những số nào đó trong ai , i = 1, 2, . . . , n, còn b trùng với một trong những số nào đó trong bi , i = 1, 2, . . . , n, thì ai1 = a > b = bi2 . Khi đó chỉ ra rằng những đoạn thẳng Ai1 (với đầu trái ai1 ) và Ai2 (với đầu phải Bi2 ) không có điểm chung. Ta nhận được sự vô lí. Hệ quả 2. Cho trước một họ I các đoạn thẳng [ ai ; bi ] (i ∈ I, I ⊂ N) trên cùng một đường thẳng. Khi đó giao của các đoạn thẳng này khác rỗng khi và chỉ khi giao của hai đoạn bất kỳ trong chúng khác rỗng. Hình bình hành có các tính chất đặc biệt hơn những hình lồi khác. Đặc biệt hơn là những hình bình hành có các cạnh song song với hai đường thẳng cố định. Khi đó, theo định lí Helly ta còn có các hệ quả sau: Hệ quả 3. Cho hình bình hành F1 , F2 , F3 , các cạnh của chúng song song với hai đường thẳng cố định. Khi đó, nếu mọi cặp hai hình trong chúng có điểm chung, thì cả ba hình bình hành cũng có điểm chung. Chứng minh. Ta chọn trong mặt phẳng hệ tọa độ với các trục nằm trên hai đường thẳng đã cho (không nhất thiết hệ tọa độ vuông góc, ta đang xét hệ tọa độ bất kì.) Kí hiệu A1 là điểm chung của F2 và F3 , A2 là điểm chung của F1 và F3 , A3 là điểm chung của của F1 và F2 . Kí hiệu ( xi , yi ) là tọa độ của điểm Ai đơi với hệ tọa độ đã chọn (i = 1; 2; 3). Không mất tính tổng quát, ta có thể giả thiết những hình bình hành F1 , F2 , F3 được gán nhãn sao cho với các tọa độ tương ứng x1 , x2 , x3 thỏa mãn bất đẳng thức x1 ≤ x2 ≤ x3 . Hình bình hành F1 sẽ chứa các điểm A2 và A3 (hình 3.7). Khi đó, nó chứa tất cả những điểm P với tọa độ ( x, y) sao cho x2 ≤ x ≤ x3 , y2 ≤ y ≤ y3 với y2 ≤ y3 hoặc là y3 ≤ y ≤ y2 với y3 ≤ y2 (hình 1 là trường hợp thứ hai). Tương tự, F2 chứa tất cả những điểm P có tọa độ ( x, y) sao cho x1 ≤ x ≤ x3 , y1 ≤ y ≤ y3 hoặc là y3 ≤ y ≤ y1 phụ thuộc vào y1 ≤ y3 hoặc là y3 ≤ y1 . Ta lặp lại lí luận trên với hình bình hành F3 , ta sẽ thui được sự tồn tại điểm P với tọa độ ( x2 , z), mà nó nằm trên cả ba hình bình hành. Thật vậy, cho các chỉ số i; j; k nhận những giá trị 1; 2; 3 và giả sử rằng bất đẳng thức sau đúng yi ≤ y j ≤ yk . Khi đó bằng cách đặt yi = z, sẽ nhận được kết quả cần thiết. Từ kết quả trên và định lí Helly suy ra kết quả: Hệ quả 4. Trong mặt phẳng cho n hình bình hành có các cạnh song song với hai đường thẳng cố định. Nếu mọi cặp hai hình bình hành có điểm chung thì tất cả n hình bình hành có điểm chung. 206
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Chứng minh. Nếu mọi hai bình hành có điểm chung thì mọi ba hình bình hành cũng có điểm chung, từ đây áp dụng định lí Helly ở phần trước. Điều kiện những cạnh của hình bình hành song song với hai đường thẳng cố định là bản chất. Bây giờ ta xét tập hợp tất cả những cung trên đường tròn. Dễ thấy một cung trên đường tròn không phải là tập lồi trong mặt phẳng. Mặt khác, mỗi cung đặc trưng bởi hình viên phân của đường tròn tương ứng với hình tròn đã cho. Mỗi hình viên phân này là một tập hợp lồi và cho n hình viên phân, ta có thể áp dụng định lí Helly. Hơn nữa, nếu hai cung có điểm chung thì những hình viên phân tương ứng cũng có điểm chung. Tuy vậy, định lí Helly không đúng nữa. Nếu ta xét những cung của đường tròn có độ dài nhỏ hơn độ dài nửa đường tròn thì khi đó tình thế sẽ khác đi. Ta có kết quả sau: Hệ quả 5. Trên đường tròn cho n > 3 cung, mỗi cung có độ dài nhỏ hơn độ dài của nửa đường tròn. Khi đó, nếu mọi bộ ba cung có điểm chung thì tất cả các cung có điểm chung. Chứng minh. Ta cho tương ứng mỗi cung ứng với hình viên phân của đường tròn xác định trên hình tròn. Trên mỗi hình viên phân có dây cung không phải là đường kính của hình tròn (do giả thiết các cung đã cho nhỏ hơn nửa độ dải đường tròn). Từ giả thiết mọi bộ ba cung có điểm chung suy ra mọi bộ ba hình viên phân có điểm chung. Sử dụng định lí Helly cho tập hợp các hình viên phân, ta nhận được tất cả các hình viên phân đều có điểm chung. Điểm này không thể trùng với tâm của hình tròn. Từ điểm chung của các hình viên phân, kẻ đường kính, một trong các điểm giao giữa đường kính vừa kẻ và đường tròn sẽ là điểm chung cho n cung đã cho (dễ thấy đường nối tâm đường tròn với một điểm bất kì trong hình viên phân đều cắt cung của hình viên phân ấy). Bộ ba cung trong định lí trên là hoàn toàn thực chất. Nếu ta xét trên đường tròn ba cung AB, c BC, d mỗi cung là 120◦ , ta nhận được mỗi cặp hai cung này có điểm chung, c CA, nhưng cả ba cung không có điểm chung. Hệ quả 6. Trên một đường tròn cho n cung, mỗi cặp cung có điểm chung. Khi đó, tồn tại đường thẳng đi qua tâm đường tròn và cắt tất cả các cung đã cho. Chứng minh. Ta kí hiệu Γ là tập hợp n cung. Ta chọn trong chúng cung ABc có độ dài nhỏ nhất (điều này làm được vì Γ là tập hợp hữu hạn), nghĩa là với mọi cung MN d ≥ AB.c không mất tính tổng quát, ta có thể giả thiết rằng cung AB c ứng với góc ở tâm nhỏ hơn 180 , vì trong trường hợp ngược lại mọi đường kính sẽ cắt mỗi cung của tập hợp Γ. Theo ◦ điều kiện của định lí, mỗi cung của Γ chứa hoặc là điểm A, hoặc là điểm B, hoặc là cả hai điểm đồng thời. Ta xét tập hợp Γ1 ⊂ Γgồm những cung chứa điểm A. Trên mỗi cung d ∈ Γ1 , ta lấy tương ứng MN MN d ∩ AB, c nó sẽ không phải là tập hợp rỗng và có thể chỉ gồm duy nhất một điểm. Cho CD d ∈ Γ1 tương ứng có giao là một điểm (đối với cung AB) c d ∩ AB, MN hoặc có độ dài nhỏ nhất giữa tất cả các cung MN c d ∈ Γ1 . Ta dựng đường kính DD 0 qua điểm D. Nếu δ ∈ Γ và D ∈ / δ, thì cung δ chứa những điểm B và C. Từ đó suy ra nó chứa cả điểm D 0 . Suy ra đường kính DD 0 cắt mọi cung của Γ, đó là điều phải chứng minh. Hệ quả 7. Cho n hình lồi, mọi cặp hai hình đều có điểm chung. Khi đó qua mọi điểm bất kì trong mặt phẳng, có thể kẻ đường thẳng cắt tất cả n hình. 207
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Chứng minh. Ta xét đường tròn k có tâm tại một điểm O. Trên mỗi hình từ những hình đã cho, ta cho tương ứng với một cung của đường tròn này theo cách sau: Mỗi điểm P trên một hình tương ứng nối với tâm O của đường tròn k và cho P tương ứng với điểm cắt của tia OP với đường tròn k. Nếu P trùng với O thì cách đặt tương ứng trên không có nghĩa, nên ta chỉ định nghĩa cho phép tương ứng trên cho các hình không chứa điểm O, với cách cho tương ứng trên sẽ là một cung nào đó của k. Những cung này sẽ thỏa mãn giả thiết của định lí vừa chứng minh ở trên. Điều đó chỉ ra rằng tồn tại đường thẳng đi qua o cắt tất cả các cung và hơn nữa cắt tất cả các hình đã cho (đường thẳng này hiển nhiên cắt cả những hình, với chúng không xác định ở trên, vì chúng đều chứa O). Đó là điều ta cần phải chứng minh. Tồn tại rất nhiều phương án của định lí Helly, trong đó điều kiện hai hoặc một số hình lồi có điểm chung thay bằng điều kiện những hình này có lát cắt. Bạn đọc có thể suy nghĩ và biến đổi các ý tưởng trên. Hệ quả 8. Trong mặt phẳng cho k điểm (k ≥ 3) điểm. Biết rằng mọi cặp ba điểm trong chúng đều nằm trong đường tròn bán kính bằng 1. Khi đó tất cả các điểm đã cho đều chứa trong đường tròn bán kính bằng 1. Chứng minh. Những điểm đã cho là x1 , x2 , . . . , xk . Cần phải chứng minh rằng tồn tại điểm x cách mỗi điểm đã cho một khoảng cách không vượt quá 1. Nghĩa là phải tìm một điểm nằm trong tất cả các đườngtròn Bi có tâm xi và bán kính bằng 1. Theo định lí Helly chỉ cần chứng minh mọi bộ ba hình tròn từ họ B1 , B2 , . . . , Bk có điểm chung. Nhưng điều đó chính là giả thiết của bài toán đã cho. Mọi bộ ba điểm xi1 , xi2 , xi3 chứa trong hình tròn bán kính 1 và tâm của hình tròn này sẽ nằm trong Bi1 , Bi2 , Bi3 . Hệ quả 9 (Định lí Yong). Trong mặt phẳng cho một số hữu hạn điểm, khoảng cách giữa hai điểm bất kì trong chúng không vượt quá 1. Chứng minh rằng tồn tại một hình tròn 1 bán kính bằng √ chứa tất cả các điểm đã cho. 3 Chứng minh. Nếu mọi bộ ba điểm của những điểm đã cho chứa trong đường tròn bán 1 kính bằng √ , thì ta có thể áp dụng lí luận chứng minh ở kết quả 8 ở trên và nhận được 3 1 tất cả các điểm nằm trong đường tròn bán kính bằng √ . 3 Cho A, B, C là ba điểm trong các điểm đã cho. Nếu tam giác ABC là tam giác tù hoặc vuông, thì hình tròn có tâm tại trung điểm của cạnh dài nhất và bán kính bằng nửa cạnh 208
Hội thảo khoa học, Hưng Yên 25-26/02/2017 này sẽ chứa toàn bộ tam giác. Bởi vì, khoảng cách giữa hai điểm bất kì từ những điểm đã cho không quá 1, thì hình tròn kể trên phủ những điểm A, B, C sẽ có bán kính lớn nhất 1 1 là , mà nó nhỏ hơn √ . 2 3 Còn lại, ta xét trường hợp tam giác ABC là nhọn. Ta xét đường tròn ngoại tiếp tam giác ABC. Kí hiệu bán kính của đường tròn này là r. Có ít nhất một trong những góc của tam giác không nhỏ hơn 60◦ , giả sử đó là A b (trường hợp ngược lại thì tổng ba góc của tam ◦ c nhỏ nhất là 120circ trên cung này tương ứng giác nhỏ hơn 180 , vô lí.) Khi đó, cung BC √ √ với dây cung BC có độ dài không nhỏ hơn r 3 (r 3 là độ dài của dây cung tương √ ứng ◦ với cung 120 ). Nhưng từ điều kiện của bài toán có 1 ≥ BC, nghĩa là 1 ≥ BC ≥ r 3. Suy 1 ra r ≤ √ và ba điểm A, B, C cũng thuộc đường tròn với bán kính bằng 1. 3 1 Chú ý 1. Số √ trong định lí Yong không thể giảm hơn được nữa. Những đỉnh của một 3 tam giác đều với cạnh bằng 1 là ví dụ của tập hợp tất cả những điểm mà khoảng cách giữa hai điểm trong chúng bằng 1, những ba điểm này không chứa trong đường tròn bán kính nhỏ hơn √13 . 2 Một số bài toán áp dụng Bài toán 1 (Olympic Toán Canada 2009). Cho n≥ 4 điểm trong mặt phẳng, trong đó 3 điểm bất kỳ luôn có thể phủ kín bởi một hình tròn bán kính bằng đơn vị. Chứng minh rằng có hình tròn bán kính bằng đơn vị phủ kín cả n điểm này. Lời giải. Xét hình tròn bán kính 1 có tâm là n điểm đã cho. Điều kiện " 3 điểm bất kỳ luôn có thể phủ kín bởi một hình tròn bán kính 1" tương đương với điều kiện "3 đường tròn bất kỳ kể trên luôn có giao khác rỗng" (chúng có ít nhất 1 điểm chung là tâm của hình tròn phủ 3 điểm đó). Theo định lý Helly n đường tròn kể trên có giao khác rỗng hay có hình tròn bán kính 1 phủ kín cả n điểm ban đầu. Bài toán 2 (Olympic Toán Canada 2003). Trên đường thẳng có 2k − 1 đoạn thẳng màu trắng và 2k − 1 đoạn thẳng màu đen sao cho mỗi đoạn thẳng cắt tại ít nhất k đoạn thẳng khác màu. Chứng minh rằng có đoạn thẳng màu trắng cắt tất cả các đoạn thẳng màu đen và có đoạn thẳng màu đen cắt tất cả các đoạn thẳng màu trắng. Lời giải. Ta chứng minh có đoạn thẳng có màu đen cắt tất cả các đoạn thẳng màu trắng. Với mỗi đoạn thẳng màu trắng cho trước ta xây dựng một tập lồi là đoạn thẳng được tạo thành bằng cách lấy hợp của đoạn thẳng đó với tất cả các đoạn thẳng màu đen có giao với nó. Mỗi tập lồi như vậy gồm ít nhất k đoạn thẳng màu đen và do ta có tổng cộng 2k − 1 đoạn thẳng màu đen nên hai tập lồi bất kỳ như vậy chắc chắn có đoạn thẳng màu đen chung. Do đó theo định lý Helly tất cả các tập lồi đó có đoạn thẳng màu đen chung. Đây chính là đoạn thẳng màu đen cần tìm. Hoàn toàn tương tự ta có đoạn thẳng màu trắng cắt tất cả các đoạn thẳng màu đen. Bài toán 3 (Olympic Toán Iran 2006). Trên bầu trời đêm có hữu hạn ngôi sao . Mỗi ngôi sao tỏa sáng trong một khoảng thời gian nhất định. Biết rằng với k > 1 ngôi sao, có ít nhất hai ngôi sao tỏa sáng cùng một thời điểm. Chứng minh rằng có thể chụp k − 1 bức ảnh về bầu trời sao cho mỗi ngôi sao tảo sáng ít nhất một bức ảnh. 209
Hội thảo khoa học, Hưng Yên 25-26/02/2017 Lời giải. Ta chứng minh bằng quy nạp theo k. Với k = 2, bài toán đúng theo định lý Helly. Giả sử ta đã có khẳng định với k ≥ 2, ta sẽ chứng minh khẳng định với k + 1. Thật vậy trong tất cả các đoạn kể trên, chọn đoạn In = [ an , bn ] sao cho an lớn nhất. Chọn một điểm là an . Khi đó tất cả các đoạn có giao với In đều chứa an . Bỏ tất cả các đoạn này đi và xét các đoạn còn lại. Nếu trong các đoạn còn lại có k đoạn đôi một không giao nhau, mâu thuẫn. Do đó với k đoạn bất kỳ trong các đoạn còn lại này luôn có hai đoạn giao nhau. Từ đó theo quy nạp ta có thể xác định k − 1 điểm sao cho mỗi đoạn trong các đoạn còn lại này chứa ít nhất một điểm trong đó. Cộng thêm điểm an ta có k điểm cần tìm. Bài toán 4 (Chọn đội tuyển Iran thi Olympic Toán Quốc tế 2002). Cho một đường cong kín trên một mặt cầu đơn vị sao cho mỗi đường tròn lớn đều có giao điểm với đường cong đó. Chứng minh rằng đường cong đó có độ dài ít nhất là 2π. Lời giải. Ta biết nếu 4 điểm bất kỳ của đường cong luôn nằm trong một nửa không gian tạo bởi mặt phẳng qua tâm cầu thì toàn bộ đường cong cũng sẽ nằm trong một nửa không gian tạo bởi mặt phẳng qua tâm cầu, mâu thuẫn. Do đó sẽ tồn tại 4 điểm A, B, C, D trên đường cong sao cho tâm cầu O nằm trong khối tứ diện ABCD. Phần đường cong nối 2 điểm A, B có độ dài nhỏ nhất là cung tròn AB. Khi đó đường cong kín ban đầu có độ dài nhỏ nhất là tổng độ dài các cung tròn AB, BC, CD, DA. Gọi D’ là điểm đối xứng tâm của D. Khi đó D’ sẽ nằm trong chỏm cầu giới hạn bởi các đường tròn ngoại tiếp tam giác ABC. Dễ dàng chứng minh được AB+ c BC c ≥ AD d0 + D d 0C Do đó AB+ c BC+c CD+ d DA d ≥ ADd0 + D d0 C + CD d + DA d = 2π. Bài toán 5. Trong mặt phẳng cho k điểm x1 , x2 , . . . , xk . Chứng minh rằng tồn tại điểm x0 với tính chất sau: Từ mỗi bên của đường thẳng bất kì l đi qua x0 chứa ít nhất một phần ba số điểm đã cho (ở đây ta tính cả những điểm nằm trên đường thẳng l). Lời giải. Ta xét tất cả những nửa mặt phẳng đóng H, trong nó chứa hơn hai phần ba số điểm đã cho. Những mặt phẳng như vậy tồn tại, ví dụ như những mặt phẳng chứa toàn bộ các điểm đã cho. Ta sẽ chứng minh rằng mọi cặp ba nửa mặt phẳng này có điểm chung. ta sử dụng định lí Helly cho vô hạn những tập lồi, ta tìm được điểm x0 chung cho tất cả các nửa mặt phẳng. Sau đó, khẳng định x0 có tính chất được mô tả trong điều kiện của bài toán. Cho Hi , i = 1, 2, 3 là ba nửa mặt phẳng trong mặt phẳng mà mỗi nửa mặt phẳng chứa số 2 điểm Si > k trong số điểm đã cho. Kí hiệu s là số điểm trong H1 ∩ H2 . Khi đó, số lượng 3 điểm nằm trong H1 ∪ H2 là s1 + s2 − s (vì số lượng điểm trong phần chung H1 ∩ H2 được 2 2 4 đếm hai lần). Ta có bất đẳng thức s1 > k, s2 > k. Ta nhận được k ≥ s1 + s2 − s > k − s, 3 3 3 1 2 nghĩa là s > k. Bởi vì mặt phẳng thứ ba H3 chứa s3 > k điểm, nên ít nhất một trong 3 3 những điểm nằm trong H1 ∩ H2 sẽ nằm trong H3 (nếu ngược lại thì số lượng điểm đã cho thực sự lớn hơn k). Suy ra x0 có thể áp dụng định Helly: Tồn tại điểm x0 nằm trên 2 tất cả nửa mặt phẳng mà nó chứa hơn số điểm đã cho. Cho l0 là đường thẳng bất kì đi 3 210
Hội thảo khoa học, Hưng Yên 25-26/02/2017 k qua x0 . Ta sẽ chứng minh rằng mỗi nửa mặt phẳng do l0 chia ra chứa ít nhất số điểm. 3 Thật vậy, giả sử ngược lại và ta kí hiệu H là nửa mặt phẳng cùng với đường thẳng l0 mà k nó chứa ít hơn số điểm. 3 Bài toán 6. Cho tập lồi A trong mặt phẳng và họ gồm k > 3 những nửa mặt phẳng phủ A. Chứng minh rằng tồn tại một họ con gồm ba nửa mặt phẳng mà chúng cũng phủ A. Lời giải. Cho H1 , H2 , . . . , Hk là những nửa mặt phẳng mà chúng phủ A (nghĩa là mỗi điểm của A nằm trong một tập nào đó trong Hi , i = 1, 2, . . . , k). Ta giả sử rằng không một bộ ba nửa mặt phẳng nào phủ được A và ta xét những tập hợp A1 , A2 , . . . , Ak , ở đây Ai , i = 1, 2, . . . , k nhận được từ A và bỏ đi những điểm thuộc mặt phẳng Hi Những tập hợp Ai là lồi. Ta sẽ chứng minh rằng mỗi bộ ba tập hợp trong chúng có điểm chung và áp dụng định lí Helly. Ta khẳng định A1 , A2 , A3 có điểm chung. Bởi vì, theo giả thiết phản chứng, những nửa mặt phẳng H1 , H2 , H3 không phủ A, sẽ tìm được một điểm x0 thuộc A không chứa trong bất cứ tập nào của H1 , H2 , H3 . Nghĩa là điểm x0 chung cho A1 , A2 , A3 . Ta áp dụng định lí Helly và tìm được điểm y0 chung cho tất cả các tập hợp Ai , i = 1, 2, . . . , k. Suy ra điểm y0 tuy nằm trong A nhưng không nằm trong bất cứ tập nào của H1 , H2 , . . . , Hk . Ta nhận được sự vô lí với giả thiết đã cho. Do đó, bài toán đã được giải quyết. Bài toán 7. Cho một số hữu hạn các đường thẳng (n ≥ 4). Biết rằng với ba đường thẳng tùy ý luôn tồn tại hình tròn có bán kính R và 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 đó. Lời giải. 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, 211
Hội thảo khoa học, Hưng Yên 25-26/02/2017 với mọi i, j, k ∈ 1, 2, 3, . . . , n ta luôn có Fi ∩ Fj ∩ Fk 6= ∅ (vì với mọi i, j, k luôn tồn tại một hình tròn cắt cả di , d j , dk ). Theo định lí Helly suy ra: F1 ∩ F2 ∩ · · · ∩ Fn 6= ∅. 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. Bài toán 8. Trên mặt phẳng cho n hình tròn (n ≥ 4). Giả sử cứ với mỗi ba hình tròn đều có một hình tròn bán kính r cắt cả ba hình tròn này. Chứng minh rằng tồn tại một hình tròn bán kính r cắt cả n hình tròn. Lời giải. Gọi Si là hình tròn tâm Ai , bán kính ri (i = 1, n, ) Si = ( Ai ; ri ). Gọi ωi là hình tròn tâm Ai , bán kính ri + r (i = 1, n), ωi = ( Ai ; ri + r ). Như vậy tâm của tất cả các hình tròn có bán kính r mà cắt Si đều nằm trong ωi . Xét n tập hợp lồi ω1 , ω2 , . . . , ωn . Với i, j, k tùy ý mà i, j, k ∈ 1, 2, 3, . . . , n. Theo giả thiết tồn tại hình tròn (Oi,j,k ; r ) cắt cả Si , S j , Sk , tức là Oi,j,k ∈ ωi ∩ ω j ∩ ωk . Điều đó chứng tỏ rằng ωi ∩ ω j ∩ ωk 6= ∅ với mọi i, j, k ∈ 1, 2, 3, . . . , n. Theo định lí Helly suy ra in=1 ωi 6= ∅. Vậy tồn tại O∗ ∈ in=1 ωi . T T Xét hình tròn tâm O∗ và bán kính r, (O∗ , r ). Hình tròn này rõ ràng cắt Si với mọi i = 1, n. Bài toán được chứng minh. 212
Hội thảo khoa học, Hưng Yên 25-26/02/2017 3 Bài tập tương tự Bài 1. Trên mặt bàn hình chữ nhật có các hình vuông bằng nhau và có các cạnh song song với cạnh bàn sao cho với k hình vuông bất kỳ luôn tồn tại hai hình vuông có thể đóng chặt vào bàn chỉ bàng một chiếc đinh. Chứng minh rằng có thể đóng chặt tất cả các hình vuông vào bàn bằng 2k − 3 chiếc đinh. Bài 2. n nửa mặt phẳng nằm trên một mặt phẳng. Chứng minh rằng nếu mọi bộ ba nửa mặt phẳng có điểm chung, thì tồn tại một điểm chung cho n nửa mặt phẳng này. Bài 3. Chứng minh định lí Helly cho n đa giác lồi trên mặt phẳng bằng cách áp dụng bài tập 2. 1 Bài 4. Trên đường tròn cho n cung, mỗi cung có độ dài nhỏ hơn cung của đường tròn. 3 Chứng minh rằng nếu mọi cặp hai cung đã cho có điểm chung thì tất cả các cung có điểm chung. Bài 5. không gian cho n điểm A1 , A2 , A3 , . . . , An khoảng cách giữa hai điểm không vượt quá √ 1. Chứng minh rằng tất cả những điểm này có thể phủ bởi hình cầu có bán kính bằng 6 . 4 Bài 6. Cho hữu hạn điểm trên mặt phẳng sao cho nếu vẽ một hình tròn bán kính đơn vị có tâm là một điểm tùy ý trong đó thì hình tròn này sẽ chứa nhiều hơn một nửa các điểm còn lại. Hình tròn có bán kính nhỏ nhất là bao nhiêu có thể chứa tất cả các điểm đã cho (hình tròn này không nhất thiết phải có tâm là một trong số các điểm kể trên)? Bài 7. Trên đường thẳng có 2k + 1 đoạn thẳng sao cho mỗi đoạn thẳng cắt ít nhất k đoạn thẳng khác. Chứng minh rằng: Tồn tại đoạn thẳng cắt tất cả các đoạn thẳng còn lại. Bài 8. (Định lí điểm trung tâm) Một điểm O được gọi là điểm trung tâm của hệ n điểm n trong mặt phẳng nếu mỗi nửa mặt phẳng đóng chứa O đều chứa ít nhất điểm của hệ 3 đã cho (O có thể không thuộc hệ điểm). Chứng minh rằng mọi hệ n điểm trong mặt phẳng đều có ít nhất một điểm trung tâm. Bài 9. Trên đường tròn cho hữu hạn cung tròn có số đo nhỏ hơn 180◦ sao cho hai cung bất kỳ luôn có điểm chung. Chứng minh rằng: Tồn tại đường thẳng đi qua tâm đường tròn cắt tất cả các cung đã cho. Bài 10. Chứng minh rằng: Với mọi đa giác lồi cho trước luôn tồn tại một điểm O trong đa giác sao cho với mỗi đường thẳng tùy ý qua O cắt biên của đa giác tại A và B ta luôn 1 OA có 6 6 2. 2 OB Tài liệu [1] Phan Huy Khải (2007), Các bài toán hình học tổ hợp,, NXB GD. [2] Nguyễn Hữu Điển (2005), Một số chuyên đề hình học tổ hợp, NXB GD. [3] G. Polya (1997), Sáng tạo toán học, NXB GD. [4] V.N.Sachkov (2004), Nhập môn các phương pháp tổ hợp của toán rời rạc, NXB MCCME . [5] Đoàn Quỳnh( chủ biên) (2012), Tài liệu chuyên toán hình học 12, NXB GD. 213