Croatian Mathematical Olympiad 2010 Problem M-2

Na svakom polju ploče $n \times n$ ($n \geqslant 2$) nalazi se žarulja koja može biti upaljena ili ugašena.

U svakom koraku biramo jedan kvadrat $2 \times 2$ na toj ploči i unutar njega sve upaljene žarulje ugasimo, a ugašene upalimo. Za raspored upaljenih žarulja kažemo da je dobar ako se može postići da, počevši od njega, nakon konačno mnogo koraka, sve žarulje budu ugašene.

a) Dokaži da raspored prikazan na slici nije dobar. (Prikazan je položaj svih upaljenih žarulja na ploči $10 \times 10$.)

b) Koliko bi, u tom primjeru, minimalno dodatnih žarulja na početku trebalo upaliti da raspored bude dobar?

c) Odredi broj svih mogućih dobrih početnih rasporeda za $n \times n$ ploču.