IMO shortlist problem-need hints to carry on with this solution. There are $n$ lamps $L_1,....,L_n$ in a row, each on or off. After each second, we simultaneously modify the state of each lamp as follows:
1.) If $L_i$ is in the same state as each of its neighbours, it is switched off(remains off if it was already off)
2.) If $L_i$ is in a different state to atleast one of its neighbours, it is switched on(remains on if it was already on)
Prove that there are infinite values of $n$ for which all lamps eventually turn off, as well as infinite values of $n$ for which all lamps never turn off, if initially all lamps except the leftmost $L_1$ are off.
Solution:
we define $f(n,k)$ as the number of lamps that are off after $k$ seconds.
As we actually carry out the algorithm, we note:
$f(n,0)$ $=$ $n - 1$
$f(n,1)$ $=$ $n - 2$
$f(n,2)$ $=$ $n - 2$
$f(n,3)$ $=$ $n - 4$
$f(n,4)$ $=$ $n - 2$
$f(n,5)$ $=$ $n - 4$
$f(n,6)$ $=$ $n - 4$
$f(n,7)$ $=$ $n - 8$
$f(n,8)$ $=$ $n - 2$
As such, we guess $f(n,k)$ is of the form $n - 2^m$, where $2^m$ is some power of $2$ if k isn't a power of $2$, and $n - 2$ if $k$ is a power of $2$. Note, if this claim is true, it simultaneously proves both parts, since we get that all $n$ that are not powers of $2$ will never have $f(n,k)$ reach $0$(the number of bulbs that are off can't be negative) and, all $n$ that are powers of $2$ can reach zero. Now, we also consider the lamps as sequences of letters $O$ and $F$ and note that any transition from $F$ to $O$ or $O$ to $F$ turns into two $O's$. This would seem to imply that there is always an even number of bulbs that are on, but there can also transitions of the form $OFO$ which turn into $OOO$. It is true then that the number of bulbs that are on could be expressed in the form $2q + 3p$, but that's not good enough, since every integer except $1$ can be expressed in that form. I need hints on how to prove that claim.
 A: (Getting one more old question off the unanswered list.)
We can represent each possible state of $L_1,\ldots,L_n$ by a bit string $b_1\ldots b_n$ of length $n$, where $b_k=1$ if $L_k$ is on, and $b_k=0$ if $L_k$ is off. For $k\in\Bbb N$ let $\beta_n^{(k)}$ be the bit string representing the state of the lights $L_1,\ldots,L_n$ after $k$ seconds, so that $\beta_n^{(0)}=10^{n-1}$, where for $b\in\{0,1\}$ and $\ell\in\Bbb Z^+$ we write
$$b^\ell=\underbrace{bb\ldots bb}_{\ell\,b\text{s}}\,.$$
A modest amount of computation suggests the following theorem.

Theorem. Let $m\in\Bbb Z^+$, and let $n=2^m$. Then
$$\begin{align*}
(i)&\quad\beta_n^{(n-1)}=1^n\,;\\
(ii)&\quad\beta_n^{(n)}=0^n\,;\text{ and}\\
(iii)&\quad\beta_{n+1}^{(2n+1)}=\beta_{n+1}^{(1)}=110^{(n-1)}\,.
\end{align*}$$

Suppose that the theorem is true; $(ii)$ says that when $n=2^m$ for some $m\in\Bbb Z^+$, all $n$ lights are switched off after $n$ seconds, and clearly there are infinitely many such $n$. Next, note that if $\beta_{n+1}^{(k)}=0^{n+1}$ for some $k\in\Bbb N$, then $\beta_{n+1}^{(\ell)}=0^{n+1}$ for all $\ell\ge k$. (I.e., once all $n+1$ lights are off, they remain off thereafter.) However, it follows from $(iii)$ by an easy induction on $k$ that $\beta_{n+1}^{(2k(n-1)+1)}=110^{n-1}\ne 0^{n+1}$ for all $k\in\Bbb N$. That is, the lights will never all be off simultaneously if $n=2^m+1$, and of course there are infinitely many such $n$. (One can in fact show in this case that every state after the first will have at least two lights on.) Thus, we need only prove the theorem in order to establish the desired result. I will sketch a proof.

It’s useful first to observe that if $0\le k\le n-1$, and $\beta_n^{(k)}=b_1\ldots b_n$, then $b_{k+1}$ is the rightmost $1$ in $\beta_n^{(k)}$, i.e., $b_{k+1}=1$, and $b_\ell=0$ for $k+1<\ell\le n$; this is easily shown by a finite induction on $k$.
We prove $(i)$ by induction on $m$; it clearly holds for $m=1$. Suppose that it holds for some $m\in\Bbb Z^+$, and let $n=2^m$. Then $\beta_{2n}^{(n-1)}=1^n0^n$, so $\beta_{2n}^{(n)}=0^{n-1}110^{n-1}$. The rules for passing from one state to the next are bilaterally symmetric, and with a little thought it follows from this that for $k=n,\ldots,2n-1$, the bit strings $\beta_{2n}^{(k)}$ are symmetric. That is, if $\beta_{2n}^{(k)}=b_1^{(k)}\ldots b_{2n}^{(k)}$, then $b_1^{(k)}\ldots b_n^{(k)}$ is the reversal of $b_{n+1}^{(k)}\ldots b_{2n}^{(k)}$.
Now suppose that $n\le k<2n-1$; $b_n^{(k)}=b_{n+1}^{(k)}$, so whether $b_n^{(k+1)}=b_n^{(k)}$ depends solely on $b_{n-1}^{(k)}$, and whether $b_{n+1}^{(k+1)}=b_{n+1}^{(k)}$ depends solely on $b_{n+2}^{(k)}$. This implies that $b_{n+1}^{(k)}\ldots b_{2n}^{(k)}=\beta_n^{k-n}=$ whenever $n+1\le k\le 2n-1$; in particular, $b_{n+1}^{(2n-1)}\ldots b_{2n}^{(2n-1)}=1^n$, and therefore $\beta_{2n}^{(2n-1)}=1^{2n}$, as desired. By induction $(i)$ holds for all $m\in\Bbb Z^+$.
Clearly $(i)$ implies $(ii)$ for any $m\in\Bbb Z^+$.
To prove $(iii)$, note first that it follows from $(i)$ that $\beta_{n+1}^{(n-1)}=1^n0$ and hence that $\beta_{n+1}^{(n)}=0^{n-1}11$. This is the reversal of $\beta_{n+1}^{(1)}=110^{n-1}$, so $\beta_{n+1}^{(n+k)}$ must be the reversal of $\beta_{n+1}^{(k+1)}$ for $0\le k<n$. In particular, $\beta_{n+1}^{(2n-1)}$ is the reversal of $\beta_{n+1}^{(n)}=0^{n-1}11$, i.e., $\beta_{n+1}^{(2n-1)}=110^{n-1}=\beta_{n+1}^{(1)}$, as desired.

