XVIII OM - II - Zadanie 2

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

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

$ 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] $

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

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

Mianowicie

$ \textrm{gdy } n = 3k, \textrm{ to } \left[ \frac{n+1}{3} \right] = k,\ \left[ \frac{2n}{3} \right] = \left[ \frac{6k}{3} \right] = 2k, $

$ \textrm{gdy } n = 3k+1, \textrm{ to } \left[ \frac{n+1}{3} \right] = \left[ \frac{3k+2}{3} \right] = k,\ \left[ \frac{2n}{3} \right] = \left[ \frac{6k+2}{3} \right] = 2k, $

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

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