Problem 3

Let

a_1,a_2,a_3,\ldots

be an infinite sequence of positive integers, and let

N

be a positive integer. Suppose that, for each

n>N

, the number

a_n

is equal to the number of times

a_{n-1}

appears in the list

(a_1,a_2,\ldots,a_{n-1})

. Prove that at least one of the sequences

a_1,a_3,a_5,\ldots

and

a_2,a_4,a_6,\ldots

is eventually periodic.

Step 2 of 6: Neighboring towers cannot drift too far apart

Previous step Next step

In plain words

Every time tower k+1 receives a new block from the process, that event can be traced back through a short, injective chain of earlier blocks to a corresponding new block in tower k, so tower k can never fall too far behind tower k+1.

h_k\ge h_{k+1}-C

Detailed analysis

Write $B_i$ for the block belonging to $a_i$ , and let its tower be labelled $a_i$ . For $i>N$ , the defining rule says that $B_i$ is at height $a_{i+1}$ , because $a_{i+1}$ counts the previous occurrences of the label $a_i$ . Fix $k$ . If $B_n$ is a yellow block in tower $k+1$ , then $B_{n-1}$ is the block at height $k+1$ in its own tower: indeed $a_n=k+1$ . Except for finitely many blocks touching the initial red blocks, the block immediately below $B_{n-1}$ is yellow; call it $B_r$ . It is at height $k$ , so the rule gives $a_{r+1}=k$ , meaning that $B_{r+1}$ lies in tower $k$ . Thus, apart from a finite exceptional set, map every yellow $B_n$ in tower $k+1$ to this $B_{r+1}$ . The map is injective: distinct $B_n$ give distinct $B_{n-1}$ , then distinct blocks immediately below them, and finally distinct successor blocks. Therefore, at every time, the number of yellow blocks in tower $k+1$ is at most the number in tower $k$ plus a fixed exceptional number. The finitely many red blocks can be absorbed into a constant $C$ depending only on $N$ and $M$ , giving $h_k\ge h_{k+1}-C$ . In particular, an unbounded tower forces every tower immediately to its left to be unbounded.