Komentarz

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.

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

Dodaj komentarz