IMO 2006 Shortlisted Problems

a. Experiments with small $n$ lead to the guess that every $n$ of the form $2^k$ should be good. This is indeed the case, and more precisely: let $A_k$ be the $2^k\times 2^k$ matrix whose rows represent the evolution of the system, with entries $0,1$ (for off and on respectively). The top row shows the initial state $[1,0,0,\dots ,0]$; the bottom row shows the state after $2^k-1$ steps. The claim is that: $$\text{The bottom row of }{A}_k\text{ is }[1,1,1,\dots ,1]\text{.}$$ This will of course suffice because one more move then produces $[0,0,0,\dots ,0]$, as required.

The proof is by induction on $k$. The base $k=1$ is obvious. Assume the claim to be true for a $k\ge 1$ and write the matrix $A_{k+1}$ in the block form \left($$\begin{array}{cc}{A}_k& O_k\\ B_k& C_k\end{array}$$\right) with four $2^k\times 2^k$ matrices. After $m$ steps, the last $1$ in a row is at position $m+1$. Therefore $O_k$ is the zero matrix. According to the induction hypothesis, the bottom row of $[A_k{O}_k]$ is $[1,\dots ,1,0,\dots ,0]$, with $2^k$ ones and $2^k$ zeros. The next row is thus $$[\underset{2^k-1}{\underbrace{0,\dots ,0}},1,1,\underset{2^k-1}{\underbrace{0,\dots ,0}}]$$ It is symmetric about its midpoint, and this symmetry is preserved in all subsequent rows because the procedure described in the problem statement is left/right symmetric. Thus $B_k$ is the mirror image of $C_k$. In particular, the rightmost column of $B_k$ is identical with the leftmost column of $C_k$.

Imagine the matrix $C_k$ in isolation from the rest of $A_{k+1}$. Suppose it is subject to evolution as defined in the problem: the first (leftmost) term in a row depends only on the two first terms in the preceding row, according as they are equal or not. Now embed $C_k$ again in $A_k$. The 'leftmost' terms in the rows of $C_k$ now have neighbours on their left side - but these neighbours are their exact copies. Consequently the actual evolution within $C_k$ is the same, whether or not $C_k$ is considered as a piece of $A_{k+1}$ or in isolation. And since the top row of $C_k$ is $[1,0,\dots ,0]$, it follows that $C_k$ is identical with $A_k$.

The bottom row of $A_k$ is $[1,1,\dots ,1]$; the same is the bottom row of $C_k$, hence also of $B_k$, which mirrors $C_k$. So the bottom row of $A_{k+1}$ consists of ones only and the induction is complete.

b. There are many ways to produce an infinite sequence of those $n$ for which the state $[0,0,\dots ,0]$ will never be achieved. As an example, consider $n=2^k+1$ (for $k\ge 1$). The evolution of the system can be represented by a matrix $\mathcal{A}$ of width $2^k+1$ with infinitely many rows. The top $2^k$ rows form the matrix $A_k$ discussed above, with one column of zeros attached at its right.

In the next row we then have the vector $[0,0,\dots ,0,1,1]$. But this is just the second row of $\mathcal{A}$ reversed. Subsequent rows will be mirror copies of the foregoing ones, starting from the second one. So the configuration $[1,1,0,\dots ,0,0]$, i.e. the second row of $\mathcal{A}$, will reappear. Further rows will periodically repeat this pattern and there will be no row of zeros.