# Spring 2018, problem 64

We have $n \geq 2$ lamps $L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $L_{i}$ and its neighbors (only one neighbor for $i = 1$ or $i = n$, two neighbors for other $i$) are in the same state, then $L_{i}$ is switched off; Ð otherwise, $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 $n$ for which all the lamps will eventually be off. $(b)$ Prove that there are infinitely many integers $n$ for which the lamps will never be all off.

Claudio
3 years ago

The key-idea is that first of all the ending one doubles; then in some further steps the couple of ones (again embedded in a null string) moves leftwards. In particular, let $S(j)$ be the string of lamps at the time $T=j$ ($j=0, 1, ...$ seconds). For $h,n$ such that $h$<<$n$ we get that the string $S(2^h-1)$ starts with all zeroes and ends with $2^h-1$ ones ; the following string, $S(2^h)$, starts again with some zeroes and ends with two ones and $2^h-1$ zeroes. As easy consequences we get:

(a) When $n=2^{k+1}$, the string $S (2^{k+1})$ is the null string.

(b) When $n=2^{k+1}-1$, for no $m$ the string $S(m)$ is the null string: at the n-th step we get a couple of ones on the left, followed by all zeroes; and the history repeates "at the mirror"