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.
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"