5. Zadatak

U svako polje pravokutne ploče s $3$ stupca i $14$ redaka upisan je simbol $X$ ili $O$ . Za ploču kažemo da je balansirana ako su zadovoljeni sljedeći uvjeti:

svaki $3\times3$ kvadrat sadržava najviše $5$ simbola $X$ i najviše $5$ simbola $O$
u svakom $3\times3$ kvadrati nijedna dijagonala ni redak ni stupac ne sadržavaju tri ista simbola.

Za balansiranu ploču $P$ , centar od $P$ je ploča s $3$ stupca i $12$ redaka dobivena uklanjanjem prvoga i posljednjega retka iz $P$ .

Među svim balansiranim pločama koliko postoji različitih centara?

Za redak na ploči kažemo da je tipa A ako je simbol u lijevom polju retka jednak simbolu u desnom polju. Retci tipa A koji se mogu pojaviti na balansiranoj ploči su

XOX,\ OXO.

Za redak kažemo da je tipa B ako su simboli u lijevom i desnom polju retka međusobno različiti. Retci tipa B koji se mogu pojaviti na balansiranoj ploči su

XOO,\ XXO,\ OOX,\ OXX.

Tvrdimo da se u centru balansirane ploče ne mogu istovremeno pojavljivati retci tipa A i retci tipa B. Pretpostavimo suprotno. Tada postoje dva uzastopna retka od kojih je jedan tipa A i drugi tipa B, te bez smanjenja općenitosti možemo pretpostaviti da dio centra ploče izgleda ovako (upitnici označavaju nepoznate simbole):

\begin{matrix} X & ?_1 & O\\ X & ?_2 & X\\ ?_3 & ?_4 & ?_5 \end{matrix}

Tada su $?_2$ i $?_3$ jednaki $O$ , jer bi inače ploča sadržavala tri pojave simbola $X$ u retku ili stupcu. Međutim, tada se na dijagonali nalaze tri uzastopna simbola $O$ , što je kontradikcija. Dakle, svaka balansirana ploča u centru sadrži samo retke tipa A ili samo retke tipa B.

Prebrojimo koliko različitih centara mogu imati ploče kojima su svi retci u centru tipa A. Primijetimo da je nemoguće da ploča sadrži retke $XOX$ , $OXO$ , $XOX$ zaredom, jer bi dijagonala sadržavala tri uzastopna simbola $X$ . Također, ploča ne smije sadržavati tri uzastopna ista retka. To znači da je centar ploče jedinstveno određen sa prva dva retka u centru:

Ako su prva dva retka različita, npr. $XOX$ i $OXO$ , onda je treći redak jednak $OXO$ , četvrti i peti redak su $XOX$ , šesti i sedmi su $OXO$ , itd. Ukupno dobivamo dva moguća centra ploče u ovom slučaju. Dva retka ploče koji nisu u centru možemo uvijek izabrati tako da ploča ostane balansirana, tako što izaberemo prikladne retke tipa A.
Ako su prva dva retka ista, recimo $XOX$ i $XOX$ , onda su treći i četvrti redak jednaki $OXO$ , peti i šesti su $XOX$ , $\ldots$ Ukupno dobivamo dva moguća centra ploče u ovom slučaju. Primijetimo da dva retka ploče koji nisu u centru možemo uvijek izabrati tako da ploča ostane balansirana, tako što izaberemo prikladne retke tipa A.

Dakle, ako su retci u centru svi tipa A, dobivamo $4$ različita centra ploče.

Pretpostavimo da su sada svi retci u centru ploče tipa B. Tvrdimo da u lijevom i desnom stupcu centralnog dijela ploče ne postoje dva uzastopna jednaka simbola. Pretpostavimo da postoje. Tada bez smanjenja općenitosti možemo pretpostaviti da jedan dio ploče izgleda ovako:

\begin{matrix} ?_1 & ?_2 & ?_3\\ X & ?_4 & O\\ X & ?_5 & O \end{matrix}

Tada je $?_1=O$ i $?_3=X$ , jer bi inače prvi ili zadnji stupac sadržavao tri uzastopna simbola. Primijetimo da je $?_4$ nemoguće odrediti tako da ploča ne sadrži tri uzastopna jednaka simbola na dijagonali, pa dolazimo do kontradikcije. Dakle, simboli u lijevom i desnom stupcu u centru ploče su alternirajući. Bez smanjenja općenitosti pretpostavimo da je prvi simbol u centralnom dijelu lijevog stupca jednak $X$ , kasnije ćemo pomnožiti odgovor dobiven u ovom slučaju s $2$ .

Tada centar ploče izgleda ovako:

\begin{matrix} X & ? & O\\ O & ? & X\\ X & ? & O\\ \vdots & \vdots & \vdots\\ X & ? & O\\ O & ? & X \end{matrix}

Sada vidimo da kako god umjesto simbola $?$ u centralni stupac upišemo simbole $X$ i $O$ na način da ne upišemo tri uzastopna simbola, dobivamo centar balansirane ploče, jer na dijagonali i u retcima ne mogu biti tri uzastopna simbola. Dva retka koji nisu dio centra možemo popuniti na način da u njih upišemo $O*X$ , gdje je $*$ simbol različit od onog koji upišemo u gornji odnosno donji redak centra ploče, te će uz taj odabir ploča biti balansirana.

Dakle, preostaje odrediti na koliko načina je moguće upisati simbole $X$ i $O$ u $12$ polja tako da u nikoja tri uzastopna polja nije upisan isti simbol.

Na $2$ načina možemo upisati jedan simbol $(X,O)$ , te na $4$ načina možemo upisati dva simbola $(XX,XO,OX,OO)$ . Neka je $f_n$ broj načina na koje možemo upisati $n$ simbola. Tada je

f_n=f_{n-1}+f_{n-2}\quad\text{za }n\ge3.

Naime, ako su posljednja dva simbola od njih $n$ jednaki, onda prvih $n-2$ simbola možemo izabrati na $f_{n-2}$ načina, a posljednja dva su jedinstveno određeni. Ako su posljednja dva simbola od njih $n$ različiti, onda prvih $n-1$ simbola možemo izabrati na $f_{n-1}$ načina, a posljednji je jedinstveno određen.

Preostaje izračunati $f_{12}$ . Imamo $f_1=2$ , $f_2=4$ , $f_3=6$ , $f_4=10$ , $f_5=16$ , $f_6=26$ , $f_7=42$ , $f_8=68$ , $f_9=110$ , $f_{10}=178$ , $f_{11}=288$ , $f_{12}=466$ .

Dakle, ukupno ima $2f_{12}+4=936$ različitih centara balansiranih ploča.