Komentarz

XXX OM - I - Zadanie 2

Na płaszczyźnie danych jest $ n $ punktów ($ n > 4 $), z których żadne trzy nie są współliniowe. Udowodnić, że istnieje co najmniej $ \binom{n-3}{2} $ czworokątów wypukłych, których wierzchołkami są pewne z danych punktów.

Rozwiązanie

Jeżeli czworokąt nie jest wypukły, to w każdej parze jego boków przeciwległych istnieje taki bok, że prosta go zawierająca przecina drugi bok pary. Wobec tego, jeżeli w pewnym czworokącie istnieje taka para boków przeciwległych, że żadna prosta zawierająca jeden z tych boków nie przecina drugiego, to czworokąt jest wypukły.

Istnieje wielokąt wypukły $ W $ zawierający wszystkie dane punkty, którego wierzchołkami są pewne z danych punktów. Niech $ A $, $ B $, $ C $ będą ustalonymi wierzchołkami tego wielokąta. Jeżeli $ D $ i $ E $ też są pewnymi z danych punktów różnymi od $ A $, $ B $, i $ C $, to prosta $ DE $ nie zawiera żadnego z punktów $ A $, $ B $, $ C $, a więc nie przecina co najmniej jednego z boków trójkąta $ ABC $. Niech na przykład prosta $ DE $ nie przecina boku $ \overline{BC} $. Gdyby prosta $ BC $ przecinała odcinek $ \overline{DE} $, to punkt przecięcia należałby do wielokąta $ W $, ponieważ odcinek $ \overline{DE} $ jest zawarty w $ W $. Zatem ten punkt przecięcia należałby do odcinka $ \overline{BC} $, ponieważ $ W \cap BC = \overline{BC} $. Jest to niemożliwe, ponieważ prosta $ DE $ nie przecina boku $ \overline{BC} $. Zatem prosta $ BC $ nie przecina odcinka $ \overline{DE} $. Z początkowej uwagi wynika więc, że czworokąt $ BCDE $ lub $ BCED $ jest wypukły.

Dowiedliśmy w ten sposób, że każde dwa z danych punktów różne od $ A $, $ B $ i $ C $ wraz z pewnymi dwoma punktami z punktów $ A $, $ B $, $ C $ tworzą czworokąt wypukły. Różnym parom odpowiadają oczywiście różne czworokąty. Wobec tego liczba czworokątów wypukłych o wierzchołkach w zbiorze danych $ n $ punktów jest nie mniejsza od liczby par danych punktów różnych od $ A $, $ B $ i $ C $. Liczba takich par jest równa $ \binom{n-3}{2} $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz