kolorowanie kwadratu

[marika331]

Oblicz ile jest istotnie różnych sposobów pokolorowania dwoma kolorami kwadratu podzielonego na trójkąty jak na rysunku poniżej

[adambak]

domyślam się, że dwa kolorowania uznajemy za istotnie różne wtw kiedy jedno nie przechodzi na drugie przy pewnym obrocie..

Odp.: \(\displaystyle{ 70}\)
z lematu Burnside'a liczymy średnią ilość punktów stałych.. na kwadrat działamy grupą obrotów (\(\displaystyle{ 0^{\circ},90^{\circ},180^{\circ},270^{\circ}}\)), a więc do rozpatrzenia mamy cztery przypadki:

1. obrót o \(\displaystyle{ 0^{\circ}}\)
w tym przypadku każde kolorowanie przechodzi na samo siebie, więc mamy \(\displaystyle{ 2^8}\) punktów stałych

2. obrót o \(\displaystyle{ 90^{\circ}}\)
zauważmy, że przy tym obrocie lewy górny trójkąt przechodzi na prawy górny, prawy górny na prawy dolny, prawy dolny na lewy dolny, lewy dolny na lewy górny i permutacja się zamyka.. taki sam cykl jest dla trójkątów w środku.. wobec tego aby kolorowanie było punktem stałym to kolorując lewy górny trójkąt wyznaczamy kolor dla reszty trójkątów w cyklu, to samo dla drugiego cyklu, wobec tego dla każdego cyklu wybieramy jeden z dwóch kolorów tzn jest \(\displaystyle{ 2^2}\) punktów stałych

3. obrót o \(\displaystyle{ 180^{\circ}}\)
lewy górny <-> prawy dolny
prawy górny <-> lewy dolny
takie same dwa cykle dla trójkątów wewnątrz, wobec tego mamy cztery cykle i dla każdego wybieramy jeden z dwóch kolorów, czyli \(\displaystyle{ 2^4}\) punktów stałych

4. obrót o \(\displaystyle{ 270^{\circ}}\)
lewy górny -> lewy dolny -> prawy dolny -> prawy górny-> lewy górny i mamy cykl, wszystkie trójkąty w cyklu ten sam kolor, mamy dwa takie cykle bo dla trójkątów wewnątrz jest to samo, czyli w tym przypadku znowu \(\displaystyle{ 2^2}\) punktów stałych

podsumowując, z lematu Burnside'a mamy że liczba orbit = średnia liczba punktów stałych, a więc liczymy tą średnią: \(\displaystyle{ \frac{1}{4} \cdot \left( 2^8+2^2+2^4+2^2\right)=70}\) istotnie różnych kolorowań tego kwadratu, na \(\displaystyle{ 2}\) kolory, z dokładnością do obrotów..

[ksisquare]

Pewną sumę z Adamem policzyliśmy różnymi sposobami.
Potwierdzam, że ten składnik otrzymujemy taki sam.
DrsyC