LV OM - II - Zadanie 6

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:

  1. $ 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.

  2. $ 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.

  3. $ 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.

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

Komentarze

Dodaj nową odpowiedź