XXX OM - I - Zadanie 2

Zawody matematyczne:

XXX OM, 1978-1979

Etap:

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}$ .