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 3 of 6: Two large terms in a row are impossible

Previous step Next step

In plain words

If a term were placed on a tower that is already taller than every one of the first N towers, tracing back through that tall, all-new-block tower shows there must already have been more than M taller towers before it, which is a contradiction the first time this happens.

a_n>M\implies a_{n+1}\le M

Detailed analysis

Assume that, for the first time, $a_n>M$ and $a_{n+1}>M$ . The block $B_n$ is in a tower labelled $a_n>M$ , so after it is placed that tower has height $a_{n+1}>M$ and contains more than $M$ yellow blocks. For each such block $B_r$ , the preceding block $B_{r-1}$ was placed at height $a_n>M$ in its own tower, because $a_n$ is the height of the tower containing $B_{r-1}$ after that placement. Distinct $B_r$ give distinct predecessor towers, since one tower has only one block at a given height. Thus more than $M$ distinct towers had already reached height greater than $M$ . Among them, one has a label $j>M$ , because only $M$ tower labels are at most $M$ . Let $B_t$ be the first block that raises tower $j$ from height $M$ to height $M+1$ . Then $a_t=j>M$ and $a_{t+1}=M+1>M$ , with $t<n$ , contradicting the choice of $n$ . Hence $a_n>M$ implies $a_{n+1}\le M$ . Consequently, among every two consecutive terms at least one is at most $M$ , so some value in $1,\ldots,M$ occurs infinitely often. Let $L$ be the largest index such that towers $1,\ldots,L$ are unbounded; the preceding injection shows that every unbounded tower has all smaller towers unbounded, while towers $L+1,\ldots,M$ are bounded.