[ edisnp @ 03.01.2011. 17:33 ] @
Svako od jedinicnih polja tablice 3X3 obojeno je jednom od tri boje .
Koliko ima razlicitih bojenja kod kojih su svaka dva susedna jedinicna
polja (tj. polja sa zajednickom stranicom) razlicite boje?
RESENJE:
U tablici postoji 9 jedinicnih polja(Istih) posto imamo tri boje najveci broj
razlicitih kombinacija je 8 po Dirihleovom principu dva polja moraju biti
isto obojena(minimum) najveci broj razlicitih bojenja je osam
nije mi jasno ovaj deo zadatks"Koliko ima razlicitih bojenja kod kojih su svaka dva susedna jedinicna
polja (tj. polja sa zajednickom stranicom) razlicite boje?"
Moze li neko da mi pojasni kako se ovo odredjuje.
[ Fermion @ 03.01.2011. 18:26 ] @
Kakvih 8, ja dobijam da ima 246 bojenja :).

Nije ti jasna postavka zadatka ili šta?

Imaš tablicu 3*3 sa 9 polja i svako obojiš nekom bojom, a pri tom imaš tri boje na raspolaganju. I sad se pita na koliko načina se ova tablica može obojiti a da susedna polja budu obojena različitom bojom. Recimo neka su boje plava, crvena i zelena. Ako je neko polje plavo nijedno polje do njega (sa kojim ima zajedničku stranicu) ne sme da bude plavo. Samo što za svako od polja moraš voditi računa da bojenje bude takvo da za svako polje važi da nijedno njemu susedno polje nije iste boje kao ono samo.
[ edisnp @ 03.01.2011. 19:21 ] @
Pa nije mi jasno kako da nadjem sve moguce nacine
[ edisnp @ 03.01.2011. 19:27 ] @
Nije mi jasno kako da izracunam sve nacine bojenja.
[ Fermion @ 03.01.2011. 19:29 ] @
Pogodnost za nalaženje rešenja je što je tablica 3*3, inače bi zadatak bio znatno teži ako je tablica većih dimenzija. Međutim ovako je najbitnije središnje polje.Središnje polje možemo obojiti na tri načina. Broj polja do središnjeg koja su iste boje je 2,3 ili 4 (pošto imamo tri boje). Ako su sva iste boje onda tu boju možemo birati na dva načina (tri su nam na raspolaganju, ali ne smemo koristi onu kojom obojili središnje polje). Ugaona polja su različite boje od one kojom smo obojili polja susedna središnjem, pa za svako od njih možemo na 2 načina odabrati boju kojom ćemo ih oboijti. A takvih polja je 4, pa imamo za početak 2*2*2*2*2*3 = 96 kombinacija. Ako je do središnjeg polja tri iste boje, onda takvih rasporeda imamo 4, jer na 4 načina možemo izabrati polje koje će imati boju različitu od preostalih i središnjeg. Njegovu boju možemo izabrati na 2 načina (time je naravno određena i boja preostalih susednih temena). Dva ugaona polja onda imaju susedna polja različite boje, pa im je boja već određena. Preostala dva ugaona polja imaju neku od dve moguće boje, jer su im susedna polja iste boje. Tako da je sad ukupan broj kombinacija 2*2*2*2*2*3=96. I ostaje slučaj kada su do središnjeg po dva temena iste boje. E sad je bitno kakav je raspored ovih polja. Imamo dva slučaja: u jednom su ugaonim poljima susedna polja različite boje, a u drugom su im susedna polja iste boje. U prvom slučaju boja ugaonih polja je određena, a pošto se raspored boja polja sudesnih centralnom može dobiti na dva načina, ovde je broj kombinacija 2*3=6 (boja za središnje polje bira se na tri načina). U drugom slučaju imamo 4 rasporeda ovih boja kod polja susednih središnjem. U tom slučaju dva ugaona polja već imaju određenu boju kojom ćemo ih obojiti, a za dva imamo dve kombinacije. Tako da ovde imamo 4*3*2*2=48 bojenja. Ukupan broj bojenja je onda zbir za sve ove kombinacije sa bojenjem, tj. 96+96+6+48=246.