5. Zadatak

Dana je ploča $n\times n$ , obojana poput šahovske, pri čemu je gornje lijevo polje crne boje. Azra u svakom koraku bira šest polja ploče koja tvore $2\times3$ ili $3\times2$ pravokutnik i sadrže točno tri bijela polja, te ta tri polja zacrni. Za koje $n$ Azra može postići da sva polja budu crne boje?

Traženi $n$ su oblika $6k-5$ , $6k-1$ i $6k$ , za proizvoljan $k\in\mathbb N$ .

Kako se u svakom koraku broj bijelih polja smanji za $3$ , zaključujemo da je broj bijelih polja na ploči prije prvog koraka nužno djeljiv s $3$ .

Ako je $n$ paran, tada na početku ploča sadrži $\frac{n^2}{2}$ bijelih polja. To je djeljivo sa $3$ kada je i $n$ djeljiv sa $3$ , pa je zato u tom slučaju nužno $n=6k$ , $k\in\mathbb N$ .

Ako je $n$ neparan, tada na početku ploča sadrži

\frac{n^2-1}{2}=\frac{(n-1)(n+1)}2

bijelih polja. Taj broj djeljiv je sa $3$ čim $n$ nije djeljiv s $3$ . Uzimajući u obzir i to da je neparan, $n$ je nužno oblika $6k-1$ ili $6k-5$ , $k\in\mathbb N$ .

Dokažimo da za sve takve $n$ Azra može obojiti sva polja u crno.

U slučaju $n=6k$ podijelimo ploču na $2\times3$ pravokutnike bez zakretanja. Azra može izvesti jedan korak na svakom od tih pravokutnika (jer svaki od njih sadrži točno tri crna i tri bijela polja), te će cijela ploča postati crna budući da je svako polje ploče pokriveno barem jednim pravokutnikom.

Za neparne $n$ tvrdnju ćemo dokazati indukcijom: za svaki $k\in\mathbb N$ , ploče oblika $(6k-5)\times(6k-5)$ i $(6k-1)\times(6k-1)$ mogu se obojiti u crno u konačno mnogo koraka.

Za bazu indukcije uzimamo $k=1$ . U slučaju $n=6\cdot1-5=1$ Azra ne treba izvesti nijedan korak, dok u slučaju $n=6\cdot1-1=5$ Azrin odabir pravokutnika vidimo na slici.

Baza indukcije za ploču 5 puta 5

Pretpostavimo da postoji $k\in\mathbb N$ takav da Azra može obojiti cijelu ploču (bilo $(6k-5)\times(6k-5)$ , bilo $(6k-1)\times(6k-1)$ ) u crno u konačno mnogo koraka, i dokažimo tvrdnju za $k+1$ .

U oba slučaja, za $k+1$ ploča je veća za $6$ redova i $6$ stupaca. Podijelimo tu ploču $(n+6)\times(n+6)$ na $5$ dijelova kao na slici.

Korak indukcije

Kvadrat dimenzija $n\times n$ u sredini, prema pretpostavci indukcije, možemo obojiti u crno u konačno mnogo koraka.

Kako je $n$ neparan, broj $n+3$ je paran. Zato svaki od pravokutnika $3\times(n+3)$ možemo podijeliti na $\frac{n+3}{2}$ pravokutnika oblika $3\times2$ , te na svakom izvesti jedan korak.

Time je korak indukcije završen, a time i dokaz tvrdnje s početka rješenja.