Komentarz

XLVIII OM - III - Zadanie 6

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:

\[<br /> {n \choose 2}-q\geq \frac{abcd}{m}+{a \choose 2}+{b \choose 2}+{c \choose 2}+{d \choose 2}.<br /> \]

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

\[<br /> \begin{split}<br /> q &\leq \frac{1}{2}(n(n - 1) - a(a - 1) - b(b - 1) - c(c - 1) - d(d - 1)) - cd =\\<br /> & = \frac{1}{2}n^2-\frac{1}{2}(a^2+b^2+c^2+d^2)-cd<br /> \end{split}<br /> \]

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

\[<br /> \begin{split}<br /> n^2 - 3q & \geq - \frac{1}{2} n^2 + \frac{3}{2}(a^2 +b^2 + c^2+ d^2) + 3cd =\\<br /> &= \left(\frac{1}{2}(a + b)-(c + d)\right)^2 + \frac{3}{4}(a-b)^2 \geq 0.<br /> \end{split}<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz