Opublikowane na Archiwum Olimpiady Matematycznej (https://archom.ptm.org.pl)

LV OM - II - Zadanie 6

Zawody matematyczne:

LV OM, 2003-2004

Etap:

II

Na przyjęciu spotkało się $n$ osób $(n \geq 5)$ . Wiadomo, że wśród dowolnych trzech osób pewne dwie znają się. Dowieść, że spośród uczestników przyjęcia można wybrać nie mniej niż $n/2$ osób i posadzić przy okrągłym stole tak, aby każdy siedział między dwoma swoimi znajomymi.

Rozwiązanie

Oznaczmy przez $X$ zbiór osób obecnych na przyjęciu. Niech $k$ będzie największą liczbą naturalną o własności: Istnieje $k$ osób $A_1,A_2,\ldots,A_k$ takich, że dla $i = 1,2,\ldots,k-1$ osoby $A_i$ oraz $A_{i+1}$ znają się. Oznaczmy:

$<br /> S = X\setminus\{A_1,A_2,\ldots,A_k \}.<br />$

W dalszym ciągu rozwiązania rozpatrzymy trzy przypadki:

$k \leq n/2$ . Wówczas zbiór $S$ liczy co najmniej $n/2$ osób. Osoba $A_k$ nie zna żadnej osoby ze zbioru $S$ , więc każde dwie osoby w tym zbiorze muszą się znać. Jeśli osoby te usiądą dowolnie przy okrągłym stole, to każda z nich będzie siedzieć obok dwóch swoich znajomych.
$n/2 <k \leq n - 1$ . Wówczas zbiór $S$ jest niepusty i żadna osoba z tego zbioru nie zna ani $A_1$ , ani $A_k$ . Stąd wynika, że osoby $A_1$ i $A_k$ się znają. Zatem osoby $A_1 , A_2, \ldots , A_k$ można posadzić przy okrągłym stole zgodnie z warunkami opisanymi w treści zadania.
$k = n$ . Niech $\ell =[(n+1)/2]$ . Wiemy, że wśród osób $A_1$ , $A_\ell$ , $A_n$ pewne dwie się znają. Stąd wynika, że osoby należące do co najmniej jednego spośród zbiorów

$<br /> \{A_1,A_2,\ldots,A_\ell\},\ \{A_\ell,A_{\ell+1} ,\ldots,A_n\},\ \{A_1,A_2,\ldots,A_n\}<br />$

mogą usiąść przy okrągłym stole zgodnie z warunkami zadania. Pozostaje zauważyć, że każdy z tych trzech zbiorów liczy co najmniej n/2 osób.

Adres źródła: https://archom.ptm.org.pl/?q=node/286