Q12 Matemática  (IMO Shortlist 1993)

Seja $n>1$ um inteiro. Em um arranjo circular de $n$ lâmpadas $L_0,\dots ,L_{n-1},$ cada uma das quais pode ser LIGADA ou DESLIGADA, começamos com a situação em que todas as lâmpadas estão LIGADAS e, em seguida, executamos uma sequência de passos, $Ste{p}_0,Ste{p}_1,\dots .$ Se $L_{j-1}$ ($j$ é tomado mod $n$) está ON então $Ste{p}_j$ muda o estado de $L_j$ (vai de ON para OFF ou de OFF para ON), mas não altera o estado de nenhuma das outras lâmpadas. Se $L_{j-1}$ estiver OFF então $Ste{p}_j$ não muda nada. Mostre que: (i) Existe um inteiro positivo $M(n)$ tal que após os passos de $M(n)$ todas as lâmpadas acendem novamente, (ii) Se $n$ tem a forma $2^k$ então todos os as lâmpadas acendem após $n^2-1$ passos, (iii) Se $n$ tem a forma $2^k+1$ então todas as lâmpadas acendem após $n^2-n+1$ passos.