logowanie

matematyka » forum » forum zadaniowe - zadania różne » zadanie

Inne, zadanie nr 97

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

tomnow
postów: 10
2012-09-22 20:54:38

Witam

Mam do pokolorowania $n$-kąt foremny za pomocą $k$ kolorów. N-kąt jest podzielony na n części odcinkami wychodzącymi ze środka okręgu opisanego na danym n-kącie do jego wierzchołków.

Pytanie: Ile jest różnych kolorowań takiego wielokąta?

Należy przyjąć, że jeśli w wyniku obrotu lub "odwrócenia" figury na drugą stronę otrzymamy figurę podobną to uznajemy kolorowania za takie same.

Rysunek niżej przedstawia kolorowanie czworokąta przy użyciu dwóch różnych kolorów. Jest ich 6.




No i tu moja wyobraźnia się kończy . Czy jest jakiś wzór ogólny, który mógłby określić liczbę kolorowań n-kątów za pomocą k kolorów?




tumor
postów: 8070
2012-10-23 20:36:02

Odpowiedzią na Twoje pytanie jest Lemat Burnside'a.

$N=\frac{1}{|G|}\sum_{g\in G}|fix(g)|$

$N$ to jest liczba, której szukasz.
$G$ jest grupą operacji, którymi działasz na zbiorze. Konkretnie chodzi nam o grupę izometrii wielokąta foremnego.
W grupie tej dla kwadratu mamy obroty o $0,90,180,270$ stopni oraz symetrie względem przekątnych (dwie) i względem symetralnych boków (też dwie). Zatem $|G|=8$.

Dla pewności dopiszę, że $G$ jest grupą w sensie teorii grup, algebry, nie taką sobie zbieraniną. :)

$fix(g)$ to zbiór punktów stałych przekształcenia $g$, czyli w naszym przypadku to zbiór kolorowań, których przekształcenie $g$ nie zmieni.

1) Obrót o $0^\circ$
Taki obrót zostawia kwadrat w spokoju. Wszystkich możliwości pokolorowania kwadratu k kolorami jest k^4, a gdy pokolorujemy, to obrót nic nie zmieni. Dlatego WSZYSTKIE możliwe kolorowania są punktami stałymi.

2) Obrót o $90^\circ$ lub $270^\circ$
Zauważmy, że kwadrat musi być cały w jednym kolorze, by po takim obrocie pozostał niezmieniony. Zatem punktów stałych jest tyle, ile kolorów, czyli $k$.

3) obrót o $180^\circ$
By nie zmienił on kwadratu, identyczne muszą być trójkąty naprzeciw siebie. Kwadrat może być dwukolorowy, by był punktem stałym takiego przekształcenia, ale nie dowolnie dwukolorowy, tylko z identycznymi odpowiednimi trójkątami, czyli $k^2$ możliwości.

4) symetria względem przekątnej
Tu także $k^2$ możliwości.

5) symetria względem symetralnej boku kwadratu
Te trójkąty, które są po przeciwnych stronach osi symetrii, muszą być w tych samych kolorach. Natomiast te przecięte osią symetrii mogą być dowolne, czyli $k^3$.

Ogółem, dla $k$ kolorów i kwadratu, dostajemy

$N=\frac{1}{8}(k^4+2k^3+3k^2+2k)$

Co jest rzeczywiście (uff!) równe $6$, jeśli mamy dwa kolory.

----

W ogólnym przypadku bierzesz n-kąt. Dzielisz go na n trójkątów, wszystkich możliwych kolorowań $k$ kolorami masz $k^n$. Rozważasz sobie wszystkie przekształcenia, które muszą tworzyć grupę. Same obroty tworzą grupę, ale obroty z symetriami też tworzą grupę i w tym przypadku na niej się skupimy.

Dla n-kąta foremnego masz $n$ obrotów o kolejne wielokrotności $\frac{360^\circ}{n}$. Symetrii jest $n$ (dla nieparzystego $n$ osiami są symetralne boków, dla parzystego symetralne boków i przekątne łączące przeciwległe wierzchołki).

Dla obrotu o $0$ stopni oczywiście wszystkie kolorowania są punktami stałymi.
Dla obrotu o $\frac{360^\circ}{n}$ punktami stałymi są tylko wielokąty jednokolorowe.
Ogólniej, jeśli $NWD(p,n)=1$, to obrót o $p\frac{360^\circ}{n}$ ma punkty stałe tylko w postaci n-kątów jednokolorowych, czyli jest ich $k$.
I tak dalej, i tak dalej, można te rozważania prowadzić, ale mi się pisać nie chce. Pomyśl, które trójkąty z którymi muszą mieć identyczny kolor, by w obrotach czy symetriach kolorowań nie zmienić. W ten sposób ustal ilość kolorowań, które w tych przekształceniach są punktami stałymi. A potem to już do wzoru. :)

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj