IMO 1993 SL 17

Origin: NET

Problem

Let n be an integer greater than 1. In a circular arrange- ment of n lamps L0, . . . , Ln−1, each one of that can be either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, Step0,Step1,. . . . If Lj−1 (j is taken mod n) is ON, then Stepj changes the status of Lj (it goes from ON to OFF or from OFF to ON) but does not change the status of any of the other lamps. If Lj−1 is OFF, then Stepj does not change anything at all. Show that: (a) There is a positive integer M(n) such that after M(n) steps all lamps are ON again. (b) If n has the form 2k, then all lamps are ON after n2 −1 steps. (c) If n has the form 2k + 1, then all lamps are ON after n2 −n + 1 steps.

Solution

We introduce the rotation operation Rot to the left by one, so that Stepj = Rot−j ◦Step0 ◦Rotj. Now writing Step∗= Rot ◦Step0, the problem is transformed into the question whether there is an M(n) such that all lamps are ON again after M(n) successive applications of Step∗. We operate in the field Z2, representing OFF by 0 and ON by 1. So if the status of Lj at some moment is given by vj \inZ2, the effect of Stepj is that vj is replaced by vj +vj−1. With the n-tuple v0, . . . , vn−1 we associate the polynomial P(x) = vn−1xn−1 + v0xn−2 + v1xn−3 + \cdot \cdot \cdot + vn−2. By means of Step∗, this polynomial is transformed into the polynomial Q(x) over Z of degree less than n that satisfies Q(x) \equivxP(x) (mod xn + xn−1 + 1). From now on, the sign \equivalways stands for congruence with this modulus. (i) It suffices to show the existence of M(n) with xM(n) \equiv1. Because the number of residue classes is finite, there are r, q, r < q such that xq \equivxr, i.e., xr(xq−r −1) = 0. One can take M(n) = q −r. (Or simply note that there are only finitely many possible configurations;

since each operation is bijective, the configuration that reappears first must be ON, ON, . . . , ON.) (ii) We shall prove that if n = 2k, then xn2−1 \equiv1. We have xn2 \equiv (xn−1 + 1)n \equivxn2−n + 1, because all binomial coefficients of order n = 2k are even, apart from the first one and the last one. Since also xn2 \equivxn2−1 + xn2−n, this is what we wanted. (iii) Now if n = 2k + 1, we prove that xn2−n+1 \equiv1. We have xn2−1 \equiv (xn+1)n−1 \equiv(x + xn)n−1 \equivxn−1 + xn2−n (again by evenness of binomial coefficients of order n−1 = 2k). Together with xn2 \equivxn2−1+ xn2−n, this leads to xn2 \equivxn−1.