Một bài toán về vị trí của các điểm

26

Một bài toán về vị trí của các điểm

G. A. Tonoyan

Giả sử có $n$ điểm trên mặt phẳng, không có ba điểm nào nằm trên cùng một đường thẳng (chúng ta sẽ chỉ xét những tập hợp điểm như vậy). Rõ ràng là nếu $n \geq 3$, thì chúng ta có thể tìm thấy đa giác lồi *) đơn giản nhất - một hình tam giác - có các đỉnh tại ba trong số các điểm này.

Có phải luôn luôn có thể tìm được một tứ giác lồi có các đỉnh tại các điểm này cho $n > 3$? Nếu $n = 4$ và các điểm là các đỉnh của một tứ giác không lồi, thì điều này sẽ xảy ra. Nếu $n \geq 5$, thì với mọi cách sắp xếp điểm đều có thể tìm được một tứ giác lồi. Thật vậy, nếu bao lồi của tập **) của chúng ta là một $k$-giác, trong đó $k > 3$, thì mọi thứ đều ổn - bốn đỉnh bất kỳ của $k$-giác này đều là các đỉnh của tứ giác cần thiết. Gọi $k = 3$ là bao lồi của tam giác $ABC$. thì có ít nhất hai điểm - $D$ và $E$ - nằm bên trong tam giác này (xem Hình 1). Prima $DE$ không đi qua các đỉnh của tam giác $ABC$. Vì vậy hai trong số

*) Nhớ lại rằng một đa giác được gọi là lồi nếu cùng với hai điểm, nó chứa một đoạn nối chúng.
**) Bao lồi của một tập hợp các điểm trên mặt phẳng là đa giác lồi tối thiểu chứa chúng. Vì giao điểm của hai đa giác lồi là đa giác lồi nên định nghĩa này đúng.

Cơm. 1.

27

Cơm. 2.
quỹ tích của tập hợp $N \setminus K$ - tập hợp thu được bằng cách loại bỏ khỏi $N$ tập con $K$ của nó và qua $M$ - tập hợp $(N \setminus K) \setminus L$.

Chúng ta hãy xem xét các khả năng sau: 1) tập $M$ trống; 2) tập $M$ bao gồm một điểm duy nhất; 3) tập $M$ chứa ít nhất hai điểm.

1. Bộ $M$ trống. Khi đó $N$ chỉ chứa các đỉnh của đa giác $K$ và $L$, tức là có nhiều nhất 8 điểm (vì mỗi đa giác $K$ và $L$ là một hình tam giác hoặc tứ giác).

2. Tập $M$ chứa một điểm duy nhất; hãy biểu thị nó bằng $P$. Nếu $L$ là một tứ giác thì bằng cách vẽ một trong các đường chéo của nó, chúng ta chia nó thành hai hình tam giác; điểm $P$ nằm bên trong một trong số chúng (Hình 3). Chúng ta hãy biểu thị các đỉnh của tam giác này bằng các chữ cái $A, B, C$. Nếu $L$ là một hình tam giác thì chúng ta biểu thị

Cơm. 3.

các đỉnh của nó đi qua $A, B, C$; điểm $P$ nằm bên trong tam giác này.

Trong mọi trường hợp, trong số các đỉnh của đa giác $L$ cũng sẽ tìm thấy ba đỉnh $A, B, C$, sao cho $P$ là điểm trong của tam giác $ABC$.

Chúng ta hãy vẽ các tia $PA, PB, PC$ từ điểm $P$. Họ chia mặt phẳng thành ba góc $APB, BPC, CPA$. Dễ dàng nhận thấy mỗi góc này chứa nhiều nhất một đỉnh của đa giác $K$. Trên thực tế, chẳng hạn, giả sử góc $APB$ chứa hai đỉnh của đa giác $K$, và do đó chứa một số cạnh $RQ$ của đa giác $K$. Khi đó các điểm $A, P, B, Q, R$ là các đỉnh của một hình ngũ giác lồi (Hình 4), điều này là không thể. Do đó $K$ có nhiều nhất ba đỉnh (một đỉnh ở mỗi góc được xem xét). Vì $L$ có tối đa bốn đỉnh và $M$ được giả sử bao gồm một điểm duy nhất $P$, nên tập hợp $N$ chứa tối đa tám điểm.

3. Tập $M$ chứa ít nhất hai điểm. Chúng ta hãy biểu thị bằng $E$ và $F$ hai điểm bất kỳ của tập hợp $M$.

Trước tiên chúng ta giả sử rằng $L$ là một tứ giác. Giả sử rằng $EF$ không đi qua các đỉnh của đa giác $L$ và cắt hai cạnh của nó. Nếu $EF$ cắt hai cạnh liền kề của tứ giác $L$ (Hình 5), thì ba đỉnh $B, C, D$ còn lại của tứ giác $L$, cùng với $E$ và $F$, là các đỉnh của một hình ngũ giác lồi. Do đó, $EF$ cắt nhau

28

thể hiện hai cạnh đối diện của tứ giác $L$.

Ví dụ: để tia $EF$ giao nhau với cạnh $AB$ và tia $FE$ giao nhau với cạnh $CD$ (Hình 6). Hãy vẽ các tia $FA$, $FB$, $EC$ và $ED$. Cùng với đoạn $EF$ họ chia mặt phẳng thành 4 phần. Nếu bên trong góc $AFB$ (là một trong bốn phần này) có hai đỉnh của đa giác $K$, và do đó cũng có cạnh kia $TR$ của đa giác $K$, thì các điểm $A$, $F$, $B$, $T$, $R$ là các đỉnh của một hình ngũ giác lồi (Hình 7). Do đó, bên trong góc $AFB$ có nhiều nhất một đỉnh của đa giác $K$. Tương tự, bên trong góc $CED$ có nhiều nhất một đỉnh của đa giác $K$. Đối với hai phần còn lại, các đỉnh của đa giác $K$ không thể nằm trong đó (nếu không, cùng với các điểm $A$, $F$, $E$, $D$ hoặc $B$, $F$, $E$, $C$, chúng sẽ được hình thành bởi một hình ngũ giác lồi, Hình 6).

Cơm. 5.

Cơm. 6.

Cơm. 7.

hóa ra $K$ có không quá hai đỉnh (mỗi đỉnh nằm trong các góc $AFB$, $CED$), điều này là không thể, vì $K$ là một hình tam giác hoặc một hình tứ giác.

Cuối cùng, giả sử rằng $L$ là một hình tam giác. Hãy sử dụng $EF$ để tách một đỉnh của tam giác này.

Ví dụ: để tia $EF$ giao nhau với cạnh $AB$ và tia $FE$ giao nhau với cạnh $AC$ (Hình 7). Lý luận, như trước đây, chúng ta thấy rằng các góc $AEC$ và $AFB$ chứa không quá một đỉnh của đa giác $K$ và phần mặt phẳng giới hạn bởi các tia $EC$, $FB$ và đoạn $EF$ không chứa bất kỳ đỉnh nào của đa giác $K$.

Vì vậy, giả sử $M$ chứa ít nhất hai điểm dẫn đến mâu thuẫn. Nếu $M$ trống hoặc chứa một điểm thì $N$ có ​​nhiều nhất tất cả các điểm. Điều này hoàn thành việc chứng minh.

Bài tập

1. Chứng minh rằng nếu tất cả các tứ giác có đỉnh tại một số điểm $n$ đều lồi thì $n$ các điểm này là các đỉnh của một $n$-giác lồi.
2. Trên máy bay cho $n$ điểm. Chứng minh rằng có ít nhất $\frac{C_n^3}{n-4}$ tứ giác lồi có đỉnh tại các điểm này.
3. Có vô số điểm trên một mặt phẳng cho trước. Chứng minh rằng với mọi $k$ đều tồn tại một $k$-giác lồi có các đỉnh tại các điểm này.
   (Chúng tôi xin nhắc bạn rằng chỉ những đa giác trong đó không có ba điểm nào nằm trên cùng một đường thẳng mới được xem xét.)