Ajmo malo da bojimo

Ajmo malo da bojimo 12.11.2012. u 12:17 · pre 170 meseci #1

1. Na koliko nacina se mogu obojiti temena pravilnog sestougla sa $n$ boja, ako dva bojenja smatramo istim ako:
a) rotacijom jednog obojenog sestougla dobijamo drugi;
b) izometrijom jednog obojenog sestougla dobijamo drugi.

2. Na koliko nacina se mogu obojiti temena pravilnog $p$ -tougla ( $p$ je prost) sa $n$ boja, ako dva bojenja smatramo istim ako rotacijom jednog obojenog $p$ -tougla dobijamo drugi.

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Ajmo malo da bojimo 13.11.2012. u 21:27 · pre 170 meseci #2

Dal' moze ovako prvi:

- oznacimo temena sestougla brojevima 1 do 6, recimo u smeru kazaljke na satu
- napravimo korespodenciju izmedju varijacija sa ponavljanjem n elemenata i temena, tako sto redom boje te varijacije dodelimo temenima sestougla.

Time dobijamo sva moguca bojenja temena, kojih ima $n^6$ pa treba oduzeti koje su fiksne u odnosu ne neku rotaciju. Naravno, mogucih rotacija ima 6 i sto se tice varijacija, mozemo ih gledati kao ciklicno pomeranje boja.

Razmotrimo koja su to bojenja invarijantna na te rotacije. Ako oznacimo jedno bojenje sa abcdef, onda ove rotacije znace sledece jednakosti boje:
1. rotacija za jedno mesto (a,b,c,d,e,f) -> (f,a,b,c,d,e), daje a=b=c=d=e=f
2. rotacija za dva mesta (a,b,c,d,e,f) -> (e,f,a,b,c,d), daje a=c=e i b=d=f (ova bi zahtevala da je n bar 2)
3. rotacija za tri mesta (a,b,c,d,e,f) -> (d,e,f,a,b,c), daje a=d, b=e i c=f (ova bi zahtevala da je n bar 3).

Rotacija za 4 mesta ce dati isto sto i rotacija za 2, a za 5 mesta isto sto i ona za 1.

Dakle, imamo 3 klase bojenja koje su invarijantne u odnosu na rotacije. Prva pomenuta klasa ima $n$ elemenata. U drugoj kao da biramo 2 razlicite boje od n i da ih mozemo postaviti na 2 razlicita nacina, sto bi trebalo da je $2 \cdot {n \choose 2}$ . Slicno, treca ima $3 \cdot {n \choose 3}$ elemenata. Dakle, sve u svemu, to bi bilo $n^6 - 2 \cdot {n \choose 2} - 3 \cdot {n \choose 3}$ (u slucaju da je $n \geq 3$ ).

Re: Ajmo malo da bojimo 16.11.2012. u 12:13 · pre 169 meseci #3

Pogresno sam razumeo zadatak, umesto da odbacujem one koji su invarijantni, treba brojati klase varijacija koje su dobijene relacijom "b je nastao od a rotacijom".
Da se ne bih previse raspisivao, evo dobio sam nesto novo, pa ako se pokaze tacnim, mogu dati kompletno objasnjenje (zadatak 1a))

${1 \over 6} \cdot \left( n^6 + 5n + 5 \cdot n \cdot (n-1) + n \cdot (n-1) \cdot (n-2) \right)$ .

Re: Ajmo malo da bojimo 16.11.2012. u 16:01 · pre 169 meseci #4

Jeste, sad je dobro. Iliti $\frac{1}{6}\Biggl(n^6+n^3+2n^2+2n\Biggr)$ (sto ne sredi lepo, nego me teras da racunam :))

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Ajmo malo da bojimo 16.11.2012. u 23:58 · pre 169 meseci #5

Imas pravo, mogao sam da sredim, ali sam toliko sredjivao da bih dosao dovde, da mi je izgledalo veoma sredjeno :) Uostalom, sto samo ja da se mucim? :)
Elem, ja stvarno ne znam da li ovde ima zainteresovanih da vide izvodjenje, pa ne znam koliko ima smisla da to prezentiram? Mada sam kao rekao da cu napisati... Pa, ako neko procita od pocetka do kraja, nek' mahne u mom pravcu, da znam da je bilo i takvih.

Kao sto rekoh, radi se o klasama ekvivalencije relacije "b nastaje rotacijom od a" u skupu varijacija n elemenata na 6 mesta, sa ponavljanjem. Nisam to bas tako tvrdo radio, ali to jeste apstrakt koji sam koristio. U grubo, postoje neke varijacije u kojima svih 6 rotacija (racunajuci i identitet) predstavljaju razlicite varijacije ("regularne"), i cine jedan skup klasa ciji broj elemenata treba deliti sa 6. One druge, koje sam vec ranije analizirao, stvaraju manje razlicitih varijacija.

Evo sada opisa tih "neregularnih" varijacija, bez ulazenja potpuno u detalje:

- oblik "aaaaaa" ima samo jedan element u klasi, a takvih klasa ima n; dakle ukupno n varijacija;

ako imamo bar 2 elementa, $a \neq b$ :
- oblik "ababab" ima 2 elementa u klasi, a klasa ima $n \choose 2$ ; ukupno $n(n-1)$ varijacija;
- oblik "aabaab" ima 3 elementa u klasi, a klasa ima $n(n-1)$ ; ukupno $3n(n-1)$ varijacija;

ako imamo bar 3 razlicita elementa, $a, b, c$ :
- oblik "abcabc" ima 3 elementa u klasi, a klasa ima $2 \cdot {n \choose 3}$ ; ukupno $6 \cdot {n \choose 3} = n(n-1)(n-2)$ varijacija;

Naravno, svih varijacija ima $n^6$ a broj regularnih dobijamo kao razliku ukupnog broja varijacija i broja neregularnih. Ovaj broj se deli sa 6, sto je zapravo zajednicki broj elemenata po klasi, i konacno treba dodati broj neregularnih klasa:

${1 \over 6} \left( n^6 - n - n(n-1) - 3n(n-1) - n(n-1)(n-2) \right) + n + n(n-1) + {n \choose 2} + 2 \cdot {n \choose 3}$ sto posle sredjivanja daje formulu koju sam naveo.

Interesantno je da formula "radi" i za n=1 i za n=2.

Re: Ajmo malo da bojimo 24.01.2013. u 17:07 · pre 167 meseci #6

Nema razloga da ja previse tupim, kad postoji lepo ispisano resenje. Naime, ova dva zadatka su sa vezbi iz predmeta Algebre 2 i mogu se naci (uradjeni) OVDE (zadaci 36. i 37.)
Meni je bilo interesantno, pa sam zato postavio, a Darko je demonstrirao i drugaciji nacin resavanja problema.

Zanimljivo, pricu oko [url=http://www.artofproblemsolving.com/Wiki/index.php/Burnside's_Lemma]Bernsajdova_lema[/url] se moze naci i u zbirci "Kombinatorika" Pavla Mladenovica.

I zasto ne radi linkovanje u drugom slucaju?

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Ajmo malo da bojimo 25.01.2013. u 09:00 · pre 167 meseci #7

U je, da li sam ja uopste polozio taj predmet? :) Iako je analiza manje vise slicna kao ono sto sam ja radio, sam racun je drugaciji, a ovo moje resenje je kao sto bi uradio neki spretniji srednjoskolac :)

Forum kao aplikacija na telefonu

Srodne teme