Q3 Matemática  (IberoAmerican 1994)

Em cada quadrado de uma grade $n\times n$ há uma lâmpada. Se a lâmpada for tocada, ela muda de estado todas as lâmpadas da mesma linha e todas as lâmpadas da mesma coluna (as que estão acesas são apagadas e vice-versa). No início, todas as lâmpadas estão apagadas. Mostre que sempre é possível, com uma sequência adequada de toques, que todas as lâmpadas do quadro se acendam e encontrem, em função de $n$, o número mínimo de toques necessários para acender cada lâmpada.