XIX OM - III - Zadanie 5

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ść.

Komentarze

Dodaj nową odpowiedź