XIX OM - II - Zadanie 3

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

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

$ (1) \qquad 1, 2, 3, \ldots,n. $

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

$ (2) \qquad 1, 3, \ldots, n, 2, \ldots,n- 1, $

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

$ 1,3,\ldots, n-1, 2,\ldots, n-2, n, $

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

$ (3) \qquad 1,3, \ldots, n-1, 2,\ldots, n, n-2. $

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.