Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

27.03.2010
sobota

Bilion z hakiem

27 marca 2010, sobota,

Nie samymi zagadkami człowiek żyje. Słońce przygrzało, więc pora zacząć mniej chodzić, a więcej pedałować. Nałogowych cyklistów jest w Szczawnicy niewielu – już wszyscyśmy rowery wypucowali i coraz częściej widać nas w plenerze. Zaliczyłem kilka krótkich wypadów na Słowację, żeby rozruszać kości po długim zimowym śnie. Na pobudzenie innych organów aplikuję dodatkowo słowackie piwo.

Nie da się niestety jeździć całkiem bezłamigłówkowo, bo to także nałóg, więc jeśli na drodze jest pustawo, a zwykle jest, główkuję nad tym i owym. Ostatnio w związku z pewnym tematem szachowym kombinowałem, jak policzyć, na ile różnych sposobów można ustawić na szachownicy 8 figur jednej armii (król, hetman, 2 wieże, 2 gońce, 2 skoczki). Ustawienia są różne, jeśli żadne nie może powstać z drugiego w wyniku obrotów lub/i odbić lustrzanych. Zadanie nie jest takie hop-siup ze względu na parę niuansów dotyczących figur. W końcu na trasie między Wielkim Lipnikiem a Czerwonym Klasztorem dopracowałem metodę liczenia i po dotarciu do domu zaprzęgłem do pracy kalkulator. Efekt mam taki:
8 wymienionych figur można umieścić na szachownicy na
1 416 372 917 760
różnych sposobów, czyli jeden bilion z dużym hakiem, prawie półtora.
Nie dam jednak głowy, czy instrument był strojny albo czy się muzyk nie pomylił. Gdyby więc ktoś z Państwa spróbował zmierzyć się z tym problemem i potwierdzić podany wynik albo go zdymisjonować, byłbym wdzięczny. Chętnie też, zwłaszcza w przypadku rozbieżności, podyskutowałbym nad sposobem liczenia.

Komentarze niekontrowersyjne 🙂 uwolnię w przeddzień kolejnego wpisu.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 28

Dodaj komentarz »
  1. hmm… Ciekawie.
    Spróbujmy tak:
    Policzmy tylko te rozstawienia, w których król jest w lewej górnej ćwiartce (A8D5). Wówczas wszystkie rozstawienia symetryczne względem przekątnej A8H1 będą policzone 1 raz, a niesymetryczne 2 razy
    No to liczymy:
    Króla stawiamy w jednym z 16 pól, hetmana na jednym z pozostałych 63 pól, miejsca dla wież, gońców i skoczków wybieramy po kolei na jeden z (62 po 2), (60 po 2), (58 po 2) sposobów. No i mamy:
    n- ilość rozstawień niesymetrycznych wzgl. przekątnej
    s- ilość rozstawień symetrycznych wzgl. przekątnej
    2n+s=16*63*(62 po 2)*(60 po 2)*(58 po 2)=5 576 968 363 680

    Teraz pozostaje policzyć, ile jest symetrycznych rozstawień, jednak w trakcie pisania uświadomiłem sobie, że nie jest to tak proste jak mogłoby się wydawać. W każdym bądź razie liczymy s i mamy:
    (2n+s+s)/2=interesująca nas suma.
    Więc wychodzi, że jest to więcej niż 5 576 968 363 680/2=2 788 484 181 840

    Ale co ja tam wiem. Bardzo irytujące bywają zadania, które rozwiązane w dwa(albo i więcej) różne sposoby dają zupełnie różne wyniki i zupełnie nie wiadomo, który jet poprawny.
    Pozdrawiam

    PS. Faktycznie wypadałoby trochę popedałować 🙂

  2. Czy gońce muszą być na polach różnego koloru?

  3. Michale, czy nie powinieneś tu uwględnić, że np. gońce musza znajdować się na polach różnego koloru?

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Można zacząć od problemu podobnego, różniącego się tylko tym, że rozstawiamy 8 takich samych figur (np. hetmanów). Otrzymane rozwiązanie po przemnożeniu przez 8!/(2!*2!*2!) dałoby odpowiedź na właściwy problem. Stąd też niestety zdymisjonowałbym podany we wpisie wynik, bo nie dzieli się przez tą liczbę bez reszty.

    Myślę, że prędzej uda się wymyślić dobry algorytm programu liczącego te możliwości niż w miarę prosty sposób samodzielnego obliczania.

  6. A nie. To nieprawda co napisałem, bo lustrzane odbicia nie pozwalają na takie postawienie problemu.

  7. 1. Wersja ogólna.

    Pierwszą figurę można ustawić na 64 sposoby, drugą na 63, itd., czyli dla ośmiu figur otrzymujemy

    64x63x…x57

    możliwych ustawień.
    Wśród figur mamy takie, które są nierozróżnialne (konik, wieża, goniec) i, aby wyeliminować identyczne układy utworzone przez nierozróżnialne figury, należy powyższy iloczyn podzielić trzy razy przez dwa (trzy pary figur), czyli mamy

    N=(64x63x…x57)/2^3 (wynik Michała Gajzlera)

    Nasze N jest tylko częścią rozwiązania, bo zawiera ono układy identyczne w sensie obrotów, odbić lustrzanych i być może czegoś jeszcze.
    Po usunieciu niepożądanych ustawień otrzymamy ostateczne rozwiązanie.
    W tej chwili, nie mam pojęcia, jak należy rozumieć obracanie szachownicą i inne sztuczki na niej wyczyniane, więc, postanowiłem puścić koło i poczekać, co zrobią liderzy łamiblogowego peletonu.

    2. Wersja uwzględniająca różnokolorowość gońców (uwagi Michała S. i Piotra).

    Liczba możliwych ustawień

    N=(32(goniec)x32(goniec)x62x61x…x57)/2^2

    Otrzymane N, tak jak w poprzednim przypadku, zawiera układy z obrotami, itd.
    Jak podzielimy N przez 8 (wykluczamy obroty, odbicia – ciekawe, gdzie one są?), to otrzymamy wynik z wpisu, co może sugerować, że Pan Marek poruszał się tym szlakiem.

    PS ROWER+PIWO=? Mam nadzieję, że „+” nie jest koniunkcją.

  8. Szachy to gra królewska, więc zacznijmy od umieszczenia na szachownicy króla. Aby uniknąć układów symetrycznych rozpatrzmy tylko jedną narożną ćwiartkę szachownicy. Króla w tej ćwiartce możemy umieścić tylko na 10 różnych sposobów. Pozosatłe sześć są symetryczne. W następnej kolejności umieszczamy gońce. Są tutaj dwie różne sytuacje:
    1. Król stoi na jednym z 4 pól głównej przekątnej
    – goniec o innym kolorze niż pole, na którym stoi król możemy być ustawiony tylko na 16 sposobów (każde z pozostałych ustawień będzie symetryczne),
    – drugi goniec 31 sposobów
    2. Król stoi na jednym z pozostałych 6-ciu pól
    – goniec o innym kolorze niż pole, na którym stoi król możemy być ustawiony na 32 sposoby
    – drugi goniec 31 sposobów

    Razem 4*16*31+6*32*31

    Dalej jest łatwo, kolejność ustawiania figur dowolna

    Dwie wieże 61*60/2
    Dwa skoczki 59*58/2
    Hetman 57

    Wynik ostateczny (4*16+6*32)*31*61*60/2*59*58/2*57=1 416 372 917 760.
    Potwierdza on wynik Marka.
    Wśród ustawień ośmiu figur na szachownicy jest wiele bardzo interesujących.
    Są 144 takie ustawienia, że atakowane są 63 pola szachownicy (nie ma takiego, w którym są atakowane wszystkie pola). Co ciekawe jeżeli oba gońce będą jednokolorowe to można tak ustawić figury, aby wszystkie pola były atakowane.
    Jest tylko jedno ustawienie z minimalną ilością 16-tu atakowanych pól.

  9. Na pierwszy rzut oka wygląda to na zadanie na zastosowanie lematu Burnside’a. Na drugi rzut oka już widać, że zastosowanie tego lematu będzie raczej proste – z wszystkich obrotów i symetrii tylko identyczność ma punkty stałe. (Tu muszę dodać, że rozumiem obroty, ale jak zastosujemy symetrię, to nam szachy pospadają). No i dostajemy 1/8*32*32*(62po2)*(60po2)*58*57, czyli dokładnie tyle ile wyszło Gospodarzowi.

  10. Ponieważ w treści zadania nie ujawniono wszystkich szczegółów, dlatego zadanie możemy potraktować trojako:
    1. Rozróżniamy figury szachowe i dopuszczamy jedynie gońce różnokolorowe,
    2. Rozróżniamy figury szachowe i dopuszczamy gońce jednokolorowe (np. po przemianie pionka),
    3. Nie rozróżniamy figur szachowych, czyli ważne są jedynie zajmowane miejsca a nie co na nich stoi.
    Dodatkowo istnieje jeszcze problem symetrii, czyli odbić i obrotów. Otóż możemy rozważać symetrię samych figur (nie zważając na kolor pól, na których one stoją) albo figur wraz z kolorami pól!
    Ponieważ liczenia jest co niemiara, dlatego ograniczę się jedynie do p. 1. bez uwzględniania kolorów pól szachownicy. Przypuszczam, że podany w zadaniu wynik również uzyskany jest przy takich założeniach.

    Zacznijmy od uporządkowania figur np. rozważmy je w następującej kolejności: dwa gońce, dwa skoczki, dwie wieże oraz król i hetman i w takiej kolejności będziemy je ustawiać na szachownicy.
    Dwa różnokolorowe gońce można ustawić na szachownicy na 136 sposobów. W tym 120 ustawień jest niesymetrycznych a pozostałe 16 są symetryczne.
    W przypadku 120 niesymetrycznych ustawień możemy w dowolny sposób ustawiać pozostałe figury bez obawy powtórzenia ustawień. W przypadku niesymetrycznego ustawienia gońców mamy:
    (120 niesymetrycznych pozycji gońców) x (62*61/2 pozycje dwóch skoczków) x (60*59/2 pozycje dwóch wież) x (58 pozycji króla) x (57 pozycji hetmana)
    co daje 1 327 849 610 400 ustawień wszystkich figur.
    Po symetrycznym ustawieniu gońców musimy uważać na powtórzenia po ustawieniu pozostałych figur. Ponieważ symetria ustawienia różnokolorowych gońców jest zawsze osiowa, o osi poziomej lub pionowej. Dlatego do dalszych obliczeń uwzględnimy jedynie symetrię o osi pionowej. Teraz, stawiając na szachownicy dwa skoczki, musimy uwzględnić ich ewentualną osiową symetrię o pionowej osi. Na 62 polach, pozostałych po ustawieniu gońców, istotnie różnych ustawień dwóch skoczków jest 961 (=1+3+?+61). Wśród nich mamy 946 niesymetrycznych ustawień oraz 15 ustawień symetrycznych o pionowej osi symetrii. W przypadku 946 ustawień niesymetrycznych możemy w dowolny sposób ustawiać pozostałe figury bez obawy powtórzenia ustawień. Zatem w przypadku symetrycznego ustawienia gońców i niesymetrycznego ustawienia skoczków mamy:
    (16 symetrycznych pozycji gońców) x (946 niesymetrycznych pozycje dwóch skoczków) x (60*59/2 pozycje dwóch wież) x (58 pozycji króla) x (57 pozycji hetmana)
    co daje 88570120320 ustawień wszystkich figur.
    Po symetrycznym ustawieniu gońców i symetrycznym ustawieniu skoczków musimy uważać na powtórzenia po ustawieniu pozostałych figur. Na 60 polach, pozostałych po ustawieniu gońców i skoczków, istotnie różnych ustawień dwóch wież jest 900 (=1+3+?+59). Wśród nich mamy 886 niesymetrycznych ustawień oraz 14 ustawień symetrycznych o pionowej osi symetrii. W przypadku 886 ustawień niesymetrycznych możemy w dowolny sposób ustawiać pozostałe figury bez obawy powtórzenia ustawień. Zatem w przypadku symetrycznego ustawienia gońców i skoczków oraz niesymetrycznego ustawienia wież mamy:
    (16 symetrycznych pozycji gońców) x (15 symetrycznych pozycji dwóch skoczków) x (886 niesymetrycznych pozycji dwóch wież) x (58 pozycji króla) x (57 pozycji hetmana)
    co daje 702987840 ustawień wszystkich figur.
    Po symetrycznym ustawieniu gońców, skoczków i wież musimy uważać na powtórzenia po ustawieniu pozostałych dwóch figur tj. króla i hetmana. Na pozostałych 58 wolnych polach mamy 29 istotnie różnych ustawień króla. Ponieważ król jest jeden zatem jego ustawienie nie daje wraz z gońcami, skoczkami i wieżami symetrycznych ustawień, dlatego hetmana możemy ustawić na dowolnym z pozostałych 57 wolnych pól.
    Zatem po symetrycznym ustawieniu gońców, skoczków i wież oraz ustawieniu króla i hetmana mamy:
    (16 symetrycznych pozycji gońców) x (15 symetrycznych pozycje dwóch skoczków) x (14 symetrycznych pozycji dwóch wież) x (29 pozycji króla) x (57 pozycji hetmana)
    co daje 5554080 ustawień wszystkich figur.
    Teraz pozostaje zsumować wszystkie ustawienia:
    1327849610400+88570120320+702987840+5554080 = 1417128272640

    Ponieważ podana w zadaniu liczba ustawień jest równa 1416372917760, dlatego ciekaw jestem przyczyny tej różnicy.

    Pozdrawiam,
    jazz

  11. Ajajaj! gońce! nikt nie mówił, że muszą być na różnych kolorach… no trudno. pomyślim jeszcze.

  12. Nie dawał mi spokoju problem obrotów i odbić lustrzanych, więc postanowiłem przyjrzeć mu się bliżej.
    Wyjąłem z szafy szachownicę, ustawiłem na niej kilka bierek i już domyślam się o co chodzi w problemie obrotów i odbić.
    Szachownicę można ustawić w czterech pozycjach różniących się o wartość kąta PI/2, względem nieruchomego obserwatora.
    Do każdej pozycji możemy przyłożyć lustro (co dosłownie zrobiłem) uzyskując w ten sposób kolejne cztery ustawienia.
    Ostatecznie, zarówno dla wersji 1 i 2, mamy

    KOŃCOWE ROZWIĄZANIE=N/8

  13. Mam taką wątpliwość Jazzie co do „W przypadku 120 niesymetrycznych ustawień możemy w dowolny sposób ustawiać pozostałe figury bez obawy powtórzenia ustawień.”

    Jeśli dobrze rozumiem warunki zadania to w ustawieniu Gb8, Sc8, Wd8, Hd7, Gg1, Sf1, We1, Ke2 zmiana króla i hetmana miejscami nie da osobnego ustawienia. Natomiast gońce nie są rozstawione symetrycznie względem żadnej z osi symetrii szachownicy. Stąd wątpliwość.

  14. Andrzeju, nie zawsze musi być dzielenie przez osiem. Załóżmy, że figura stoi na którymkolwiek polu na przejątnej, wówczas w wyniku obrotów i odbić dostaniemy tylko cztery różne ustawienia.

    Pozdrawiam,
    jazz

  15. Jazzie, czy mógłbyś podać przykład ustawienia 8 figur należącego do rodziny złożonej z mniej niż ośmiu ustawień bliźniaczych? Oczywiście z różnokolorowymi gońcami (w przykładzie Michała G. gońce są jednokolorowe).
    mp

  16. Tak, zasiał mi Pan ziarno wątpliwości, gdyż rzeczywiście stawiając na szachownicy dwa różnokolorowe gońce i do towarzystwa króla lub hetmana nie uzyskamy rodziny o liczebności mniejszej od ośmiu. A co do komentarza Andrzeja, to myślałem o nim bardziej w oderwaniu od zadania. Niemniej mam coś do przemyślenia, bo póki co nie jestem jeszcze przekonany o błędzie w uzyskanym przeze mnie wyniku.
    Natomiast wątpliwość Michała Gajzlera chyba nie ma uzasadnienia, gdyż w podanym przez Niego przykładzie rzeczywiście gońce są jednokolorowe a z symetrią punktową możemy mieć do czynienia jedynie przy gońcach jednokolorowych.

    Pozdrawiam,
    jazz

  17. Mimo chwilowego zwątpienia nadal nie widzę błędu w moim rozumowaniu i oczekuję na ewentualne wyjaśnienie przyczyny rozbieżności pomiędzy uzyskanym przeze mnie wynikiem a wynikiem przedstawionym w zadaniu.
    🙂

  18. Jazzie, masz rację, nie zawsze musi być dzielenie przez osiem. Istnieją przypadki, kiedy dzielimy przez cztery, ale tylko wówczas, gdy wszystkie figury leżą na tej samej przekątnej (obroty i lustrzane odbicia pokrywają się). Jest to przypadek zadania, w którym gońce nie muszą być różnokolorowe. W zadaniu dla różnokolorowych gońców dzielimy przez osiem.

    Dzięki twojemu spostrzeżeniu, podane przeze mnie rozwiązanie, w wersji ogólnej, jest błędne i powinno zostać poprawione. Natomiast w wersji różnokolorowych gońców pozostaje bez zmian.

  19. Andrzeju, ponieważ powołujesz się na swoje rozwiązanie, więc zdecydowałem się uwolnić przed terminem wszystko, co kończy się takim wynikiem, jak we wpisie.
    Moim zdaniem rozwiązanie Jazza jest poprawne – i robi wrażenie – dla pary gońców, którym jest wszystko jedno, na jakich polach stoją. Jeśli natomiast gońce są różnopolowe, to prawidłowy jest wynik z wpisu. Chyba że nie dostrzegam jakiegoś kruczka.
    mp

  20. Faktycznie. Dziękuję. Nie zwróciłem uwagi.

  21. W związku z takim obrotem sprawy powinienem wyliczyć wszystkie dopuszczalne ustawienia różnokolorowych gońców. A oto i one (dużymi literami zaznaczono symetryczne):
    – jeden goniec na a8, drugi na: b8, d8, f8, H8, c7, e7, g7, d6, f6, h6, e5, g5, f4, h4, g3, h2 (16 w tym 1 symetryczny);
    – jeden goniec na b8, drugi na: c8, e8, G8, b7, d7, f7, h7, a6, c6, e6, g6, b5, d5, f5, h5, a4, c4, e4, g4, b3, d3, f3, h3, c2, e2, g2, B1, d1, f1 (29 w tym 2 symetryczne);
    – jeden goniec na c8, drugi na: d8, F8, c7, e7, g7, b6, d6, f6, h6, a5, c5, e5, g5, b4, d4, f4, h4, c3, e3, g3, b2, d2, f2, C1, e1 (25 w tym 2 symetryczne);
    – jeden goniec na d8, drugi na: E8, b7, d7, f7, c6, e6, g6, b5, d5, f5, h5, c4, e4, g4, b3, d3, f3, c2, e2, g2, D1 (21 w tym 2 symetryczne);
    – jeden goniec na b7, drugi na: c7, e7, G7, d6, f6, e5, g5, f4, g3 (9 w tym 1 symetryczny);
    – jeden goniec na c7, drugi na: d7, F7, c6, e6, g6, b5, d5, f5, c4, e4, g4, d3, f3, C2, e2 (15 w tym 2 symetryczne);
    – jeden goniec na d7, drugi na: E7, d6, f6, c5, e5, g5, d4, f4, c3, e3, D2 (11 w tym 2 symetryczne);
    – jeden goniec na c6, drugi na: d6, f6, e5, f4 (4 w tym 1 symetryczny);
    – jeden goniec na d6, drugi na: E6, d5, f5, e4, D3 (5 w tym 2 symetryczne);
    – jeden goniec na d5, drugi na: E5 (1 w tym 1 symetryczny);
    Razem 136 w tym 16 symetrycznych.
    Myślę, że wszystkie są różne, ale może się mylę.

    Pozdrawiam,
    jazz

  22. Jazzie, czy uwzględnianie symetrycznego ustawienia gońców jest w ogóle istotne dla ustalenia wszystkich różnych ustawień 8 figur?
    Weźmy prostszą sytuację: na ile różnych sposobów można ustawić 2 gońce i króla?
    Niezależnie od tego, czy pozycja gońców będzie symetryczna, czy nie, to po dostawieniu króla każde ustawienie 3 figur będzie miało 7 ustawień bliźniaczych, ponieważ króla nie można ulokować na osi symetrii ustawienia gońców. Chcąc teraz ustalić, ile jest różnych ustawień tych 3 figur, wystarczy policzyć hurtem wszystkie bliźniacze (32x32x62) i podzielić przez 8.
    Podobnie wygląda sytuacja z kompletem 8 figur.
    mp

  23. Kiedy wszystkie figury leżą na jednej przekątnej ( ogólny wariant zadania), to chyba dzielimy przez dwa , a nie cztery.

    Panie Marku, a jaka to była metoda liczenia, która powstała w Pana głowie, na trasie między Wielkim Lipnikiem a Czerwonym Klasztorem?

  24. Andrzeju, moja metoda była łudząco podobna do Twojej (dla różnokolorowych gońców, bo tylko ten wariant mnie interesował). I nie dziwota – wszak my, rowerzyści, myślimy podobnie.
    Istone było zauważenie, że liczba ustawień wież i skoczków odpowiada liczbie kombinacji bez powtórzeń, czyli można ją potraktować symbolem Newtona. Niby nic wielkiego, ale dojść do tego jadąc na rowerze to wyższa szkoła jazdy :).
    Pozdravy
    mp

  25. To zadanie przypomniało mi jak kiedyś zastanawiałem się nad liczbą możliwych przebiegów gry w ‚kółko i krzyżyk’ (gdzie ruchy ‚symetryczne’ należy uznać za te same). W związku z tym szczególnie zainteresowała mnie wypowiedź Thety o zastosowaniu lematu Burnside’a. Niestety niewiele rozumiem z tego co o nim przeczytałem w sieci, ale może miałby i tu zastosowanie? A może ktoś z czytelników pokusiłby się o obliczenie tych możliwości, a zwłaszcza o znalezienie wygodniejszego sposobu liczenia niż rozpatrywanie po kolei wszystkich możliwości? Zachęcam, bo jestem ciekaw czy tu też okaże się, że rozwiązanie jest prostsze niż się wydaje.

  26. Jeśli gońce nie musiałyby stać na polach różnego koloru, to tym bardziej lobbowałbym za zastosowaniem lematu Burnside’a. Niech N oznacza ilość wszystkich ustawień (policzoną np. przez Andrzeja dla wersji ogólnej) i niech k oznacza ilość ustawień na przekątnej (łatwo policzyć). Dostajemy 1/8*(N+k+k), bo 8 to liczba elementów grupy przekształceń, identyczność ma N punktów stałych, symetrie względem przekątnej po k punktów stałych, pozostałe symetrie i obroty nie mają punktów stałych (punkt stały to takie ustawienie, którego dane przekształcenie nie zmienia).

  27. Michale G.
    Spróbuję z tym kółkiem i krzyżykiem i przy okazji może ciut przybliżę lemat B. Najczęściej stosujemy go do szachownicy lub naszyjnika z iluśtam koralików. Jeśli chcemy wiedzieć ile jest jakichś układów na szachownicy lub układów koralików niezależnych od obrotów lub obrotów i symetrii (te dwie rodziny przekształceń to grupy), dla każdego z przekształceń liczymy ilość ustawień, których to przekształcenie nie zmienia (np. identyczność nie zmienia żadnego ustawienia), sumujemy i dzielimy wynik przez liczbę przekształceń (liczbę elementów grupy).

    Dla planszy ‚kik’ podobnie jak w szachach mamy identyczność, trzy obroty i cztery symetrie. Powiedzmy, że zawsze zaczynamy od kółka. Jeśli grę rozumiemy jako kolejne numerowane ruchy, to sprawa sprowadza się do policzenia N – liczby wszystkich gier (mających 5 ruchów, 6 ruchów, …, 9 ruchów) – wszystkie są oczywiście punktami stałymi identyczności, zaś przy każdym obrocie, czy symetrii jakiś numerek zmienia miejsce, czyli nie mają one punktów stałych. Zatem wynik to N/8.

    Więcej roboty mielibyśmy z lematem B., gdybyśmy grę rozumieli np. jako wszystkie ustawienia pięciu kółek i czterech krzyżyków. Wtedy dla idetyczności stałe są wszystkie układy (9po5), dla obrotu o 1 stały będzie układ z kółkiem w środku i kółkami w rogach oraz układ z kółkiem w środku i krzyżykami w rogach, czyli (o ile żadnego nie pominąłem) 2 układy. Itd. Sumujemy, dzielimy przez osiem i gotowe.

  28. Theta, wielkie dzięki za objaśnienie lematu! Ponieważ odnalezione w sieci przykłady na jego zastosowanie są dość skomplikowane to pozwolę sobie podać dydaktycznie bardzo prosty przypadek (co niech jednocześnie będzie sprawdzianem, czy aby na pewno wszystko dobrze zrozumiałem).

    ‚Na oko’ widać, że na pustej planszy gry w ‚kółko i krzyżyk’ kółko można postawić na 3 zasadniczo różne sposoby. Zgodnie z lematem Burnside’a: (9+3+3+3+3+1+1+1)/8 = 3,

    – 9 (czy też: [9po1]), ze względu na przekształcenie identycznościowe,
    – 3, bo są 3 ustawienia, których symetria nie zmienia (a symetrie są 4 i każda ma ‚swoje’ 3 ustawienia, których nie zmienia)
    – 1, bo jest tylko jedno ustawienie, którego żaden obrót nie zmienia (a obroty są 3)
    a 8 to liczba przekształceń.

    Ponieważ od początku kombinowałem nad opcją, w której gońce mogą być jednokolorowe, to wyszło mi, że

    k=8*7*(28*27*26+(6!/(2!*2!*2!))+[6po2]*[4po2]*28*3+[6po2]*28*27*3)

  29. Michale G.
    Wszystko się zgadza.

css.php