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?
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$.
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 2x2 case) but am not sure how to prove this strategy cannot be beaten in a more general fashion.