Q52 Matemática  (IMO Longlists 1992)

Seja $n$ um inteiro $>1$. Em um arranjo circular de $n$ lâmpadas $L_0,\cdots ,L_{n-1}$, cada uma das quais pode estar LIGADA ou DESLIGADA, começamos com a situação em que todas as lâmpadas estão LIGADAS, e então realizamos uma seqüência de etapas, $Ste{p}_0,Ste{p}_1,\cdots$. Se $L_{j-1}$ ($j$ é tomado mod n) está LIGADO, então $Ste{p}_j$ altera o status de $L_j$ (vai de LIGADO para DESLIGADO ou de DESLIGADO para LIGADO), mas não altera o estado de qualquer uma das outras lâmpadas. Se $L_{j-1}$ estiver OFF, então $Ste{p}_j$ não muda nada. Mostre que: (a) Existe um inteiro positivo $M(n)$ tal que após os passos de $M(n)$ todas as lâmpadas acendem novamente. (b) Se $n$ tem a forma $2^k$, então todas as lâmpadas acendem após $n^2-1$ passos. (c) Se $n$ tem a forma $2^k+1$, então todas as lâmpadas acendem após os passos $n^2-n+1$.