Przy stole siedzi 7 osób

Ruahyin · Post autor: **Ruahyin** » 2 gru 2016, o 20:35

Przy stole siedzi 7 osób. Wykaż, że mozna przesadzić je tak aby każda osoba miała dwóch sąsiadów innych niz poprzednio.

Yelon · Post autor: **Yelon** » 2 gru 2016, o 20:43

Zakładam, że chodzi o okrągły stół, bo tylko wtedy każda osoba ma dwójkę sąsiadów.

Załóżmy, że osoby które siedzą przy stole ponumerujemy kolejno, czyli mamy

\(\displaystyle{ (1) \ , \ (2) \ , \ (3) \ , \ (4) \ , \ (5) \ , \ (6) \ , \ (7)}\) i oczywiście siódma osoba siedzi przy pierwszej.

Teraz sadasz te osoby w takiej kolejności:

\(\displaystyle{ (1) \ , \ (3) \ , \ (5) \ , \ (2) \ , \ (7) \ , \ (4) \ , \ (6)}\) i szósta osoba siedzi koło pierwszej.

W takim rozsadzeniu każdy ma dwóch nowych sąsiadów.

Ruahyin · Post autor: **Ruahyin** » 2 gru 2016, o 20:48

Yelon, Czyli nie ma żadnego algorytmu na wyznaczenie kolejności w jakiej mają siedzieć tylko trzeba zgadywać?

Yelon · Post autor: **Yelon** » 2 gru 2016, o 20:53

Dla 7 osób, a tyle podałeś, tak było najszybciej

Jeśli to zadanie zmodyfikować "Niech \(\displaystyle{ n}\) osób siedzi przy okrągłym stole...", to już trzeba by pomyśleć.

dec1 · Post autor: **dec1** » 2 gru 2016, o 21:13

Ustawienie dla \(\displaystyle{ n\geq 5}\) osób, osoby ponumerowane \(\displaystyle{ 1, 2, ... , n}\):

dla \(\displaystyle{ n}\) nieparzystego: \(\displaystyle{ 1, 3, ... , n - 2, n, 2, 4, 6, ... , n - 1}\), tak jakby skaczemy po 2 w cyklu.
dla \(\displaystyle{ n}\) parzystego: \(\displaystyle{ 1, 3, ..., n - 1, 2, 4, ..., n - 4, n, n - 2}\), znowu skaczemy po 2, ale zamieniamy dwie ostatnie miejsca zeby nie było połączenia \(\displaystyle{ n, 1}\).

Dla \(\displaystyle{ n\leq 4}\) się nie da.

kinia7 · Post autor: **kinia7** » 3 gru 2016, o 18:13

dec1 pisze:dla \(\displaystyle{ n}\) nieparzystego: \(\displaystyle{ 1, 3, ... , n - 2, n, 2, 4, 6, ... , n - 1}\), tak jakby skaczemy po 2 w cyklu.

zakładając, że 1 siedzi zawsze na tym samym miejscu a na następnych sami nieparzyści
to nieparzystych możemy uszeregować w dowolny sposób i do nich w prawie dowolnej kolejności dosadzić parzystych
wszystkich takich możliwości jest \(\displaystyle{ \frac{n^3-11n^2+43n-57}{8} \cdot \left( \frac{n-5}{2} \right)! \cdot \left( \frac{n-3}{2} \right)!}\)

\(\displaystyle{ n=5\ \ \ \ \ \rightarrow \ \ \ \ \ \ \ \ 1}\)
\(\displaystyle{ n=7\ \ \ \ \ \rightarrow \ \ \,\ \ \ \ 12}\)
\(\displaystyle{ n=9\ \ \ \ \ \rightarrow \ \ \ \ \ 252}\)
\(\displaystyle{ n=11\ \ \ \rightarrow \ \ \ \ 7488}\)