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 1 of 6: The tower picture

Previous step Next step

In plain words

Imagine placing a numbered block for every term of the sequence into the tower labeled by its value; then each new term after index N is exactly the current height of the tower that the previous term points to.

M=\max(a_1,\ldots,a_N)

Detailed analysis

Set $M=\max(a_1,\ldots,a_N)$ and visualize a row of towers labeled $1,2,3,\ldots$ ; for $i=1,2,\ldots$ , term $a_i$ adds a block to tower $a_i$ . The first $N$ blocks are called red; for $i>N$ , block $a_i$ is placed on tower $a_i$ , whose new height after this placement is by definition $a_i$ itself, i.e. block $a_i$ lands exactly at height $a_i$ in its tower — reflecting that $a_i$ counts how many times $a_{i-1}$ has appeared so far.