# 2006 IMO Shortlist Problems/C1

## Problem

(*France*)
We have lamps in a row, each of them being either *on* or *off*. Every second we simultaneously modify the state of each lamps as follows:

- if the lamp and its neighbours (only one neighbour for or , two neighbours for other ) are in the same state, then is switched off;
- otherwise, is switched on.

Initially, all the lamps are off except the leftmost one which is on.

(a) Prove that there are infinitely many integers for which all the lamps will eventually be off.

(b) Prove that there are infinitely many integers for which the lamps will never be all off.

## Solution

We suppose that is the leftmost lamp. We note that for , in the th second, is on, and is the rightmost lamp which is on. This follows from induction.

**Lemma.** If , then in the th second, are exactly the lamps which are on.

*Proof.* We know that no lamps to the left of are on, so it is enough to show that all the lamps are on. We show this by induction. For the base case, , we note that initially is on. Now, suppose that in the th second, lamps are on. Then in the th second, the only lights which are on are and . At this point, we have symmetry between the lamps and the lamps , which is preserved in every second until is turned on (if there is such a lamp). Thus from the th second to the th second, inclusive, the lamps and behave as independent replicas of the original state. Then by the inductive hypothesis, after th second, the lamps as well as the lamps are all turned on. ∎

Now, from the lemma, it is clear that when we have lamps, for any integer , in the th second, all lamps are turned on, so in the th second, they are all turned off. This proves part (a) of the problem. On the other hand, if we have lamps, for any integer , then in the th second, the lamps will be the only lamps on. This is the mirror image of the state of the lamps in the second second, so the lamps' state must be periodic and there will always be at least one lamp on. ∎

*Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.*