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 6 of 6: Pigeonhole forces eventual periodicity

Previous step Next step

In plain words

With only finitely many states available and a deterministic rule advancing the state by two indices at a time, the sequence of states must eventually repeat a value, and after that everything cycles forever.

T(n)=T(n')\implies a_n,a_{n+2},\ldots \text{ periodic from that point}

Detailed analysis

Since $T(n)$ takes finitely many values as $n$ ranges over $N',N'+2,N'+4,\ldots$ (Step 5) and $T(n+2)$ is a deterministic function of $T(n)$ , by pigeonhole some state repeats, $T(n)=T(n')$ for some $n<n'$ with $n\equiv n'\pmod2$ ; from that point on the states cycle with period $n'-n$ , and in particular the corresponding subsequence of $a_n$ 's (indices of one fixed parity) is eventually periodic. Since $N'$ has a definite parity, this shows one of the two subsequences $a_1,a_3,a_5,\ldots$ or $a_2,a_4,a_6,\ldots$ is eventually periodic.