Matematyka.pl

Udowodnić, że jeśli \(\displaystyle{ n \geq 5}\) osób jest przy okrągłym stole, to można ich tak pozamieniać miejscami, aby każdy miał innego sąsiada niż poprzednio.

Dla \(\displaystyle{ n=5}\) przestawieniem układu ABCDE(A) spełniającym założenie jest choćby ACEBD(A).
Dla \(\displaystyle{ n=6}\) z układu ABCDEF(A) zabieram osobę F i wykorzystuję przestawienie dla \(\displaystyle{ n=5}\). Osobę F wstawiam w miejsce spełniające założenie dostając układ ACEBFD(A).
Dla \(\displaystyle{ n=7}\) z układu ABCDEFG(A) zabieram osobę G i wykorzystuję przestawienie dla \(\displaystyle{ n=6}\). Przy 6 odstępach miedzy osobami w najwyżej cztery (przy pierwotnych sąsiadach G) nie można wstawić G.
....
Dla \(\displaystyle{ n=k \wedge k \in \NN \setminus \left\{ 0,1,2,3,4,5,6\right\} }\) z układu zabieram osobę \(\displaystyle{ K}\) i wykorzystuję przestawienie dla \(\displaystyle{ n=k-1}\). Przy \(\displaystyle{ k-1}\) odstępach miedzy osobami w najwyżej cztery nie można wstawić osobę K.

Dla \(\displaystyle{ n > 6}\) mamy \(\displaystyle{ \varphi(n) > 2}\). Można zatem wziąć liczbę \(\displaystyle{ k \in \{ 1, 2, \ldots, n-1 \}}\) różną od \(\displaystyle{ 1}\) i \(\displaystyle{ n-1}\) oraz względnie pierwszą z \(\displaystyle{ n}\), i brać co \(\displaystyle{ k}\)-tą osobę.