5. Zadatak

Polja ploče dimenzija $N\times N$ obojana su u crno i bijelo tako da su polja koja imaju zajedničku stranicu različite boje i tako da je barem jedno polje u kutu ploče crne boje. U pojedinom koraku odabire se kvadrat dimenzija $2\times2$ i sva četiri polja unutar tog kvadrata mijenjaju boju tako da bijela polja postaju crna, crna postaju siva, a siva postaju bijela.

Odredi sve prirodne brojeve $N>1$ za koje je konačnim nizom opisanih koraka moguće postići da sva polja koja su na početku bila crna budu bijela i da sva polja koja su na početku bila bijela budu crna.

Rješenje

Tvrdimo da su traženi brojevi svi višekratnici broja $3$ .

Uočimo da je za $N=3$ moguće postići da crna postanu bijela i obratno tako da dva puta odaberemo svaki od četiri kvadrata dimenzija $2\times2$ .

Prvi niz odabira na ploči 3×3

Također, za ploču dimenzija $3\times3$ kojoj su polja u kutu i središnje polje bijelo, a ostala polja crna, možemo postići da crna postanu bijela i obratno tako da jednom odaberemo svaki od četiri kvadrata dimenzija $2\times2$ .

Drugi niz odabira na ploči 3×3

Ako $3$ dijeli $N$ , onda ploču možemo podijeliti na disjunktne ploče dimenzija $3\times3$ . Prema prethodnom zaključujemo da za sve takve $N$ možemo postići da crna polja postanu bijela i obratno.

Tvrdimo da ako $3$ ne dijeli $N$ , nije moguće postići da crna polja postanu bijela i obratno. Neka je $N=3K+L$ za $L\in\{1,2\}$ i $K\in\mathbb N$ .

Uočimo da će crno polje postati bijelo ako i samo ako broj koraka u kojima mijenjamo boju tog polja daje ostatak $2$ pri dijeljenju s $3$ . Analogno, bijelo polje će postati crno ako i samo ako broj koraka u kojima mijenjamo boju tog polja daje ostatak $1$ pri dijeljenju s $3$ .

Također možemo uočiti da neki kvadrat ne moramo odabirati više od dva puta jer su boje polja koje dobivamo nakon $3q+r$ koraka jednake bojama koje dobivamo nakon $r$ koraka za $r\in\{0,1,2\}$ i $q\in\mathbb N$ .

Promotrimo prva dva retka ploče dimenzija $N\times N$ i pretpostavimo da je prvo polje u prvom retku crne boje. Kvadrat dimenzija $2\times2$ u prva dva stupca moramo odabrati dva puta. Nakon toga je drugo polje u prvom retku sivo, pa kvadrat u drugom i trećem stupcu moramo odabrati dva puta. Time je postignuto da je drugo polje crno, a treće polje bijelo. Zato zaključujemo da kvadrat u trećem i četvrtom stupcu ne smijemo odabrati. Analogno zaključujemo da kvadrat u četvrtom i petom stupcu moramo odabrati jednom, kvadrat u petom i šestom stupcu jednom, a kvadrat u šestom i sedmom stupcu ne smijemo odabrati.

Na isti način je jednoznačno određeno što moramo činiti sa svim $2\times2$ kvadratima u gornjem lijevom dijelu dimenzija $2\times3K$ , tj. $2\times2$ kvadrate redom moramo odabrati

2,2,0,1,1,0,2,2,0,\ldots

puta, pri čemu je taj niz brojeva periodičan s periodom $6$ .

Bez obzira je li $L=1$ ili $L=2$ , jednoznačno je određeno koliko puta bismo morali odabrati kvadrat dimenzija $2\times2$ u posljednja dva stupca kako bismo postigli da pretposljednje polje u prvom retku promijeni boju iz crne u bijelu ili obratno. No, taj broj se razlikuje od broja potrebnih odabira tog istog kvadrata kako bismo postigli da posljednje polje u prvom retku promijeni boju iz crne u bijelu ili obratno. Time je dokaz završen.