A $5\times 5$ square with $+1$ and $-1$

puzzle

This is a problem from the Monthly Contest of the Berkeley Math Circle in 2001/2002.

The Problem

A 5 ×5 square has been dissected into a unit square grid. One of the unit squares has been filled with “−1” and the rest have been filled with “+1”. In each step, one can choose a square, with side at east 2 and its sides parallel to the sides of the grid, and change all the signs in the square. Find all terh possible intial format(s) such that it is possible to get an all “+1” grid in a finite number of steps.

Some comments on the official solution

This puzzle has an official solution here, and states that the only possible initial position is the center of the square. Beggining with a $-1$ anywhere else, it is impossible.

My feeling is that the answer is true, BUT THE PROOF is wrong. I'll try to explain.

First, using $\mod 4$ argument, the solution states that only odd squares movements may affect the total sum of $+1$ and $-1$. So to reach a solution, we must toggle odd squares an odd number of times; so, as only 3×3 and 5×5 are allowed (and all of them involve the center), the center tile have been toggled an odd number of times. So if we begin with a $+1$ we will end with a $-1$.

The solution says that from this arguments follows the answer. BUT I think it is possible to toggle the center piece also with an even square. So this argument fails.

My Question
My feeling is that the argument fails, but the answer is true. But I cannot give a proof.

Can anyone give a complete answer?

Thanks in advance

Best Answer

I agree with you that their argument is not a proof.
Here is my proof.

Consider this pattern of cells:

x . . x .
. x x . x
x . . x .
x . . x .
. x x . x

Every move toggles an even number of the cells marked x. Therefore their sum mod 4 remains constant (I actually prefer to say that the sign of their product remains constant). This means that if the initial -1 is located at one of the x-cells, then it is impossible for the moves to eliminate it - there is always an odd number of x-cells containing a -1.

This pattern works in any orientation, so every cell except for the centre one is such an x-cell. Therefore only the starting pattern with the -1 in the centre cell is solvable.

Edit:
Actually, there is simpler pattern:

x x x x x
x x x x x
. . . . .
x x x x x
x x x x x
Related Question