szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 2 gru 2016, o 20:35 
Użytkownik

Posty: 123
Lokalizacja: Yakushima
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 20:43 
Użytkownik
Avatar użytkownika

Posty: 560
Lokalizacja: Kraków
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

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

Teraz sadasz te osoby w takiej kolejności:

(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.
Góra
Kobieta Offline
PostNapisane: 2 gru 2016, o 20:48 
Użytkownik

Posty: 123
Lokalizacja: Yakushima
Yelon, Czyli nie ma żadnego algorytmu na wyznaczenie kolejności w jakiej mają siedzieć tylko trzeba zgadywać?
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 20:53 
Użytkownik
Avatar użytkownika

Posty: 560
Lokalizacja: Kraków
Dla 7 osób, a tyle podałeś, tak było najszybciej :D

Jeśli to zadanie zmodyfikować "Niech n osób siedzi przy okrągłym stole...", to już trzeba by pomyśleć.
Góra
Mężczyzna Offline
PostNapisane: 2 gru 2016, o 21:13 
Użytkownik

Posty: 714
Ustawienie dla n\geq 5 osób, osoby ponumerowane 1, 2, ... , n:

  • dla n nieparzystego: 1, 3, ... , n - 2, n, 2, 4, 6, ... , n - 1, tak jakby skaczemy po 2 w cyklu.
  • dla n parzystego: 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 n, 1.

Dla n\leq 4 się nie da.
Góra
Kobieta Offline
PostNapisane: 3 gru 2016, o 18:13 
Użytkownik
Avatar użytkownika

Posty: 654
Lokalizacja: Wrocław
dec1 napisał(a):
dla n nieparzystego: 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 \frac{n^3-11n^2+43n-57}{8} \cdot \left(  \frac{n-5}{2} \right)! \cdot \left(  \frac{n-3}{2} \right)!

n=5\ \ \ \ \  \rightarrow \ \ \ \ \ \ \ \ 1
n=7\ \ \ \ \  \rightarrow \ \ \,\ \ \ \ 12
n=9\ \ \ \ \  \rightarrow \ \ \ \ \ 252
n=11\ \ \  \rightarrow \ \ \ \ 7488
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kombinatoryka - ustawianie osób przy okrągłym stole  zuza12342  0
 n prezentów n osób, szansa że k dostanie swój prezent  _radek  2
 ola i bolek przy stole  jurczakos  1
 20 osób losowo w szeregu. Osoby A i B nie stoja obok siebi  Konik  8
 Schemat rekurencyjny przy rozkładzie na równanie jednorodne  Revoltbent  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl