XIX OM - II - Zadanie 3

Dowieść, że jeżeli przy okrągłym stole siedzi co najmniej 5 osób, to można je tak przesadzić, że każda osoba będzie miała obu sąsiadów innych niż poprzednio.

Rozwiązanie

\spos{1} Oznaczmy dane osoby znakami liczb naturalnych od $ 1 $ do $ n $ ($ n \geq 5 $) i załóżmy, że przy stole osoba $ 1 $ sąsiaduje z osobami $ n $ i $ 2 $, osoba $ 2 $ sąsiaduje z osobami $ 1 $ i $ 3 $ itd., wreszcie osoba $ n $ sąsiaduje z osobami $ n- 1 $ i $ 1 $. Powiemy krótko, że liczby od $ 1 $ do $ n $ ustawione są w cykl

\[<br />
(1) \qquad  1, 2, 3, \ldots,n.<br />
\]

Niech $ n $ będzie liczbą nieparzystą. Ustawmy te same liczby w cykl

\[<br />
(2) \qquad  1, 3, \ldots, n, 2, \ldots,n- 1,<br />
\]

w którym występują oddzielnie kolejne liczby nieparzyste i kolejne liczby parzyste. Łatwo stwierdzić, że w cyklu (2) każda liczba sąsiaduje z innymi liczbami, niż w cyklu (1). Mianowicie: $ 1^\circ $ Każda liczba nieparzysta z wyjątkiem $ 1 $ i $ n $ sąsiaduje w cyklu (1) z liczbami parzystymi, a w cyklu (2) z liczbami nieparzystymi; $ 2^\circ $ Każda liczba parzysta z wyjątkiem $ 2 $ i $ n-1 $ sąsiaduje w cyklu (1) z liczbami nieparzystymi, a w cyklu (2) z liczbami parzystymi; $ 3^\circ $ liczba $ 1 $ sąsiaduje w cyklu (1) z liczbami $ n $ i $ 2 $, a w cyklu (2) z liczbami $ n-1 $ i $ 3 $, różnymi od $ n $ i $ 2 $, gdyż $ n \geq 5 $; to samo dotyczy liczb $ n $, $ 2 $ i $ n-1 $.

Przyjmijmy z kolei, że $ n $ jest liczbą parzystą i ustawmy liczby od $ 1 $ do $ n $ w cykl

\[<br />
1,3,\ldots, n-1, 2,\ldots, n-2, n,<br />
\]

w którym, podobnie jak w (2), występują oddzielnie kolejne liczby nieparzyste oraz kolejne liczby parzyste, a następnie przestawmy w nim liczby $ n-2 $ i $ n $:

\[<br />
(3) \qquad  1,3, \ldots, n-1, 2,\ldots, n, n-2.<br />
\]

W cyklu (3) każda liczba sąsiaduje z innymi liczbami niż w cyklu (1), co stwierdzamy zupełnie podobnie jak w przypadku $ n $ nieparzystego.

Komentarze

Dodaj nową odpowiedź