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ę.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź