XIX OM - III - Zadanie 6

Dany jest zbiór $ n > 3 $ punktów, z których żadne trzy nie są współliniowe, oraz liczba naturalna $ k < n $. Udowodnić twierdzenia:
1. Jeżeli $ k \leq \frac{n}{2} $, to każdy punkt danego zbioru można połączyć z co najmniej $ k $ innymi punktami zbioru w taki sposób, że wśród poprowadzonych odcinków nie ma trzech boków tego samego trójkąta.
2. Jeżeli $ k > \frac{n}{2} $ i każdy punkt danego zbioru jest połączony z $ k $ innymi punktami zbioru, to wśród poprowadzonych odcinków są trzy boki tego samego trójkąta.

Rozwiązanie

$ 1^\circ $. Załóżmy, że $ k \leq \frac{n}{2} $. Wybierzmy z danego zbioru $ Z $ część $ Z_1 $ składającą się z $ \left[ \frac{n}{2} \right] $ punktów*); część pozostała $ Z_2 $ zawiera $ \left[ \frac{n}{2} \right] $ punktów, gdy $ n $ jest parzyste, a $ \left[ \frac{n}{2} \right]+ 1 $ punktów, gdy $ n $ jest nieparzyste. Ponieważ $ k $ jest liczbą całkowitą, więc z warunku, że $ k \leq \frac{n}{2} $ wynika, że $ k \leq \left[ \frac{n}{2} \right] $. Zatem każdy ze zbiorów $ Z_1 $, $ Z_2 $ zawiera co najmniej $ k $ punktów.

Połączmy odcinkami każdy punkt zbioru $ Z_1 $ z każdym punktem zbioru $ Z_2 $. Wówczas każdy punkt zbioru $ Z $ zostanie połączony z co najmniej $ k $ innymi punktami tego zbioru. Żadne trzy z poprowadzonych odcinków nie są bokami tego samego trójkąta, gdyby bowiem taki trójkąt istniał, wtedy dwa jego wierzchołki, tj. oba końce jednego z odcinków, leżałyby w jednym ze zbiorów $ Z_1 $, $ Z_2 $, co jest niemożliwe, gdyż żaden taki odcinek nie został poprowadzony.

$ 2^\circ $ Załóżmy, że $ k > \frac{n}{2} $ i że każdy punkt danego zbioru łączy $ k $ odcinków z $ k $ innymi punktami zbioru; niech $ AB $ będzie jednym z poprowadzonych odcinków.

Z każdego z punktów $ A $ i $ B $ wychodzi oprócz $ AB $ jeszcze $ k - 1 $ innych odcinków, czyli razem $ 2k - 2 $ odcinków, których końce należą do zbioru pozostałych $ n - 2 $ punktów. Lecz jeśli $ k > \frac{n}{2} $, to $ 2k - 2 > n - 2 $; wśród owych $ 2k - 2 $ odcinków istnieją więc dwa odcinki o wspólnym końcu $ C $. W zbiorze poprowadzonych odcinków znajdują się zatem boki $ AB $, $ AC $ i $ BC $ trójkąta $ ABC $.

Uwaga. W podobny sposób można udowodnić twierdzenie ogólniejsze. Niech będą dane: zbiór $ Z $ złożony z $ n > 3 $ punktów, z których żadne trzy nie są współliniowe, liczba naturalna $ p $ spełniająca nierówności $ 3 \leq p < n $ oraz liczba naturalna $ k < n $. Wtedy:

$ 1 ^\circ $ Jeżeli $ k \leq \frac{p-2}{p-1}n $, wtedy każdy z punktów zbioru $ Z $ można tak połączyć odcinkami z co najmniej $ k $ innymi punktami tego zbioru, że w każdym podzbiorze zbioru $ Z $ złożonym z $ p $ punktów któreś dwa punkty nie są połączone odcinkiem.

$ 2^\circ $ Jeżeli $ k > \frac{p-2}{p-1}n $ i każdy punkt zbioru $ Z $ jest połączony odcinkiem z $ k $ innymi punktami tego zbioru, wtedy istnieje taki podzbiór zbioru $ Z $ złożony z $ p $ punktów, w którym każde dwa punkty są połączone odcinkiem.

Komentarze

Dodaj nową odpowiedź