XVIII OM - III - Zadanie 3

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Na sali znajduje się 100 osób, z których każda zna co najmniej 67 innych. Dowieść, że jest na tej sali taka czwórka osób, w której każde dwie osoby się znają. Zakładamy, że jeśli osoba $A$ zna osobę $B$ , to również osoba $B$ zna osobę $A$ .

Rozwiązanie

W zbiorze $M$ osób znajdujących się na sali są co najwyżej $32$ osoby nie znające jakiejś określonej osoby $A$ (przyjmujemy, że osoba $A$ zna sama siebie).

Jeżeli $A$ , $B$ , $C$ są trzema dowolnymi osobami zbioru $M$ , to w zbiorze $M$ jest taka osoba $D$ , różna od $A$ , $B$ i $C$ która zna te trzy osoby. Istotnie, jeśli z sali wyjdą wszystkie osoby nie znające $A$ , wszystkie osoby nie znające $B$ oraz wszystkie osoby nie znające $C$ , to wyjdzie razem co najwyżej $3 \cdot 32 = 96$ osób. Każda z pozostałych osób zna wówczas $A$ , $B$ i $C$ , a ponieważ tych osób jest co najmniej $100-96 = 4$ , więc co najmniej jedna z nich jest różna od $A$ , $B$ i $C$

Czwórkę osób zbioru $M$ znających się wzajemnie możemy wobec tego wyszukać w prosty sposób. Mianowicie $A$ może być którąkolwiek osobą tego zbioru, $B$ osobą znającą $A$ i różną od $A$ , $C$ osobą znającą $A$ i $B$ , a różną od $A$ i od $B$ , wreszcie $D$ osobą znającą $A$ , $B$ i $C$ , różną od $A$ , od $B$ i od $C$ .

Uwaga. W analogiczny sposób można udowodnić twierdzenie ogólniejsze: Jeżeli na sali znajduje się $n$ osób, z których każda zna co najmniej $\left[ \frac{2n}{3} \right] +1$ pozostałych osób, to jest na tej sali czwórka osób, w której każde dwie osoby się znają.

Aby tego dowieść, stwierdzamy najpierw, że liczba osób nie znających jakiejś określonej osoby wynosi co najwyżej $n - \left[ \frac{2n}{3} \right] -2$ . Liczba osób nie znających choćby jednej z trzech osób $A$ , $B$ , $C$ wynosi zatem co najwyżej $m = 3n-3 \left[ \frac{2n}{3} \right]-6$ . Ponieważ $\left[ \frac{2n}{3} \right] > \frac{2n}{3} -1$ , więc $3 \left[ \frac{2n}{3} \right] > 2n - 3$ , wobec czego $3 \left[ \frac{2n}{3} \right] \geq 2n-2$ , zatem $m \leq 3n - (2n-2) - 6 = n-4$ . Liczba osób znających $A$ , $B$ , $C$ jest więc co najmniej równa $n-m \geq 4$ , zatem co najmniej jedna z tych osób jest różna od $A$ , od $B$ i od $C$ Dalszy ciąg dowodu pozostaje ten sam co poprzednio.