XLVIII OM - III - Zadanie 6

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

III

Na okręgu o promieniu $1$ leży $n$ różnych punktów ( $n \geq 2$ ). Niech $q$ będzie liczbą odcinków o końcach w tych punktach i długości większej niż $\sqrt{2}$ . Dowieść, że $3q \leq n^2$ .

Rozwiązanie

Odcinek o końcach w rozważanym zbiorze będziemy nazywać długim, jeśli jego długość jest większa niż $\sqrt{2}$ , a krótkim w przeciwnym przypadku. Tak więc $q$ jest liczbą długich odcinków. W dany okrąg wpisujemy kwadrat $ABCD$ tak, by żaden z danych $n$ punktów nie był jego wierzchołkiem. Przyjmijmy, że na łukach $AB$ , $BC$ , $CD$ , $DA$ leży odpowiednio $a$ punktów, $b$ punktów, $c$ punktów, $d$ punktów. Weźmy pod uwagę zbiór wszystkich czworokątów mających wierzchołki w danych punktach, po jednym na każdym z czterech łuków. Jest $abcd$ takich czworokątów. Każdy czworokąt wpisany w dany okrąg ma co najmniej jeden bok krótki.

Przyporządkujmy każdemu czworokątowi (z rozważanego zbioru) jeden z jego krótkich boków i pomalujmy ten wybrany bok na zielono. Ustalony zielony odcinek mający końce na łukach $AB$ i $BC$ mógł zostać przyporządkowany co najwyżej $c \cdot d$ czworokątom, a więc co najwyżej $m$ czworokątom, gdzie $m$ jest największą z liczb $ab$ , $bc$ , $cd$ , $da$ . Tak samo da się oszacować liczbę czworokątów, którym został przyporządkowany dowolnie ustalony zielony odcinek (o końcach w którychkolwiek dwóch sąsiednich łukach). Stąd wniosek, że łączna liczba zielonych odcinków jest nie mniejsza niż $(abcd)/m$ .

Wszystkie zielone odcinki są krótkie. Oczywiście takie wszystkie odcinki mające oba końce w jednym łuku są krótkie. Zatem liczba krótkich odcinków, równa ${n \choose 2} - q$ , spełnia oszacowanie:

$ {n \choose 2}-q\geq \frac{abcd}{m}+{a \choose 2}+{b \choose 2}+{c \choose 2}+{d \choose 2}. $

Można przyjąć (przesuwając w razie potrzeby oznaczenia), że $m = ab$ . Otrzymana nierówność przybiera po przekształceniu postać:

$ \begin{split} q &\leq \frac{1}{2}(n(n - 1) - a(a - 1) - b(b - 1) - c(c - 1) - d(d - 1)) - cd =\\ & = \frac{1}{2}n^2-\frac{1}{2}(a^2+b^2+c^2+d^2)-cd \end{split} $

(skorzystaliśmy z tego, że $a + b + c + d = n$ ). A zatem

$ \begin{split} n^2 - 3q & \geq - \frac{1}{2} n^2 + \frac{3}{2}(a^2 +b^2 + c^2+ d^2) + 3cd =\\ &= \left(\frac{1}{2}(a + b)-(c + d)\right)^2 + \frac{3}{4}(a-b)^2 \geq 0. \end{split} $