Ciao. Fact 1 n moves are necessary. With less than n moves, there exist at least a row and a column without touched lamps. The lamp at the crossing is still off. Fact 2 If n is odd, n moves are sufficient. Just touch all the lamps in a row, to lit them all. Fact 3.0 It is useless to touch a lamp twice. Obvious. Fact 3.1 If there is a solution, then n^2 moves are sufficient. From now on, WLOG, I suppose no lamp is touched twice. Changing the order of moves doesn't change the result, so if X is the set of subsets of lamps, I can define f: X --> X, s.t. given a subset A, f(A) is the set of lamps lit after touching exactly once the lamps in A. X is finite. For the case of n even, I will prove f is injective by proving Fact 4 If n is even, f is surjective. Infact, choose a lamp L. Touch exactly the lamps in the same column or row of L. The result is that you lit L, and no other lamps. Now, choose a set of lamps A. You can lit exactly the lamps of A by repeating the procedure described for every lamp in A, so every configuration is attainable and f is surjective. Fact 5 If n is even, n^2 moves are necessary. f is bijective, so there exists a unique solution. But touching all the lamps IS a solution. [] As a remark, in the case of n even, you can see that f(f(A)) = A, so there is a very simple way to calculate the minimal sequence of moves for every desired configuration. M.

Generalization: Consider an array of size $m\times{n}$. If both $m$, $n$ are odd then minimum number of steps = $min(m,n)$ obtained by touching each of the buttons along the side containing the $min(m,n)$ buttons. If only one of the sides is odd say $m$, then minimum number of steps = $m$, obtained by touching each of the buttons along the side containing m buttons. If both $m$ and $n$ are even, then one way to alter all lights to all-ON state is to touch each of the $m.n$ buttons EXACTLY ONCE sequentially going from one row/column to the next or in any other order. We shall prove that minimum number of steps = $m.n$ when both $m$, $n$ are even. To prove the above claim it suffices to prove that no button can be left untouched. Assume that a button is left untouched, then this button will be turned to ON state only if there are a total of Odd number of touches along the row and column containing this button. So either the row or column (say row) containing this button must have odd number of touches and the other (say column) must have an even number of touches. Let us label this row as $R$ and column as $C$. Now, each button in $C$ needs to have Odd number of touches in total, so each row of the matrix obtained after excluding $C$ and $R$ must have an Odd number of touches. This matrix has the dimensions of $m-1\times{n-1}$, so total number of touches in this matrix must be odd $-- (1)$ Now, each button in $R$ needs to have Odd number of touches in total, so each column of the matrix obtained after excluding $C$ and $R$ must have an even number of touches, so total number of touches in this matrix must be even $-- (2)$ From $(1)$ and $(2)$ we have a contradiction.