Mathematical Olympiad Rioplatense

A $k$-table has $2k^2+2k$ cells. Imagine them colored black and white in chessboard pattern, with the top right cell black. The white part can be regarded as the union of $k$ white diagonals with $k+1$ cells in each, running from top left to bottom right. Likewise the black part is the union of $k$ black diagonals with $k+1$ cells in each, running from top right to bottom left. Pressing the switch in a cell $C$ can change only the state of cells with the opposite color, and only in diagonals containing cells adjacent to $C$. Moreover, observe that if a diagonal (of the opposite color) is affected by pressing the switch in $C$ then exactly two bulbs in it change state. Consequently the parity of the number of bulbs in state on is constant for every diagonal. All bulbs were off initially. Hence each diagonal contains an even number of bulbs that are on, after any number of moves.

If $k$ is even, it follows that at least one of the $k+1$ bulbs in each of the $2k$ diagonals is off after any number of moves. So at most $(2k^2+2k)-2k=2k^2$ bulbs on can be obtained. (No similar restriction follows for $k$ odd.) We present examples that all $2k^2+2k$ bulbs can be turned on in the odd case, and exactly $2k^2$ bulbs on can be achieved in the even case.

For $k$ odd the procedure involves only switches in odd-numbered rows (from top to bottom). Press the two switches in row 1. In row 3 press the pairs of switches (1,2) and (5,6); in row 5 the pairs (1,2), (5,6) and (9,10). Proceed similarly till row $k$ (which is involved in the process since $k$ is odd): press the first two switches, jump over the next two and so on. For the odd-numbered rows $k+2,k+4,\dots ,2k-1$ the rule is similar. We press two switches and jump over the next two, but starting with the second switch in each of these rows. Every cell in the $k$-table has exactly one neighbor whose switch is pressed. Hence all bulbs will be on eventually.



$k$ odd



$k$ even

Let $k$ be even. We regard the $k$-table $T$ as an extension of a $(k-1)$-table $T^{\prime }$ so that $T$ and $T^{\prime }$ share the same center. The cells of $T$ outside $T^{\prime }$ are precisely the border cells of $T$. Apply to $T^{\prime }$ the sequence of switches described in the odd case. It turns on all cells in $T^{\prime }$. Observe in addition that all border cells of $T$ above the middle horizontal line are also turned on—but the border cells below the middle horizontal line are off. There are $2k$ such cells, so the procedure achieves exactly $2k^2$ bulbs on.