Oblicz ile jest istotnie różnych sposobów pokolorowania dwoma kolorami kwadratu podzielonego na trójkąty jak na rysunku poniżej
kolorowanie kwadratu
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
kolorowanie kwadratu
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..
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..
-
- Użytkownik
- Posty: 132
- Rejestracja: 1 cze 2012, o 07:04
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 15 razy
kolorowanie kwadratu
Pewną sumę z Adamem policzyliśmy różnymi sposobami.
Potwierdzam, że ten składnik otrzymujemy taki sam.
DrsyC
Potwierdzam, że ten składnik otrzymujemy taki sam.
DrsyC