2006 IMO Shortlist Problems/C1

Problem

(France) We have $n \ge 2$ lamps $L_1, \dots, L_n$ 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 $\displaystyle {} L_i$ and its neighbours (only one neighbour for $\displaystyle i=1$ or $\displaystyle {i=n}$ , two neighbours for other $\displaystyle i$ ) are in the same state, then $\displaystyle {} L_i$ is switched off;
otherwise, $\displaystyle {} L_i$ is switched on.

Initially, all the lamps are off except the leftmost one which is on.
(a) Prove that there are infinitely many integers $\displaystyle n$ for which all the lamps will eventually be off.
(b) Prove that there are infinitely many integers $\displaystyle n$ for which the lamps will never be all off.

Solution

We suppose that $\displaystyle L_1$ is the leftmost lamp. We note that for $k \le n$ , in the $\displaystyle k$ th second, $\displaystyle L_k$ is on, and is the rightmost lamp which is on. This follows from induction.

Lemma. If $2^k \le n$ , then in the $\displaystyle 2^k$ th second, ${} L_1, \dots, L_{2^k}$ are exactly the lamps which are on.

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

Now, from the lemma, it is clear that when we have $\displaystyle 2^k$ lamps, for any integer $\displaystyle k$ , in the $\displaystyle 2^k$ th second, all lamps are turned on, so in the $\displaystyle 2^k +1$ th second, they are all turned off. This proves part (a) of the problem. On the other hand, if we have $\displaystyle 2^k +1$ lamps, for any integer $k \ge 1$ , then in the $\displaystyle 2^k + 1$ th second, the lamps $\displaystyle {} L_{2^k}, L_{2^k+1}$ 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.

Resources

Page

Toolbox

Search

2006 IMO Shortlist Problems/C1

Problem

Solution

Resources