LVI OM - II - Zadanie 3

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

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

$ 9T^{2}<2K^{3}. $

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

$ (1) \qquad k_{1}+k_{2}+\ldots+k_{m}=2K\ \textrm{oraz}\ t_{1}+t_{2}+\ldots+t_{m}=3T. $

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

$ (2)\qquad t_{i}\leq {{k_i} \choose 2} = \frac{k_{i}^{2}-k_{i}}{2} < \frac{k_{i}^{2}}{2}. $

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

$ (2)\qquad t_{i}\leq K. $

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

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

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