JBMO 2008 problema 4

[Omer Cerrahoglu]

Se da un patrat 4x4 in care toate patratelele unitate sunt colorate in alb. Doua patratele se numesc vecine daca au o latura comuna. O mutare consta in alegerea unui patratel si schimbarea culorii lui si a patratelelor vecine in alb, daca initial erau negre, sau in negru, daca initial erau albe. Sa se determine toate numerele naturale nenule \( n \) pentru care exista o secventa de \( n \) mutari dupa care sa obtinem 16 patratele negre.

[Sorin]

Deasupra celor patru patratele de pe linia de sus inscriem literele A, B, C, D, iar in stanga celor patru patratele de pe coloana laterala scriem cifrele 1, 2, 3, 4. In acest fel fiecare patratel unitate va avea o coordonata, intr-un fel ca pe tabla de sah. De exemplu, patratelul A1 este patratelul aflat in coltul din stanga sus. Fac asta ca sa ma intelegeti.
Coloram pe rand patratelele B1, A3, C4 si D2. Imaginile se vor imbina perfect si culoarea tuturor celor 16 patrate va deveni neagra dupa exact 4 mutari. Deci n poate lua valoarea 4.

[Laurian Filip]

A 4x4 table is divided into 16 white unit square cells. Two cells are called neighbors if they share a common side. A move consists in choosing a cell and the colors of neighbors from white to black or from black to white. After exactly n moves all the cells were black. Find all possible values of n.

[Sorin]

Oricum, avem nevoie de cel putin patru mutari pentru ca o mutare coloreaza maxim 5 patratele (un patrat are 4 laturi), iar \( 3 \cdot 5 \) < 16. Dar \( n \leq 5 \), deoarece cu o mutare vom colora cel putin trei patratele, iar \( 3 \cdot 6 \) > 16.
Acum vom demonstra ca \( n \) nu poate fi 5. Pentru a fi 5, trebuie sa coloram patru patratele cu 2 vecini si un patrat cu 3 vecini. Insa exista doar 4 patratele cu 2 vecini, cele 4 colturi ale patratului mare. Daca le coloram doar centrul patratului, un patrat 2 x 2 va ramane alb. Dar pe el nu-l putem face negru cu o singure mutare.
Pentru n=4 am dat un exemplu de colorare mai sus.