Swiecace zaroweczki ( orbity, symetrie itp. )

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Zadanie polega na znalazieniu ilosci istotnie roznych sposobow, na jakie mozna pokolorowac szesciokat foremny, w ktorym na kazdym wierzcholku umieszczono zarowke swiecaca na 3 rozne kolory w zaleznosci od wartosci funkcji \(\displaystyle{ f( t ) = ( k + t ) \mod 3 \ \ k \in \{ 0, 1, 2 \}}\), gdzie t to parametr czasu ( czyli swiatlo zmienia sie wraz z uplywem czasu ) a k to stan poczatkowy danej zarowki. Istotnie rozny sposob to takie rozmieszczenie, ze jedno przechodzi na drugie przy pewnej izometrii szesciokata i po uplywie jakiegos czasu. To zadanie podejrzewam jest na liczenie orbit itp., natomiast z tego tematu nie mialem okazji widziec wielu ( lub tez wcale ) zadan i takie proste, lopatologiczne rozwiazanie byloby tu jak znalazl ( nie mowie z dowodami twierdzen, czy superszczegolowym wyjasnieniem krokow, natomiast jesli jakas metoda, czy twierdzenie sie pojawia, to miloby bylo o tym wiedziec ( szczegolnie w kontekscie "google'owania" ) ).

Z gory dziekuje za okazana pomoc.


Z powazaniem, M4ksiu
Awatar użytkownika
Konikov
Użytkownik
Użytkownik
Posty: 497
Rejestracja: 13 mar 2008, o 18:56
Płeć: Mężczyzna
Lokalizacja: z całki tego świata
Podziękował: 66 razy
Pomógł: 44 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Konikov »

Heh, MD na UW? ;] Ja to policzyłem na egz. na palcach, wypisałem wszystkie możliwości. Jeśli interesują Cię szczegóły (wypisane kolejne sposoby, ilość takich możliwości i dlaczego), to chętnie napiszę.

Generalnie owe zadanie można policzyć 2 sposobami: na chama (preferowane przez prawie wszystkich studentów) i użyć jakichś mocniejszych narzędzi (chętnie bym sam się dowiedział/przypomniał jak).
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Tak, jestem zainteresowany. Probowalem to zrobic "na chama", ale chyba gdzies sie walnalem, bo dostalem 0 punktow ( pewnie nie uwzglednilem jakis przypadkow, ktore sie powatarzaja, czy czegos innego a moze po prostu moj sprawdzajacy oczekiwal indeksow cyklowych, symetrii, obrotow i Bog wie czego jeszcze ) - dlatego chetnie sie dowiem jak wyglada "agresywne" i poprawne ( zakladam, ze dostales cos wiecej niz 0 za zadanie ) rozwiazanie.


Z powazaniem, M4ksiu.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Zordon »

Lemat Burnside'a

wsk: działamy grupą \(\displaystyle{ \mathbb{Z}_3\times \mathbb{D}_6}\)
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Heh, spodziewalem sie tej odpowiedzi. Dobra, pomyslmy troche, bo to zawsze dobrze wplywa na tok rozumowania.

Mamy 6 elementow, ktore musimy pokolorowac na 3 kolory. Mozna sie bawic w dziwne rzeczy typu: \(\displaystyle{ {6 \choose k}{6 - k \choose l} = \frac{6!}{k!l!(6 - k - l)!}}\), ale tu nie nalezy podejmowac sie robienia zadania tak "niebezposrednia" ( ze wzgledu na k i l, ktore trzeba wybijac na przypadki ). Dlatego przypuszczam, ze nalezy zrobic proste \(\displaystyle{ 3^6}\) - czytaj dla kazdego z 6 punktow wybieramy 1 z 3 kolorow.

Ok, teraz rozbijamy "to" na przypadki obrotow, ktore maja nam wskazac punkty stale:
1) \(\displaystyle{ id = 3^6}\), czyli kazdy punkt jest tu punktem stalym.
2) Obrot o kat \(\displaystyle{ \frac{\pi}{3}}\):
a) 2 przesuniecia o ten kat ( po jeden na kierunek ), ktore daja 0 punktow stalych chyba, ze wszystkie wierzcholkow maja jeden kolor.
b) 2 przesuniecia o \(\displaystyle{ \frac{2 \pi}{3}}\), w ktorych przypadku mamy wszystkie punkty stale, jesli przesuwamy figure jednokolorowa lub tez punkty sa kolorowane naprzemiennie.
c) przesuniecie o kat \(\displaystyle{ \frac{\pi}{2}}\), w ktorym to - by byly punkty stale - mamy miec dwie polowy pomalowane symetrycznie wzgledem osi przechodzacej przez dany wierzcholek i jego przeciwlegly odpowiednik ( o tym samym kolorze ).

Teraz zliczam wszystkie punkty stale.
1) \(\displaystyle{ 3^6}\)
2)
a) 0
b) \(\displaystyle{ 3^2}\)
c) \(\displaystyle{ 3^3}\)

Teraz co do wyliczen \(\displaystyle{ |G|}\), to mam w swojej glowie mnostwo watpliwosci, ale zaryzykuj ( patrzac na swoje notatki i to, co napisal Zordon ), ze bedzie to \(\displaystyle{ |G| = 6 * 3}\), jako grupa 6-elementowa o 6 obrotach i 3 przypadkach, ktore sie powtarzaja wraz z uplywem czasu ( pewnie to jakas wielka gafa, za ktora bede sie wstydzil przyjsc ponownie na forum ).

Zatem zliczajac:
\(\displaystyle{ N = \frac{3^6 + 2 * 3^2 + 3^3}{3^2 * 2} = \frac{3^4 + 2 + 3}{2} = \frac{86}{2} = 43}\).

Niestety musze sie przyznac, ze troche pokombinowalem z tym \(\displaystyle{ |G|}\), aby wyszlo rowno i nie rozumiem tego do konca, poniewaz zadania, z ktorymi mialem stycznosc, nie tlumaczyly roznych zabiegow ( pewnie dlatego, bo byly czasem robione chaotycznie lub tylko dla grupy krzyczacej "dalej!", lub ewentualnie w ogole nie byly dokanczane ). Dlatego moim poczatkowym pomyslem na \(\displaystyle{ |G|}\) bylo: oborty * ilosc_elementow_powtarzajacych_sie_w_czasie * "cos".

Prosilbym o proste wyjasnienie tego jak i sprawdzenie rozumowania i rozwiazania zadania.


Z powazaniem, M4ksiu.


Edit: Ok, juz widze pierwszy blad. Jesli przesuwamy o kat \(\displaystyle{ \frac{2 \pi}{6}}\), to mamy punkty stale, jesli calosc jest jednokolorowa ( mamy 3 (?) ). Chyba walnalem sie gdzies jeszcze, bo nic dobrego nie wychodzi. To wymaga opinii eksperta. =X
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Zordon »

Ogólnie widać, że wiesz o co chodzi, ale zwróć uwagę, że nie wystarczy patrzeć na obroty, ale trzeba też rozważać symetrie tego sześciokąta. Dlatego bierzemy taką grupę jak napisałem, ma ona \(\displaystyle{ 3\cdot 12=36}\) elementów.

Poza tym, zajrzyj tu: https://www.matematyka.pl/92570.htm
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Hmm, masz racje ( przyszla profesja - stwierdzanie rzeczy oczywistych ). Zauwazylem w jednym z zadan, ktore sprowadzalo sie do obliczenia istotnie roznych kolorowan, ze najpierw liczylismy "wielomian" dla symetrii, nastepnie dla obrotow a dopiero potem skladamy to w calosc.

Jesli juz jestesmy przy tamtej stronie, to od wczoraj wlasciwie jest ona otwarta, natomiast przyklady tam sa troche mniej skomplikowane ( choc moge sie mylic ).


Ok, "przejdzmy sie" po tych symetriach. Mamy 6 symetrii:
1) 3 wzgledem prostej przechodzacej przez dwa przeciwlegle wierzcholki
2) 3 przechodzace przez srodki 2 przeciwleglych bokow

Teraz spojrzmy na oba przypadki:
1) Tu sprawa wyglada nastepujaco. Mamy zawsze 2 punkty stale ( na osi symetrii ), ktore malujemy w dowolny sposob ( \(\displaystyle{ 3^2}\) ). Ponadto mamy przypadki, kiedy 0, 1 lub 2 wierzcholki z jednej strony osi maja swoje lustrzane odpowiedniki po drugiej. Mamy \(\displaystyle{ 3^{2 + k}}\), gdzie \(\displaystyle{ k}\) wskazuje przypadek. Zatem \(\displaystyle{ 3^2 ( 1 + 2 \cdot 3 + 9 ) = 16 \cdot 3^2}\).
2) Ponownie punkty stale wystepuja wtedy, kiedy wierzcholki maja swoje kolorowe, lustrzane odpowiedniki po drugiej stronie osi. Czyli \(\displaystyle{ 3^{k}}\), gdzie \(\displaystyle{ k \in \{ 1, 2, 3 \}}\), czyli \(\displaystyle{ 3( 1 \cdot 3 + 3 \cdot 2 + 3^2 ) = 3 \cdot 18}\).

Notka: Niektore przypadki sa domnozone przez ilosc "miejsc", w ktorych moga sie rozpoczynac. Np. przy 1), kiedy to poza osia moze byc dodatkowo lustrzana para punktow stalych, ta wlasnie para moze znajdowac sie w 2 miejscach - z czego wynika "domnozenie".


Jesli sie nie pomylilem, to teraz mamy \(\displaystyle{ |G| = ( iloscObrotow + iloscSymetriiOsiowych ) * przypadkiWlasciwe}\), czyli, jak juz powiedziales, mamy \(\displaystyle{ |G| = 3 \cdot( 6 + 6 ) = 36}\) ( co jest chyba po prostu wlasciwoscia grupy \(\displaystyle{ D_{2n}, n \in nieparz}\), ze \(\displaystyle{ |G| = 2n \cdot przypadki}\) ). Nastepnie dokonujemy sumowania i dzielenie wedlug wzoru:
\(\displaystyle{ N = \frac{pktStaleObroty + pktStaleSymetrie}{|G|}}\), czyli:
\(\displaystyle{ N = \frac{3^6 + 2 \cdot 3^2 + 3^3 + 3 \cdot ( 16 \cdot 3^2 + 3 \cdot 18 )} \\
N = \frac{ 729 + 18 + 27 + 9 \cdot ( 48 + 18 )}{36} \\
N = \frac{ 774 + 9 \cdot 66 }{ 36 } \\
N = \frac{ 774 + 594 }{ 36 } \\
N = \frac{ 1368 }{ 36 } \\
N = 38}\)


Nie jestem pewien, czy czegos nie ominalem i czy w ogole dobrze policzylem ( watpliwosci w tym temacie chyba juz nigdy mnie nie opuszcza ), ale tak na teraz wyglada moj wynik. Ponowne sprawdzenie i weryfikacja bylyby mile widziane.


Z powazaniem, M4ksiu.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Zordon »

Kłopot w tym, że elementy tej grupy to nie tylko obroty i symetrie, ale też np. element "dodaj 1 do t" oraz "dodaj 2 do t" i inne (które są złożeniami np. obrotu i jednego z tamtych elementow).
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Myslalem, ze z tego wzgledu dzielimy wszystko przez \(\displaystyle{ 3}\) i to zalatwia sprawe ( jako grupa \(\displaystyle{ \mathbb{Z}_3}\) ). W innym wypadku moge sie przyznac do tego, ze sie zgubilem.


Z powazaniem, M4ksiu.-- 30 sie 2010, o 20:39 --Czy ktos moglby wyjasnic jak dokonczyc lub wlasnie dokonczyc zadanie ?
aleksyprycki
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 17 sie 2010, o 14:47
Płeć: Mężczyzna
Lokalizacja: Baranowo
Pomógł: 1 raz

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: aleksyprycki »

Tez chetnie się dowiem - też mam md
------------------------------
mi chodzi głównie co się robi jak mamy działanie takiego złożenia grup - jak wtedy liczyć punkty stałe?
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Chetnie przeszedlbym dalej, ale najpierw dobrze by bylo wiedziec, czy zamieszczona czesc rozwiazania jest dobrze zrobiona. To by bardzo ulatwilo sprawe. Takze prosze o weryfikacje. Dla doswiadczonego uzytkownika teorii ( lematu ) to nie powinno stanowic duzego problemu.


Z powazaniem, M4ksiu.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Zordon »

grupa ma 36 elementów, dla każdego trzeba znaleźć liczbę punktów stałych... jak dotąd tego nie zrobiłeś
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Czyzby moje zapiski nie "wyliczaly" wszystkich punktow stalych dla grupy takiej, ze swiatelka przy przeksztalceniu nie zmieniaja koloru ? Bo o te punkty na tym etapie pytam. =X


Z powazaniem, M4ksiu.


Edit: Moze po prostu zrobilem to zle ? Moze nie robi sie tego w ten sposob, ale skladajac przeksztalcenia ? Nie "wciagnalem sie" w temat skladania i wyliczania punktow stalych, dlatego moze to byc ciezkie do zrobienia z mojej perspektywy. Natomiast jesli taka odpowiedz sie pojawi, to postaram sie poprawic swoje myslenie i rozpisac to poprawnie.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: Zordon »

symetrie są chyba OK, ale np. dla obrotu o \(\displaystyle{ 60}\) stopni mamy dokładnie 3 punkty stałe, nie widzę tego w tamtych obliczeniach...
M4ksiu
Użytkownik
Użytkownik
Posty: 34
Rejestracja: 24 sty 2010, o 17:21
Płeć: Mężczyzna
Lokalizacja: Somewhere and nowhere
Podziękował: 2 razy

Swiecace zaroweczki ( orbity, symetrie itp. )

Post autor: M4ksiu »

Edit: Ok, juz widze pierwszy blad. Jesli przesuwamy o kat \(\displaystyle{ \frac{2 \pi}{6}}\), to mamy punkty stale, jesli calosc jest jednokolorowa ( mamy 3 (?) ). Chyba walnalem sie gdzies jeszcze, bo nic dobrego nie wychodzi. To wymaga opinii eksperta. =X

To jest notka, ktora zostawilem po pierwszych przemysleniach wiadomosc z obrotami. Jest to oczywiscie potem uwzgledniane.


Z powazaniem, M4ksiu.


Edit: Hmm, faktycznie chyba pominalem ten przypadek bezposrednio w obliczeniach. Naturalnie dodam go przy dalszych pracach. Czy natomiast inne przypadki jak i calosc ( odliczajac te wpadke ) sa dobrze "wydedukowane" ?
ODPOWIEDZ