XIX OM - III - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

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.