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.