2n drużyn w turnieju gra równolegle, dowód, że się da

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
banias
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 13 wrz 2009, o 11:39
Płeć: Mężczyzna
Lokalizacja: Szczebrzeszyn
Podziękował: 2 razy

2n drużyn w turnieju gra równolegle, dowód, że się da

Post autor: banias »

Mam problem z udowodnieniem, że da się ustalić harmonogram turnieju tak, żeby w 2n-1 kolejka grały jednocześnie wszystkie drużyny i na koniec każdy z każdym zagrał dokładnie raz.
Przykład: drużyny A, B, C, D:
1. kolejka: A vs B, C vs D
2. kolejka: A vs C, B vs D
3. kolejka: A vs D, B vs C
Drużyny A, B, C, D, E, F:
1. kolejka: A vs B, C vs D, E vs F
2. kolejka: A vs F, B vs C, D vs E
3. kolejka: A vs C, D vs F, B cs E
4. kolejka: A vs E, B vs D, C vs F
5. kolejka: A vs D, B vs F, C vs E
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

2n drużyn w turnieju gra równolegle, dowód, że się da

Post autor: norwimaj »

Najpierw zrób to zadanie, gdy drużyn jest \(\displaystyle{ 2n-1}\). Wtedy też mamy \(\displaystyle{ 2n-1}\) kolejek i w każdej kolejce jedna drużyna pauzuje. Wskazówka: tabliczka dodawania w \(\displaystyle{ \mathbb{Z}_{2n-1}}\) z wykreśloną przekątną.

Potem wystarczy że dodasz jedną drużynę, która będzie grała z tymi, którzy w poprzednim rozwiązaniu pauzowali.
banias
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 13 wrz 2009, o 11:39
Płeć: Mężczyzna
Lokalizacja: Szczebrzeszyn
Podziękował: 2 razy

2n drużyn w turnieju gra równolegle, dowód, że się da

Post autor: banias »

Ciągle mi nie idzie ;/
Narysowałem tabelkę, ale za nic nie mogę z niej ułożyć harmonogramu.
norwimaj
Użytkownik
Użytkownik
Posty: 5101
Rejestracja: 11 mar 2011, o 16:31
Płeć: Mężczyzna
Lokalizacja: 52°16'37''N 20°52'45''E
Podziękował: 4 razy
Pomógł: 1001 razy

2n drużyn w turnieju gra równolegle, dowód, że się da

Post autor: norwimaj »

Jeśli \(\displaystyle{ l+m=k}\) dla \(\displaystyle{ l\ne m}\); \(\displaystyle{ l,m\in\{0,1,\ldots,2n-2\}}\), to \(\displaystyle{ l}\)-ta drużyna spotka się z \(\displaystyle{ m}\)-tą drużyną w \(\displaystyle{ k}\)-tej kolejce.
ODPOWIEDZ