LVI OM - II - Zadanie 3

W przestrzeni danych jest $ n $ punktów ($ n\geq 2 $) z których żadne cztery nie leżą w jednej płaszczyźnie. Niektóre z tych punktów zostały połączone odcinkami. Niech $ K $ będzie liczbą poprowadzonych odcinków ($ K\geq 1 $), a $ T $ liczbą powstałych trójkątów. Udowodnić, że

\[<br />
9T^{2}<2K^{3}.<br />
\]

Rozwiązanie

Ponumerujmy liczbami od 1 do $ m $ te punkty, z których wychodzi co najmniej jeden odcinek i przyjmijmy, że z punktu o numerze $ i $ ($ i=1,2,\ldots,m $) wychodzi dokładnie $ k_i $ odcinków. Wtedy $ k_i>0 $. Oznaczmy ponadto przez $ t_i $ ($ i=1,2,\ldots,m $) liczbę tych trójkątów, których jednym z wierzchołków jest punkt o numerze $ i $ Wówczas

\[<br />
(1) \qquad k_{1}+k_{2}+\ldots+k_{m}=2K\ \textrm{oraz}\ t_{1}+t_{2}+\ldots+t_{m}=3T.<br />
\]

Zbiór $ A_i $ tych punktów, które zostały połączone odcinkiem z punktem o numerze $ i $ zawiera dokładnie $ k_i $ elementów. Ponadto trójkątów mających wierzchołek w punkcie o numerze $ i $ jest tyle samo, ile poprowadzonych odcinków o wierzchołkach w zbiorze $ A_i $. Zatem

\[<br />
(2)\qquad t_{i}\leq {{k_i} \choose 2} = \frac{k_{i}^{2}-k_{i}}{2} < \frac{k_{i}^{2}}{2}.<br />
\]

Z drugiej strony, liczba tych odcinków jest mniejsza niż liczba wszystkich poprowadzonych odcinków. Wobec tego

\[<br />
(2)\qquad t_{i}\leq K.<br />
\]

Mnożąc stronami nierówności (2) i (3) uzyskujemy $ t_i^2< \frac{1}{2}k_i^2K $. Stąd oraz z równości (1) otrzymujemy

\[<br />
3T = \sum_{i=1}^{m}t_{i} < \sum_{i=1}^{m}\frac{k_{i}\cdot\sqrt{K}}{\sqrt{2}} = \frac{\sqrt{K}}{\sqrt{2}}\cdot\sum_{i=1}^{m}k_{i} = \frac{2K\sqrt{K}}{\sqrt{2}}.<br />
\]

Podnosząc ostatnią nierówność stronami do kwadratu dostajemy tezę.

Komentarze

Dodaj nową odpowiedź