Cono Sur Mathematical Olympiad

a. It suffices to show an algorithm that leaves exactly one lamp on (afterwards, the same algorithm can be repeated using appropriate translations). We will present two such algorithms.

ALGORITHM 1. Stacking four $3\times 3$ squares we get a $12\times 3$ rectangle, and stacking three $4\times 4$ squares we get a $12\times 4$ rectangle. By overlapping these moves, we get a $12\times 1$ rectangle of lamps that are on.

→ →

In a similar fashion we can make a sequence of moves that switches all lamps inside a $20\times 1$ rectangle (by overlapping $20\times 4$ and $20\times 5$ rectangles), or inside a $15\times 1$ rectangle (by overlapping $15\times 6$ and $15\times 5$ rectangles). Since $\gcd (12,20,15)=1$, it is possible to get a $1\times 1$ square with its lamp on by combining those rectangles. (For example: we turn 40 lamps on using two $20\times 1$ rectangles, then we turn the last 15 lamps off with a $15\times 1$ rectangle, and finally we turn further 24 lamps off by using two $12\times 1$ rectangles.)

ALGORITHM 2. With two $4\times 4$ squares and two $5\times 5$ squares we can achieve that inside a $9\times 9$ square all lamps are on, except for the one on the center. Now, we can divide the $9\times 9$ square into nine $3\times 3$ squares and make moves on them to switch all 81 lamps. This leaves only the central lamp on, as wanted.

b. First we analyze the case where only $3\times 3$ and $5\times 5$ squares are used. We color the columns of the grid with the following pattern: two black columns, one white column, two black, one white, .... Suppose the rows of the grid are labelled, in order, as ..., $-3$, $-2$, $-1$, $0$, $1$, $2$, $3$, .... For each residue $r$ modulo 5 we count how many rows with a label $\equiv r(\mathrm{mod}5)$ have an odd number of black cells with its lamp on. These five numbers are $a,b,c,d,e$. Initially, all of them are equal to 0. A move with a $3\times 3$ square does not alter the parity of these numbers, since each row has either 2 or 0 black cells inside any $3\times 3$ square. A move with a $5\times 5$ square either leaves all parities unchanged or changes all of them (there is one row for each residue $r$, and all of those rows have the same number of black cells). So in both cases we find that $a,b,c,d,e$ are always all even or all odd. Therefore, it is impossible that after a sequence of moves the only lamps that are on are those inside a $2\times 2$ square if this square has 2 white cells and 2 black cells. By taking a translation of the original coloring we can always assume that is the case for our goal $2\times 2$ square. A similar argument works for the remaining two cases. If the squares used are $3\times 3$ and $4\times 4$, then we color the columns with the pattern 2 black, 2 white, 2 black, 2 white, ..., and we classify rows according to their residue modulo 3. If the squares used are $4\times 4$ and $5\times 5$, we use the same coloring as in the previous case and we classify rows modulo 5.