Problem 3.
Let $a_1,a_2,a_3,...$ be an infinite sequence of positive integers, and let $N$ be a positive integer. Suppose that, for each $n \ge N, a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1,a_2,...,a_{n-1}$.
Prove that at least one of the sequences $a_1,a_3,a_5,... $and $a_2,a_4,a_6,...$ is eventually periodic.
(An infinite sequence $b_1,b_2,b_3,...$ is eventually periodic if there exist positive integers $p$ and $M $such that $b_{m+p}=b_m$ for all $m \geq M$.)

Solution

Denote $f(n, i)$ the number of occurrences of $i$ among the first $n$ entries $a_1, \ldots, a_n$ of the sequence. We have $a_n = f(n-1, a_{n-1})$ for all $n > N$. Select a sufficiently large integer $M > N$ such that $f(N, j) = 0$ for all $j \ge M$ and $f(N, j) < M$ for all $j <M$.

We begin by observing that starting from $n = N+1$, any pairs $(a_n, a_{n+1})$ will appear only once in the sequence. It means that all the numbers that precedents a same number $j$ in the sequence must be mutually different.

Claim 1: For all $t > N$ and $M \le i < j$, $f(t, i) \ge f(t, j)$.
Proof

Claim 2: $f(t, K)\le K-1$ for all $t$.
Proof

Due to claim 1 and claim 2, for all $t$ and $i \ge K$, we have $f(t, i) \le K-1$. This means that for any given $i$, $\lim_{t\to \infty} f(t, i)$ converges to $B_i$ for some $B_i \le K-1$ (due to monotonicity in $t$). Due to claim 1 again we can see that $B_i\ge B_j$ for all $K\le i < j$, so $\lim_{i\to \infty} B_i = c$ for some $0\le c \le K-1$. Hence, there exists constants $T, M, c$ such that $f(t, i) = c$ for all $t > T, i > M$.

Claim 3: $c \ge 1$ and the numbers $1, 2, \ldots, c$ are the only numbers that occur infinitely often in the sequence.
Proof

Claim 3 implies that there exists sufficiently large integers $N'$ and $M$ such that for all $n > N'$, it is either that $a_n > M$, or $a_n \le c$. Note that we can again select $N'$ to be large enough so that $f(N', i) > c$ for all $1\le i \le c$, so that any numbers that comes after $1\le i \le c$ must be larger than $M$. This creates an alternating sequence between "large" and "small" number. It is sufficient to show that the sequence of "small" number is eventually periodic. The tricky part of this is to control the gap between occurrences of the same number.

Claim 4: There exists a constant $D$ such that for any $t$, $\max_{1\le i \le c} f(t, i) - \min_{1\le i\le c} f(t, i) \le D$.
Proof

For a number $n > M$, define $i_{n, 1} < i_{n, 2} < \ldots < i_{n, c}$ the indices that $a_{i_{n, k}} = n$. Denote the difference tuple $T_n = (i_{n, 2} - i_{n, 1}, \ldots, i_{n, c} - i_{n, c-1})$.

Claim 5: There is a constant $D'$ such that $i_{n, h} - i_{n, h-1} \le D'$ for all $n > M$ and $2\le h\le c$.
Proof

Now, since there are at most $D'^{c-1}$ values for the tuples $T_n$ for $n \ge M$, $T_n$ must be eventually periodic. Let $T$ be the period of $T_n$, and let $b = i_{n+T, 1} - i_{n, 1}$, then for every sufficiently large $n$ and $1\le h\le c$, we have $i_{n+T, h} - i_{n, h} = i_{n+T, H} - i_{n+T, 1} - (i_{n, h} - i_{n, 1}) + i_{n+T,1} - i_{n, 1} = i_{n+T,1} - i_{n, 1}$. Now, we can proceed similar to claim 5 to show that there is a constant $B$ such that $i_{n+T,1} - i_{n, 1} \le B$ for all $n$ (brief idea: the difference $i_{n+T,1} - i_{n, 1}$ is the difference between the $n^\text{th}$ 1 and $(n+T)^\text{th}$ 1, hence occurrences of $2, \ldots, c$ can only be at most $T+2D$ for each of them). This again means that $i_{n+T,1} - i_{n, 1} \le B$ is eventually periodic, so there is a period $C$ such that $i_{n+T+C,1} - i_{n+C, 1} = i_{n+T,1} - i_{n, 1}$ for all $n$ sufficiently large.

It is important to note that eventual periodicity is implied due to a non trivial fact that once a pattern repeats, then by induction it will keep repeating. I'll leave this as some details for others to work on.

Let $b = i_{n+T+C, 1} - i_{n, 1}$. Then for any $n$ sufficiently large and $1\le h\le c, a_{i_{n, h} +1} = h = a_{i_{n+T+C, h} + 1} = a_{i_{n, h} + b+1}$. This implies that the "small" sequence is eventually periodic, as desired.