IMO 1993 · Problem 6

There are \(n\) lamps \(L_0,\ldots,L_{n-1}\) in a circle \((n>1)\), where we denote \(L_{n+k}=L_k\). (A lamp at all times is either on or off.) Perform steps \(s_0,s_1,\ldots\) as follows: at step \(s_i\), if \(L_{i-1}\) is lit, switch \(L_i\) from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

(a) There is a positive integer \(M(n)\) such that after \(M(n)\) steps all the lamps are on again;

(b) If \(n=2^k\), we can take \(M(n)=n^2-1\);

(c) If \(n=2^k+1\), we can take \(M(n)=n^2-n+1\).

Official text of the problem. Official problem paper (PDF)

Solution

Represent an illuminated lamp by \(1\) and an extinguished lamp by \(0\), and perform all arithmetic modulo \(2\). The update rule then adds the state of \(L_{i-1}\) to the state of \(L_i\).

After \(t\) steps, immediately before step \(s_t\), record the states in the order \[ L_t,L_{t+1},\ldots,L_{t+n-1}. \] Since \(L_{t-1}=L_{t+n-1}\), performing the next step and recording the states in the new order transforms the vector by \[ T(x_0,x_1,\ldots,x_{n-1}) =(x_1,x_2,\ldots,x_{n-1},x_0+x_{n-1}). \] Thus, writing \(\mathbf1=(1,\ldots,1)\), the recorded vector after \(t\) steps is \(T^t\mathbf1\). All lamps are on exactly when this vector equals \(\mathbf1\).

The map \(T\) is linear and invertible, with \[ T^{-1}(y_0,\ldots,y_{n-1}) =(y_{n-1}+y_{n-2},y_0,\ldots,y_{n-2}). \] Here \(n>1\) ensures that all the indicated coordinates exist.

(a) There are only \(2^n\) possible vectors, so \[ T^a\mathbf1=T^b\mathbf1 \] for some integers \(0\le a<b\). Applying \(T^{-a}\) gives \[ T^{b-a}\mathbf1=\mathbf1. \] Therefore \(M(n)=b-a>0\) has the required property.

To prove the stated values in (b) and (c), we first establish an identity for \(T\). Given any vector \[ v=(b_0,\ldots,b_{n-1}), \] extend its entries recursively by \[ b_{r+n}=b_{r+n-1}+b_r\qquad(r\ge0). \] The definition of \(T\) gives, by induction, \[ T^r v=(b_r,\ldots,b_{r+n-1}). \] Consequently, applying the recurrence to each coordinate yields \[ T^n v=T^{n-1}v+v. \] Since \(v\) was arbitrary, \[ T^n=T^{n-1}+I, \] where \(I\) is the identity map. Set \(S=T^{-1}\). Multiplication by \(T^{-n}\) gives \[ \boxed{S^n=S+I.} \]

We shall also use the identity \[ (A+I)^{2^k}=A^{2^k}+I \] for linear maps over arithmetic modulo \(2\). Indeed, \((A+I)^2=A^2+I\), and repeated squaring proves the identity for every nonnegative integer \(k\).

(b) Suppose \(n=2^k\). Then \[ S^{n^2}=(S^n)^n=(S+I)^n=S^n+I=(S+I)+I=S. \] Since \(S\) is invertible, this implies \[ S^{n^2-1}=I, \qquad\text{hence}\qquad T^{n^2-1}=I. \] In particular, \(T^{n^2-1}\mathbf1=\mathbf1\), proving that we may take \[ M(n)=n^2-1. \]

(c) Suppose \(n=2^k+1\), and put \(q=2^k=n-1\). Then \[ S^{nq}=(S^n)^q=(S+I)^q=S^q+I. \] Multiplying by \(S\) and using \(q+1=n\), we obtain \[ S^{nq+1}=S^{q+1}+S=S^n+S=(S+I)+S=I. \] Therefore \[ T^{nq+1}=I. \] As \(nq+1=n^2-n+1\), all lamps are on after this many steps. Thus we may take \[ M(n)=n^2-n+1. \] This calculation also covers \(k=0\), if allowed, when \(n=2\). All the displayed choices of \(M(n)\) are positive because \(n>1\).

The solution was checked against John Scholes' IMO solution archive (Kalva).