[Przedszkole]Czyli krótka rozprawa o zliczaniu (istotnie) różnych rzeczy

Wpis opublikowany przez Hakken Wrzesień 24, 2014

1018 wyświetleń

Wstęp

Częstym problemem kombinatorycznym z którym mierzą się uczniowie szkół już nawet gimnazjalnych jest pytanie "na ile sposobów można pokolorować cośtam?". Dzisiaj zajmiemy się problemami tego typu... oraz wieloma innymi, bo teoria którą przedstawię jest bardzo poważna i mocna. Ze względu na to ścisłe podejście do problemu umieszczę na końcu, może uda się uniknąć omdleń.

Weźmy przykładowy problem którym będziemy się zajmować: mamy naszyjnik, czyli sznureczek na który można nawlekać kolorowe kamyczki. Ile różnych naszyjników można stworzyć jeżeli chcemy nawlec 6 kamyczków, a mamy kamyczki w dwóch kolorach (powiedzmy, że w obu kolorach mamy do dyspozycji 6 kamyczków).

Podejście naiwne

Można by powiedzieć tak: narysujmy sobie taki naszyjnik:

Teraz powiedzielibyśmy tak: każdy z sześciu kamyczków może zostać wybrany na jeden z dwóch sposobów. Można więc stworzyć 2^6 (czyli 64) różnych naszyjników. Zapamiętajmy ten wynik.

Refleksja

Wydawać by się mogło, że problem jest rozwiązany. Jednak w zależności od wyobraźni możemy szybciej lub wolniej zauważyć pewien problem.

Według powyższego rozumowania poniższe dwa naszyjniki są różne:

A przecież zamiana jednego w drugi to lekki obrót naszyjnika. Nikt w realnym świecie nie dałby sobie wmówić, że są to dwa odmienne wzory. To oznacza, że do naszego problemu zliczania naszyjników trzeba podejść inaczej...

Podejście Burnside'a

Żeby policzyć ile jest istotnie różnych naszyjników użyjemy lematu Burnside'a.

Najpierw zastanówmy się, co można z takim naszyjnikiem zrobić? Wypiszmy:

Zostawić jak leży, nie robić nic.
Obrócić w lewo o jeden kamyczek
Obrócić w lewo o dwa kamyczki
Obrócić w lewo o trzy kamyczki
Obrócić w lewo o cztery kamyczki
Obrócić w lewo o pięć kamyczków

Możemy przyjąć, że kamyki są kolorowe tylko z jednej strony, przez co odchodzą operacje odwracania naszyjnika na drugą stronę (tak, że to co teraz jest na wierzchu byłoby pod spodem). Robimy to dla ułatwienia obliczeń.

Teraz po kolei będziemy się zastanawiać dla każdej z powyższych czynności ile jest takich naszyjników, że przed i po danej operacji nic w wyglądzie naszyjnika się nie zmieni.

Jeżeli nic nie będziemy z naszyjnikiem robić, to każdy jest inny - czyli mamy 2^6 takich naszyjników.

Jeżeli obrócimy o jeden kamyk, to każdy kamień musi być tego samego koloru. Takich naszyjników nie jest wiele, bo tylko 2.

Przy obrocie o dwa mamy cztery możliwości: zauważmy, że tworzą się dwa niejako trójkąty, wszystkie kamyki w trójkącie muszą być tego samego koloru, a więc albo oba są tego samego koloru (2 możliwości), albo są innych kolorów (znowu dwie możliwości). Widać to na rysunku niżej

Obrót o trzy: widzimy, że stworzą się trzy pary. W każdej parze oba kamienie muszą być tego samego koloru, czyli mamy 2^3 (czyli osiem) możliwości.

Obrót o cztery jest taki sam jak obrót o dwa, więc znowu 4.

Obrót o pięć jest taki sam jak obrót o 1, czyli znowu 2.

Dwa ostatnie przypadki były łatwe, bo obrót o 5 w lewo to to samo, co obrót o 1 w prawo, analogicznie jest z 4 i 2.

Teraz musimy dodać wszystkie te wartości i podzielić przez liczbę ruchów jakie były dozwolone (czyli te, które są wypisane w liście powyżej).

Liczymy:

Jak widać, otrzymany wynik jest istotnie różny niż ten, który dostaliśmy stosując podejście naiwne!

Ogólny schemat działania

Można się zastanowić, czy ta sztuczka działa tylko dla koralików. Otóż nie, jest to bardzo uniwersalna metoda działania. Niezależnie czy rozważamy koraliki, kolorowanie grafów, figur w płaszczyźnie bądź przestrzeni postępowanie jest to samo: wypisujemy możliwe operacje i dla każdej szukamy takich obiektów, że przed i po tej operacji są dokładnie takie same. Potem dodajemy, dzielimy przez liczbę działań i mamy wynik.

Ścisłe wyjaśnienie algebraicznej teorii - nie dla ludzi o słabych nerwach!

Zacznijmy od tego, że operacje (powyższe obroty) stanowią grupę G działającą na zbiór obiektów kombinatorycznych (w naszym przykładzie naszyjniki, czyli mówiąc ściślej cykl o sześciu wierzchołkach). Grupę którą określiliśmy można rozważać geometrycznie (jak to robiliśmy wyżej) lub jako - liczby od 0 do 5 z działaniem dodawania modulo 6.

Rozważmy teraz zbiór zwany orbitą elementu x:. Jest to więc zbiór różnych elementów które powstają na wskutek działania grupy G.

Stabilizator elementu x to taki zbiór działań (czyli elementów z G), że .

x jest punktem stałym jeżeli . Zbiór punktów stałych wyznaczonych przez element g oznaczamy .

Zbiór wszystkich orbit oznaczamy .

Lemat Burnside'a mówi, że (dla skończonych zbiorów działań i elementów) liczba orbit jest równa średniej liczbie punktów stałych, czyli

Jak widać ten lemat można stosować do przeróżnych obiektów i grup wymyślając przeróżne warunki utożsamiania dwóch obiektów.

Jeżeli ktoś chce poćwiczyć, to może np. policzyć ile jest istotnie różnych sposobów pokolorowania ścian sześciościanu foremnego przy użyciu dwóch kolorów, jeżeli utożsamiamy takie pokolorowania, że jedno przechodzi na drugie przy pewnym obrocie w