Let $n \geqslant 1$ be a positive integer. Consider a line of $n$ lamps. Initially, some of the lamps are on, and each minute, the lamps that have exactly one neighboring lamp on turn on, and the others turn off (the lamps at the ends have only one neighboring lamp).

For which integers $n$ are we certain that, regardless of the initial configuration of the lamps, they will all be off after a certain time?
If $n$ is even, it is impossible for all the lamps to turn off. Indeed, for this to happen, the second lamp, the fourth, and so on up to the $n$-th would have to be off at the minute before. Similarly, starting from the right, the $(n-1)$-th, the $(n-3)$-th, and so on up to the first.

If $n$ is odd, consider the positions $2, 4, \cdots, n-1$. We can observe that after two minutes, one of these lamps turns on only when one of its neighbors at a distance of 2 is on. Thus, if $n$ does not satisfy the statement, $2n+1$ will not either.

The only remaining cases are integers of the form $2^k - 1$ with $k \geq 1$. To show that these integers satisfy the statement, we proceed by induction on $k$.

Assume the result is true for $k$, then consider the line with $2^{k+1} - 1$ lamps. If we only look at even times, the even-numbered lamps evolve independently of the odd-numbered lamps: that is, the $2^k - 1$ even-numbered lamps evolve as in the original statement, and the $2^k$ odd-numbered lamps evolve as in the original statement if we assume that the lamps at the ends are neighbors of themselves.

It remains to show that if $2^k$ lamps are arranged in a line, and the lamps at the ends are considered neighbors of themselves, then after a certain time all the lamps will turn off regardless of the initial configuration.

One trick is to consider the following problem: $2^{k+1}$ lamps are placed in a circle, and at each minute a lamp turns on if exactly one of its neighbors is on. We show by induction on $k$ that having one lamp on initially forces all the lamps to be off after $k+1$ steps (for $k=0$, the two lamps are doubly neighbors).

Thus, any initial configuration leads to all the lamps being off after $k+1$ steps: indeed, we can write a configuration by noting 1 for a lamp that is on and 0 otherwise. Then the value of a lamp after one step is the sum modulo 2 of its neighbors. Thus, if we have two configurations $A$ and $B$ of the lamps, and we add modulo 2 their associated numbers at each lamp, we get a configuration $C$. If $A$ becomes $A'$, $B$ becomes $B'$, and $C$ becomes $C'$, then $C'$ is the sum of $A'$ and $B'$. We deduce in particular that each configuration disappears completely after $k+1$ steps.

If we have a configuration in our interval of length $2^k$, and we place it in the circle of length $2^{k+1}$ and place its symmetric on the remaining $2^k$ positions, the configuration will preserve its axis of symmetry, and half of the circle will behave like the interval. We have thus shown what we wanted.

## 2 Midway Training

## Statements