The question states:
In every square of an $n × n$ board there is a lamp. Initially all the lamps are turned off. Touching a lamp changes the state of all the lamps in its row and its column (including the lamp that was touched). Prove that we can always turn on all the lamps and find the minimum number of lamps we have to touch to do this.
How do I complete the proof for the even case below?
My attempt:
If we spit the problem into odd $n \times n$ cases and even $n \times n$ cases we see the following:
Odd:
We can turn every lamp on in a board by simply touching every lamp in one column. Suppose we sequentially touch every lamp in column $C1$. This turns on all lamps in each row (and since they are not affected by consequent moves remain on). The lamps in the column will eventually all be on too because they are affected an odd number of times.
Thus we have a strategy taking $n$ moves. We cannot affect all the lamps in fewer moves and this must be the best strategy for an odd $n$.
Even:
I present a strategy for turning on all lamps:
We can split any $n \times n$ board into blocks of $2\times 2$. For each $2 \times 2$ if we touch each lamp in a clockwise fashion, we turn on all the lamps in that block without affecting all other lamps. We can thus use this strategy for all blocks and turn on all lamps in $n^2$ moves.
Now I have a feeling we cannot beat this strategy (I get this sense because I cannot beat it in the 2×2 case) but am not sure how to prove this strategy cannot be beaten in a more general fashion.
Best Answer
Your intuition is right.
My arguments can be wrapped up more concisely with the machinery of linear algebra, but let us not use it.
Assume that $n$ is even. Suppose we press the $(i,j)$-th light bulb $a_{ij}$ times. We know that double pressing a bulb does no difference from not pressing it at all, so, to guarantee minimal pressing, we assume $a_{ij}$ is in $\{0,1\}$ for all $(i, j) \in \{1, \cdots, n\}^2$.
Under this restriction there are $2^{n^2}$ combinations of pressing the light bulbs, and there are also $2^{n^2}$ configurations of the status of the light bulbs. Therefore, if we can justify that all configurations of the status can be attained, we can guarantee that the only way to light all bulbs on is to press all the light bulbs.
In particular, it suffices to show that we can light up exactly one light bulb on the board.
So, if we do the steps 1, 2, and 3 altogether, then...