Problem: Let $a_1$, $a_2$, $a_3$, \dots\ 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, \dots, a_{n-1})$.
Prove that at least one of the sequences $a_1$, $a_3$, $a_5$, \dots\
and $a_2$, $a_4$, $a_6$, \dots\ is eventually periodic.

Solution: We present the solution from ``gigamilkmen'tgeg''
in \url{https://aops.com/community/p31224483},
with some adaptation from the first shortlist official solution as well.
Set $M \coloneq \max(a_1, \dots, a_N)$.

\paragraph{Setup.}
We will visualize the entire process as follows.
We draw a stack of towers labeled $1$, $2$, \dots, each initially empty.
For $i=1,2,\dots$, we imagine the term $a_i$ as adding a block $B_i$ to tower $a_i$.

Then there are $N$ initial blocks placed, colored \emph{red}.
The rest of the blocks are colored \emph{yellow}:
if the last block $B_i$ was added to a tower that then reaches height $a_{i+1}$,
the next block $B_{i+1}$ is added to tower $a_{i+1}$.
We'll say $B_i$ \emph{contributes} to the tower containing $B_{i+1}$.

In other words, the yellow blocks $B_i$ for $i > N$
are given coordinates $B_i = (a_i, a_{i+1})$ for $i>N$.
Note in particular that in towers $M+1$, $M+2$, \dots, the blocks are all yellow.

\begin{center}
\begin{asy}
unitsize(0.85cm);
int[] a = {1,2,2,2,2,2,3,4,1,2,6,1,3,2,7,1,4,2,8,1,5,1,6,2,9,1,7,2,10};
int N = 8;

filldraw(shift(0,0)*unitsquare, palered, black+1);
filldraw(shift(1,0)*unitsquare, palered, black+1);
filldraw(shift(2,0)*unitsquare, palered, black+1);
filldraw(shift(3,0)*unitsquare, palered, black+1);
filldraw(shift(1,1)*unitsquare, palered, black+1);
filldraw(shift(1,2)*unitsquare, palered, black+1);
filldraw(shift(1,3)*unitsquare, palered, black+1);
filldraw(shift(1,4)*unitsquare, palered, black+1);

for (int i=N; i<a.length-1; ++i) {
  filldraw(shift(a[i]-1, a[i+1]-1)*unitsquare, paleyellow, black+1);
}
draw((0,0)--(4,0)--(4,1)--(2,1)--(2,5)--(1,5)--(1,1)--(0,1)--cycle, brown+2);
label("$\boxed{N}$", (a[N-1]-0.5, a[N]-0.5), fontsize(14pt));

void draw_arrow(int k, pen p) {
  draw((a[k-1]-0.5,a[k]-0.5)--(a[k]-0.5,a[k+1]-0.5),
    p, EndArrow(TeXHead), Margin(2,2));
}

draw((4,10)--(4,-0.7), deepgreen);
label("$M$", (4,-0.7), dir(-90), deepgreen);

for (int j=1; j<=9; ++j) {
  label("$"+(string)j+"$", (j-0.5,0), dir(-90), blue+fontsize(10pt));
}

// Figure 1: setup
for (int i=8; i<=14; ++i) { draw_arrow(i, black+1.0); }

for (int i=N; i<a.length-1; ++i) {
  label("$"+(string)(i+1)+"$", (a[i]-0.5, a[i+1]-0.5), fontsize(12pt));
}
\end{asy}
\end{center}

We let $h_\ell$ denote the height of the $\ell$\ts{th} tower at a given time $n$.
(This is an abuse of notation and we should write $h_\ell(n)$ at time $n$,
but $n$ will always be clear from context.)

\paragraph{Up to alternating up and down.}
We start with two independent easy observations:
the set of numbers that occur infinitely often is downwards closed,
and consecutive terms cannot both be huge.

\begin{center}
\begin{asy}
unitsize(0.85cm);
int[] a = {1,2,2,2,2,2,3,4,1,2,6,1,3,2,7,1,4,2,8,1,5,1,6,2,9,1,7,2,10,1,8,2,11,1,9,2,12};
int N = 8;

// Red X region
fill(box((4,4),(11,12)), lightgray);
draw((4,4)--(11,12), red+1.4);
draw((11,4)--(4,12), red+1.4);

filldraw(shift(0,0)*unitsquare, palered, black+1);
filldraw(shift(1,0)*unitsquare, palered, black+1);
filldraw(shift(2,0)*unitsquare, palered, black+1);
filldraw(shift(3,0)*unitsquare, palered, black+1);
filldraw(shift(1,1)*unitsquare, palered, black+1);
filldraw(shift(1,2)*unitsquare, palered, black+1);
filldraw(shift(1,3)*unitsquare, palered, black+1);
filldraw(shift(1,4)*unitsquare, palered, black+1);

for (int i=N; i<a.length-1; ++i) {
  filldraw(shift(a[i]-1, a[i+1]-1)*unitsquare, paleyellow, black+1);
}
draw((0,0)--(4,0)--(4,1)--(2,1)--(2,5)--(1,5)--(1,1)--(0,1)--cycle, brown+2);
label("$\boxed{N}$", (a[N-1]-0.5, a[N]-0.5), fontsize(14pt));

void draw_arrow(int k, pen p) {
  draw((a[k-1]-0.5,a[k]-0.5)--(a[k]-0.5,a[k+1]-0.5),
    p, EndArrow(TeXHead), Margin(2,2));
}

draw((2,0)--(2,-0.7), deepgreen);
draw((4,12)--(4,-0.7), deepgreen);
label("$L$", (2,-0.7), dir(-90), deepgreen);
label("$M$", (4,-0.7), dir(-90), deepgreen);
draw((4,4)--(11,4), deepgreen);

for (int j=1; j<=11; ++j) {
  label("$"+(string)j+"$", (j-0.5,0), dir(-90), blue+fontsize(10pt));
}


// Figure 2: claim with C
filldraw(shift(a[18]-1, a[19]-1)*unitsquare, yellow, black+2);
filldraw(shift(a[19]-1, a[20]-1)*unitsquare, yellow, black+2);
filldraw(shift(a[30]-1, a[31]-1)*unitsquare, yellow, black+2);
filldraw(shift(a[31]-1, a[32]-1)*unitsquare, yellow, black+2);
draw_arrow(19, blue+1.1);
draw_arrow(31, blue+1.1);

for (int i=N; i<a.length-1; ++i) {
  label("$"+(string)(i+1)+"$", (a[i]-0.5, a[i+1]-0.5), fontsize(12pt));
}
\end{asy}
\end{center}

\begin{claim*}
  If the $(k+1)$\ts{st} tower grows arbitrarily high, so does tower $k$.
  In fact, there exists a constant $C$ such that $h_{k} \ge h_{k+1} - C$ at all times.
\end{claim*}
\begin{proof}
  Suppose $B_n$ is a yellow block in tower $k+1$.
  Then with at most finitely many exceptions, $B_{n-1}$ is a yellow block at height $k+1$,
  and the block $B_r$ right below $B_{n-1}$ is also yellow;
  then $B_{r+1}$ is in tower $k$.
  Hence, with at most finitely many exceptions, the map
  \[ B_n \mapsto B_{n-1} \mapsto B_r \mapsto B_{r+1} \]
  provides an injective map taking each yellow block in tower $k+1$
  to a yellow block in tower $k$.
  (The figure above shows $B_{32} \to B_{31} \to B_{19} \to B_{20}$ as an example.)
\end{proof}

\begin{claim*}
  If $a_n > M$ then $a_{n+1} \le M$.
\end{claim*}
\begin{proof}
  Assume for contradiction there's a first moment where $a_n > M$ and $a_{n+1} > M$,
  meaning the block $B_n$ was added to an all-yellow tower past $M$
  that has height exceeding $M$.
  (This is the X'ed out region in the figure above.)
  In $B_n$'s tower, every (yellow) block (including $B_n$)
  was contributed by a block placed in different towers at height $a_n > M$.
  So before $B_n$, there were already $a_{n+1} > M$ towers of height more than $M$.
  This contradicts minimality of $n$.
\end{proof}

It follows that the set of indices with $a_n \le M$
has arithmetic density at least half, so certainly
at least some of the numbers must occur infinitely often.
Of the numbers in $\{1,2,\dots,M\}$,
define $L$ such that towers $1$ through $L$ grow unbounded
but towers $L+1$ through $M$ do not.
Then we can pick a larger threshold $N' > N$ such that
\begin{itemize}
  \ii Towers $1$ through $L$ have height greater than $(M,N)$;
  \ii Towers $L+1$ through $M$ will receive no further blocks;
  \ii $a_{N'} \le L$.
\end{itemize}
After this threshold, the following statement is true:
\begin{claim*}
  [Alternating small and big]
  The terms $a_{N'}$, $a_{N' + 2}$, $a_{N' + 4}$, \dots\ are all at most $L$ while
  the terms $a_{N' + 1}$, $a_{N' + 3}$, $a_{N' + 5}$, \dots\ are all greater than $M$.
\end{claim*}

\paragraph{Automaton for $n \equiv N' \pmod 2$.}
From now on we always assume $n > N'$.
When $n \equiv N' \pmod 2$, i.e., when $a_n$ is small, we define the state
\[ S(n) = (h_1, h_2, \dots, h_L; a_n). \]
For example, in the figure below, we illustrate how
\[ S(34) = (9,11;a_{34}=1) \longrightarrow S(36) = (9,12;a_{36}=2) \]
\begin{center}
  \begin{asy}
    unitsize(0.85cm);
    int[] a = {1,2,2,2,2,2,3,4,1,2,6,1,3,2,7,1,4,2,8,1,5,1,6,2,9,1,7,2,10,1,8,2,11,1,9,2,12};
    int N = 8;

    filldraw(shift(0,0)*unitsquare, palered, black+1);
    filldraw(shift(1,0)*unitsquare, palered, black+1);
    filldraw(shift(2,0)*unitsquare, palered, black+1);
    filldraw(shift(3,0)*unitsquare, palered, black+1);
    filldraw(shift(1,1)*unitsquare, palered, black+1);
    filldraw(shift(1,2)*unitsquare, palered, black+1);
    filldraw(shift(1,3)*unitsquare, palered, black+1);
    filldraw(shift(1,4)*unitsquare, palered, black+1);

    for (int i=N; i<a.length-1; ++i) {
      filldraw(shift(a[i]-1, a[i+1]-1)*unitsquare, paleyellow, black+1);
    }
    draw((0,0)--(4,0)--(4,1)--(2,1)--(2,5)--(1,5)--(1,1)--(0,1)--cycle, brown+2);
    label("$\boxed{N}$", (a[N-1]-0.5, a[N]-0.5), fontsize(14pt));

void draw_arrow(int k, pen p) {
  draw((a[k-1]-0.5,a[k]-0.5)--(a[k]-0.5,a[k+1]-0.5),
    p, EndArrow(TeXHead), Margin(2,2));
}

draw((2,0)--(2,-0.7), deepgreen);
draw((4,12)--(4,-0.7), deepgreen);
label("$L$", (2,-0.7), dir(-90), deepgreen);
label("$M$", (4,-0.7), dir(-90), deepgreen);
draw((4,4)--(11,4), deepgreen);

for (int j=1; j<=11; ++j) {
  label("$"+(string)j+"$", (j-0.5,0), dir(-90), blue+fontsize(10pt));
}

// Figure 3: automaton
filldraw(shift(a[33]-1, a[34]-1)*unitsquare, yellow, black+2);
filldraw(shift(a[34]-1, a[35]-1)*unitsquare, yellow, black+2);
filldraw(shift(a[35]-1, a[36]-1)*unitsquare, yellow, black+2);
draw_arrow(34, deepgreen+1.1);
draw_arrow(35, deepgreen+1.1);

for (int i=N; i<a.length-1; ++i) {
  label("$"+(string)(i+1)+"$", (a[i]-0.5, a[i+1]-0.5), fontsize(12pt));
}
\end{asy}
\end{center}

The final element $a_n$ simply reminds us which tower was most recently incremented.
At this point we can give a complete description of how to move from $S(n)$ to $S(n+2)$:
\begin{itemize}
  \ii The intermediate block $B_{n+1}$ is placed in the tower
  corresponding to the height $a_{n+1}$ of $B_n$;
  \ii That tower will have height $a_{n+2}$ equal to the number of towers
  with height at least $a_{n+1}$; that is, it equals the cardinality of the set
  \[ \{ i \colon h_i \ge h_{a_n} \} \]
  \ii We increment $h_{a_{n+2}}$ by $1$ and update $a_n$.
\end{itemize}

For example, the illustrated $S(34) \to S(36)$
corresponds to the block $B_{34}$ at height $h_1$ in tower $1$
giving the block $B_{35}$ at height $2$ in tower $h_1$,
then block $B_{36}$ at height $h_2 + 1$ being placed in tower $2$.


\paragraph{Pigeonhole periodicity argument.}
Because only the \emph{relative} heights matter in the automata above,
if we instead define
\[ T(n) = (h_1-h_2, h_2-h_3, \dots, h_{L-1}-h_L; a_n). \]
then $T(n+2)$ can be determined from just $T(n)$.

So it would be sufficient to show $T(n)$ only takes on finitely many values
to show that $T(n)$ (and hence $a_n$) is eventually periodic.

Since we have the bound $h_{k+1} \le h_k + C$,
we are done upon proving the following lower bound:
\begin{claim*}
  For every $1 \le \ell < L$ and $n > N'$,
  we have $h_\ell \le h_{\ell+1} + C \cdot (L-1)$.
\end{claim*}
\begin{proof}
  Assume for contradiction that there is some moment $n > N'$ such that
  \[ h_\ell > h_{\ell+1} + C \cdot (L-1) \]
  and WLOG assume that $h_\ell$ was just updated at the moment $n$.
  Together with $h_{k+1} \le h_k + C$ for all $k$ and triangle inequality, we conclude
  \[ \min(h_1, \dots, h_\ell) > q \coloneq \max(h_{\ell+1}, \dots, h_L). \]
  We find that the blocks now in fact alternate between being placed
  among the first $\ell$ towers and in towers with indices greater than $q$ thereafter.
  Hence the heights $h_{\ell+1}$, \dots, $h_L$ never grow after this moment.
  This contradicts the definition of $L$.
\end{proof}

\begin{remark*}
  In fact, it can be shown that the period is actually exactly $L$,
  meaning the periodic part will be exactly a permutation of $(1,2,\dots,L)$.
  For any $L$, it turns out there is indeed a permutation achieving that periodic part.
\end{remark*}