Temat: Szukanie rozstawienia... :)

Witam,
mam problem z którym nie radzę sobie od tygodnia: Problemik. Może ktoś tutaj spojrzy na to bardziej fachowym okiem ? :) Pozdrawiam.Darek J. edytował(a) ten post dnia 03.12.12 o godzinie 11:37

Temat: Szukanie rozstawienia... :)

Zadanie z analizy kombinatorycznej. Należy skorzystać z twierdzenia Brucka-Rysera-Chowli.
Ponieważ 20 jest liczbą parzystą, w grupie są 4 osoby a każda para może powtórzyć się tylko jeden raz, należy sprawdzić czy 4-1 jest kwadratem, a ponieważ nie jest, więc nie jest spełniony warunek konieczny istnienia BIB-konfiguracji. W związku z tym, że z 20 liczb można utworzyć tylko 190 różnych par (20 po 2 = 190) a do utworzenia 6 grup po 5 czwórek potrzebnych jest ich 180, zadanie nie ma rozwiązania.

Można natomiast utworzyć 6 grup po 4 czwórki - jak poniżej.

17, 18, 19, 20 | 14, 15, 16, 20 | 12, 13, 16, 19 | 11, 13, 15, 18 |
11, 12, 14, 17 | 9, 10, 16, 18 | 8, 10, 15, 19 | 8, 9, 13, 20 |
7, 10, 13, 17 | 7, 9, 14, 19 | 7, 8, 12, 18 | 6, 10, 12, 20 |
6, 9, 15, 17 | 6, 8, 11, 16 | 5, 7, 11, 20 | 5, 6, 14, 18 |
4, 5, 16, 17 | 3, 5, 12, 15 | 3, 4, 13, 14 | 2, 4, 11, 19 |
2, 3, 8, 17 | 1, 4, 9, 12 | 1, 3, 10, 11 | 1, 2, 7, 16 |

Temat: Szukanie rozstawienia... :)

Brak rozwiązania można uzasadnić w inny sposób, bez odwoływania się do twierdzenia B-R-C.

Tak na chłopski rozum można by oczekiwać, że rozwiązanie istnieje, bo po każdej rundzie każdy gracz ma 3 dodatkowych graczy z którymi zagrać już nie może. Czyli po 6 rundach nie może zagrać z 18 graczam, a przeciwników jest 19 więc niby rozwiązanie mogłoby istnieć. Jasne jest że gdyby rund byłoby 7 to rozwiązania na pewno by nie było.

Ale, jeżeli gracze rozegrają 5 rund, to każdy gracz zagra z 15 innymi graczami, czyli pozostanie mu w ostatniej rundzie 5 do wyboru. Jacy oni będą?

Algorytm:
1) Dzielimy graczy na 4 grupy po 5 graczy (ponumerujmy grupy od 1 do 4)
2) W pierwszej rundzie do każdego z 5 stołów (numerujemy je od 1 do 5) siada po jednym zawodniku z każdej grupy.
3) W kolejnej rundzie zawodnicy z pierwszej grupy przesiadają się o 1 stół w lewo, z drugiej grupy o 2 stoły w lewo, z trzeciej o 3 w lewo, z czwartej o 4. Stoły są zorganizowane z koło, zatem jeżeli gracz siedzący przy stole nr. 5 ma przesiąść się o 2 stoły w lewo to siada przy stole 2. Matematycznie ruch gracza można opisać prostym wzorem:

nr_stołu = (nr_stołu_w_poprzedniej_rundzie + (nr_grupy - 1)) \ 5 + 1

gdzie \ to operacja wyznaczania reszty z dzielenia.
4) W kolejnych 5 rundach indeksy ruchu graczy się tak ułożą, że żaden gracz nie zagra z żadnym innym graczem 2 razy. Co więcej, każdy gracz jednej grupy zagra ze wszystkimi graczami pozostałych grup. Jeżeliby dokonać jakiejkolwiek zamiany graczy, to jakaś para graczy zagrałąby ze sobą 2 razy. Zatem jest to jedyne dopuszczalne rozwiązanie.

W piątej rundzie każdemu graczowi zostaje 5 graczy z którymi nie grał i są to tylko i wyłącznie gracze z jego własnej grupy. I tutaj jest problem, bo do 4 stołów można posiadzić po 4 graczy przy czym przy każdym stole siedzą gracze z dokładnie tej samej grupy. Zostaje stół 5 gdzie trzeba by posadzić pozostałych graczy: po jednym z każdej grupy ale oni już ze sobą grali. Więc nie ma rozwiązania. W ostaniej rundzie powinny być 4 stoły po 5 graczy a nie 5 stołów po 4 graczy.

Czy coś pominąłem?

Temat: Szukanie rozstawienia... :)

Filip Gurgul:
Brak rozwiązania można uzasadnić w inny sposób, bez odwoływania się do twierdzenia B-R-C.
...
3) W kolejnej rundzie zawodnicy z pierwszej grupy przesiadają się o 1 stół w lewo, z drugiej grupy o 2 stoły w lewo, z trzeciej o 3 w lewo, z czwartej o 4. Stoły są zorganizowane z koło, zatem jeżeli gracz siedzący przy stole nr. 5 ma przesiąść się o 2 stoły w lewo to siada przy stole 2.

Gratuluję. Rozumowanie godne wielebnego Thomasa Kirkmana przy ustawianiu w trójki swoich uczennic.

Temat: Szukanie rozstawienia... :)

Dzięki Wam Panowie, muszę przeczytać i przetrawić oba rozwiązania, co w moim wieku może nie być proste... :) Pozdrawiam.

Temat: Szukanie rozstawienia... :)

Darek J.:
Dzięki Wam Panowie, muszę przeczytać i przetrawić oba rozwiązania, co w moim wieku może nie być proste... :) Pozdrawiam.

:-)
Nigdy nie jest za późno ;-)
BTW. W lutym na coursera.org rozpoczynają się zajęcia z analizy kombinatorycznej:
https://www.coursera.org/course/introACpartI

Temat: Szukanie rozstawienia... :)

Marcin Szwebs:
BTW. W lutym na coursera.org rozpoczynają się zajęcia z analizy kombinatorycznej:
https://www.coursera.org/course/introACpartI

Dzięki, nie wiem czy wyrobię, bo już zapisałem się na parę kursików w necie, ale zobaczę jeszcze jak mi pójdzie :)