6. Zadatak

Prvo rješenje.

Za $i\in\{1,2,3,4\}$ definirajmo skupove

$$A_i=\{\text{bojanja u kojima su polja }i,\ i+1,\ i+2\text{ obojana s 3 različite boje}\}.$$

Zanima nas koliko elemenata ima skup $A_1^c\cap A_2^c\cap A_3^c\cap A_4^c$.

Ukupan broj svih mogućih bojanja polja u tri boje je $3^6$. Po formuli uključivanja-isključivanja vrijedi

$$\begin{aligned} |A_1^c\cap A_2^c\cap A_3^c\cap A_4^c| &=3^6-\sum_{i=1}^4|A_i|+\sum_{i<j}|A_i\cap A_j|\\ &\quad-\sum_{i<j<k}|A_i\cap A_j\cap A_k| +|A_1\cap A_2\cap A_3\cap A_4|. \end{aligned}$$

Treba izračunati koliko pojedini skup u formuli ima elemenata.

Svaki skup $A_i$ ima $3\cdot2\cdot1\cdot3^3$ elemenata jer imamo $3$ mogućnosti za boju polja $i$, $2$ za boju polja $i+1$ i preostala boja ide na polje $i+2$. Preostala $3$ polja možemo obojati u bilo koju boju.

Za $i\in\{1,2,3\}$ skupovi $A_i\cap A_{i+1}$ imaju po $3\cdot2\cdot1\cdot3^2$ elemenata jer imamo $3$ mogućnosti za boju polja $i$, $2$ za boju polja $i+1$ i preostala boja ide na polje $i+2$. Polja $i$, $i+3$ moraju biti obojana istom bojom, a preostala $2$ polja možemo obojati u bilo koju boju.

Skupovi $A_1\cap A_3$, $A_2\cap A_4$ imaju po $3\cdot2\cdot1\cdot2\cdot3$ elemenata jer imamo $3\cdot2\cdot1$ mogućnosti za boje prva $3$ polja, četvrto polje ne smije imati istu boju kao treće polje i time je boja petog polja jednoznačno određena. Preostalo šesto polje možemo obojati u bilo koju boju.

Skup $A_1\cap A_4$ ima $6\cdot6$ elemenata jer imamo $6$ mogućnosti za boje prva $3$ polja i $6$ mogućnosti za boje zadnja $3$ polja.

Skupovi $A_1\cap A_2\cap A_3$ i $A_2\cap A_3\cap A_4$ imaju po $6\cdot3$ elemenata jer imamo $6$ mogućnosti za boje prva $3$ polja čime su boje četvrtog i petog polja jednoznačno određene. Preostalo šesto polje možemo obojati u bilo koju boju.

Skupovi $A_1\cap A_2\cap A_4$ i $A_1\cap A_3\cap A_4$ imaju po $6\cdot2$ elemenata jer imamo $6$ mogućnosti za boje prva $3$ polja čime je boja četvrtog polja jednoznačno određena, a za zadnja $2$ polja imamo $2$ mogućnosti (kao za skupove $A_1\cap A_3$, $A_2\cap A_4$).

Skup $A_1\cap A_2\cap A_3\cap A_4$ ima $6$ elemenata jer polja $i$, $i+3$ moraju biti iste boje za $i\in\{1,2,3\}$.

Dakle, broj traženih bojanja iznosi

$$3^6-4\cdot6\cdot3^3+3\cdot6\cdot3^2+2\cdot6\cdot6+6\cdot6 -2\cdot6\cdot3-2\cdot6\cdot2+6=297.$$

Drugo rješenje.

Svako bojanje niza s tri boje tako da ne postoje tri uzastopna polja obojena trima različitim bojama ćemo zvati dobro. Ako su zadnja dva polja iste boje, reći ćemo da je bojanje tipa 1, a ako su zadnja dva polja različite boje, reći ćemo da je bojanje tipa 2.

Neka je $a_n$ broj dobrih bojanja $n$ polja tipa 1 i $b_n$ broj dobrih bojanja $n$ polja tipa 2. Zanima nas koliko je $a_6+b_6$.

Odredimo rekurzivne relacije za $a_n$ i $b_n$. Prvo, vrijedi $a_{n+1}=a_n+b_n$. Naime, kako su polja $n$, $n+1$ iste boje, svako dobro bojanje $n+1$ polja dolazi od jedinstvenog dobrog bojanja $n$ polja.

Promotrimo sada dobro bojanje $n+1$ polja tipa 2. Ako su polja $n-1$, $n$ iste boje, tada polje $n+1$ može biti obojano u $2$ boje. Ako su polja $n-1$, $n$ različite boje, tada polje $n+1$ mora biti obojano kao i $n-1$. Stoga je $b_{n+1}=2a_n+b_n$.

Kako je $a_2=3$ i $b_2=6$, uz ove relacije dobivamo da je $a_6=123$, $b_6=174$. Stoga je broj dobrih bojanja jednak $a_6+b_6=297$.