XIX OM - III - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Na płaszczyźnie leży $n$ punktów ( $n \geq 4$ ), z których każde cztery są wierzchołkami czworokąta wypukłego. Dowieść, że wszystkie te punkty są wierzchołkami wielokąta wypukłego.

Rozwiązanie

Zastosujemy metodę indukcji. Gdy $n = 4$ , teza twierdzenia jest prawdziwa. Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego naturalnego $n \geq 4$ , i niech $A_1, A_2, \ldots, A_n, A_{n+1}$ będą takimi $n + 1$ punktami płaszczyzny, że każde cztery z nich są wierzchołkami wielokąta wypukłego. Według założenia indukcyjnego punkty $A_1, A_2, \ldots, A_n$ są wierzchołkami wielokąta wypukłego $W$ . Przyjmiemy, że są to wierzchołki kolejne, co można uzyskać przez odpowiednią numerację punktów. Punkt $A_{n+1}$ nie leży na obwodzie wielokąta $W$ , gdyż żadne trzy dane punkty nie są współliniowe. Nie leży on także wewnątrz wielokąta $W$ , gdyż każdy punkt wewnętrzny wielokąta należy do jednego z trójkątów, na jakie można podzielić wielokąt jego przekątnymi, a punkt $A_{n + 1}$ nie może się znajdować w takim trójkącie. Zatem punkt $A_{n+1}$ leży na zewnątrz wielokąta $W$ . Weźmy pod uwagę kąty wypukłe o wierzchołku $A_{n+1}$ , których ramiona przechodzą przez wierzchołki wielokąta $W$ . Zbiór tych kątów jest skończony, więc istnieje wśród nich kąt największy. Niech to będzie na przykład kąt $\alpha = A_kA_{n + 1}A_l$ . Wewnątrz kąta $\alpha$ leżą wszystkie wierzchołki wielokąta $W$ oprócz $A_k$ i $A_l$ . W trójkącie $T$ o wierzchołkach $A_k$ , $A_{n+1}$ , $A_l$ nie leży żaden z wierzchołków $A_i$ wielokąta $W$ , różnych od $A_k$ i $A_l$ , gdyż punkty $A_i$ , $A_k$ , $A_l$ , $A_{n+1}$ są według założenia wierzchołkami czworokąta wypukłego. Wobec tego $A_k$ i $A_l$ są kolejnymi wierzchołkami wielokąta $W$ , np. $l=k+1$ . W takim razie punkty $A_1, A_2 \ldots A_k, A_{n+1}, A_{k+1}, \ldots, A_n$ są kolejnymi wierzchołkami wielokąta $W_1$ , który składa się z wielokąta $W$ i z trójkąta $T$ .

Dowiedziemy, że wielokąt $W_1$ jest wypukły, tj. że każdy odcinek którego końce leżą w wielokącie $W_1$ zawiera się cały w tym wielokącie. Istotnie, jeżeli punkty $M$ i $N$ leżą w wielokącie $W_1$ , to zachodzi jeden z przypadków: a) Punkty $M$ i $N$ leżą oba w wielokącie wypukłym $W$ , albo oba w trójkącie $T$ ; wtedy cały odcinek $MN$ zawiera się w wielokącie $W$ albo w trójkącie $T$ , a tym samym zawiera się w wielokącie $W_1$ ; b) Jeden z tych punktów, np. punkt $M$ , leży w wielokącie $W$ , a punkt $N$ w trójkącie $T$ . Odcinek $MN$ przecina wtedy obwód trójkąta $T$ w pewnym punkcie $P$ . Punkt $P$ leży na tej części obwodu trójkąta $T$ , która znajduje się w kącie $\alpha$ , tj. na odcinku $A_kA_{k+1}$ . Odcinek $MP$ należy więc do wielokąta $W$ , a odcinek $PN$ - do trójkąta $T$ ; każdy z tych odcinków, zatem także ich suma $MN$ , należy do wielokąta $W_1$ . Dowód indukcyjny twierdzenia został przeprowadzony.

Uwaga. Bardzo prosty dowód twierdzenia uzyskamy opierając się na twierdzeniu następującym:

Dla każdego skończonego zbioru $Z$ punktów płaszczyzny, składającego się z $n \geq 3$ punktów nie leżących na jednej prostej, istnieje taki wielokąt wypukły $W$ , że

1. Zbiór $Z$ jest zawarty w wielokącie $W$ .

2. Każdy wierzchołek wielokąta $W$ należy do zbioru $Z$ .

Taki wielokąt $W$ nazywa się oponą zbioru $Z$ *)

Niech $Z$ będzie zbiorem $n \geq 4$ punktów płaszczyzny, którego każde $4$ punkty są wierzchołkami czworokąta wypukłego i niech wielokąt $W$ będzie oponą zbioru $Z$ . Wówczas każdy punkt zbioru $Z$ jest wierzchołkiem wielokąta $W$ . Albowiem: $1^\circ$ żaden punkt zbioru $Z$ nie leży na obwodzie wielokąta $W$ między dwoma jego wierzchołkami, gdyż w zbiorze $Z$ nie ma trzech punktów współliniowych; $2^\circ$ żaden punkt zbioru $Z$ nie leży wewnątrz wielokąta $W$ , gdyż wówczas leżałby w jednym z trójkątów, na jakie można $W$ podzielić przekątnymi, a to byłoby również sprzeczne z założeniem. Opona $W$ jest zatem tym wielokątem, którego istnienia należało dowieść.