XVIII OM - II - Zadanie 2

Na sali znajduje się 100 osób, z których każda zna co najmniej 66 spośród pozostałych 99 osób. Dowieść, iż jest możliwe, że w każdej czwórce tych osób są takie dwie, które się nie znają. Przyjmujemy, że jeśli osoba $ A $ zna osobę $ B $, to również osoba $ B $ zna osobę $ A $.

Rozwiązanie

Oznaczmy osoby znajdujące się na sali literami $ A_1, A_2, \ldots, A_{100} $. Niech $ M $ oznacza zbiór osób $ \{A_1, A_2, \ldots, A_{33}\} $, $ N $ - zbiór osób $ \{A_{34}, A_{35}, \ldots, A_{66}\} $ i $ P $ - zbiór osób $ \{A_{67}, A_{68}, \ldots, A_{100} \} $. Przypadek, o którym mowa w zadaniu, zachodzi na przykład wtedy, gdy każda osoba zbioru $ M $ zna te i tylko te osoby, które należą do zbioru $ N $ lub do zbioru $ P $ (razem $ 67 $ osób), i podobnie każda osoba zbioru $ N $ zna wszystkie osoby zbiorów $ P $ i $ M $ i tylko te osoby ($ 67 $ osób), a każda osoba zbioru $ P $ zna wszystkie osoby zbiorów $ M $ i $ N $ i tylko te osoby ($ 66 $ osób). Jeśli bowiem ($ A_i, A_j, A_k, A_l $) jest jakąkolwiek czwórką danych osób, to któreś dwie z nich znajdują się w jednym i tym samym ze zbiorów $ M $, $ N $, $ P $, a wobec tęgo osoby te się nie znają.

Uwaga. Twierdzenie powyższe łatwo uogólnić. Załóżmy, że na sali znajduje się $ N $ osób, z których każda zna co najmniej $ \left[ \frac{2n}{3} \right] $ pozostałych osób. Może się wówczas zdarzyć, że w każdej czwórce tych osób są dwie takie, które się nie znają. Aby to udowodnić podzielmy zbiór $ M $ wszystkich osób na $ 3 $ zbiory $ M_1 $, $ M_2 $, $ M_3 $ zawierające odpowiednio $ m_1 = \left[ \frac{n+1}{3} \right] $ , $ m_2 = \left[ \frac{n+1}{3} \right] $ oraz $ m_3 = n - 2 \left[ \frac{n+1}{3} \right] $ osób. Jeżeli każda osoba zbioru $ M_i $ zna osoby zbiorów $ M_j $ i $ M_k $ ($ i, j, k = 1, 2, 3;\ i \ne j \ne k \ne i $) i tylko te osoby, to w każdej czwórce osób zbioru $ M $ są takie dwie osoby, które należą do tego samego zbioru $ M_i $, więc się nie znają. Każda zaś osoba zbioru $ M $ zna wtedy co najmniej $ \left[ \frac{2n}{3} \right] $ osób. Albowiem

\[<br /> m_1 + m_2 = \left[ \frac{n+1}{3} \right] + \left[ \frac{n+1}{3} \right] = 2 \left[ \frac{n+1}{3} \right] \geq \left[ \frac{2n}{3} \right]<br /> \]
\[<br /> m_1 + m_3 = m_2 + m_3 = n- \left[ \frac{n+1}{3} \right] \geq<br /> \left[ \frac{2n}{3} \right],<br /> \]

co najłatwiej stwierdzić oddzielnie dla każdego z trzech możliwych przypadków: $ n = 3k $, $ n = 3k+1 $, $ n= 3k + 2 $.

Mianowicie

\[<br /> \textrm{gdy } n = 3k, \textrm{ to }<br /> \left[ \frac{n+1}{3} \right] = k,\<br /> \left[ \frac{2n}{3} \right] = \left[ \frac{6k}{3} \right] = 2k,<br /> \]
\[<br /> \textrm{gdy } n = 3k+1, \textrm{ to }<br /> \left[ \frac{n+1}{3} \right] = \left[ \frac{3k+2}{3} \right] = k,\<br /> \left[ \frac{2n}{3} \right] = \left[ \frac{6k+2}{3} \right] = 2k,<br /> \]
\[<br /> \textrm{gdy } n = 3k+2, \textrm{ to }<br /> \left[ \frac{n+1}{3} \right] = \left[ \frac{3k+3}{3} \right] = k+1,\<br /> \left[ \frac{2n}{3} \right] = \left[ \frac{6k+4}{3} \right] = 2k+1,<br /> \]

Widzimy stąd, że podane wyżej nierówności są spełnione dla każdego naturalnego $ n $.

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

Komentarze

Dodaj nową odpowiedź