XVIII OM - III - Zadanie 3

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.

Komentarze

Dodaj nową odpowiedź