IMO 2024 Problem 3

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$, $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 sequence $a_1, a_3, a_5, \dots$ and $a_2, a_4, a_6, \dots$ is eventually periodic.

(An infinite sequence $b_1, b_2, b_3, \dots$ is eventually periodic if there exist positive integers $p$ and $M$ such that $b_{m+p} = b_m$ for all $m \ge M$.)

======================

Scroll down to the bottom to see the elegant and beautiful proof provided by IMO.

Proof 1:

Denote by $c_n$ the number of occurrences of $a_n$ in $a_1,a_2,\dots,a_{n}$. Let 

$$
W:=\max_{1\le n\le N}\max\{a_n,c_n\}
$$

Fact 1

Eventually $a_n=c_{n-1}$.

Lemma 2

There does not exist $n$ such that $a_n,c_n>W$.

Proof: Up to $n\le N$ every $(a_n,c_n)\in [W]\times[W]$, so if such $n$ exists then $N<n$. Let $n$ be the smallest integer with $a_n,c_n>W$. Since this is the $c_n^\text{th}$ occurrence of $a_n$, we know that $c_n=W+1$ and $a_n$ has appeared $W$ times before. This means that each of some $W$ distinct positive integers has appears at least $a_n>W$ times, and now some $a_{n-1}$ also has appears $a_n>W$ times. Either $a_{n-1}$ or one of those $W$ distinct positive integers is greater than $W$, and they all have appeared more than $W$ times. This contradicts with our assumption that $n$ is the smallest integer with $a_n,c_n>W$.

$\square$

Given $W$ is finite we have the following.

Corollary 3

Eventually either $a_n\le W,c_n>W$ or $a_n>W,c_n\le W$. Moreover, these two conditions alternate infinitely.

From now on, we focus on the condition $a_n\le W,c_n>W$ for $n>N_0$ because this will be lead to the eventual periodicity. Consider the following equivalent infinite process. For some $z\in[W]$ let $x_1,x_2,\dots,x_{z}>W$ and $y\in[z]$ be positive integers. Increase $x_y$ by $1$. Suppose that among $x_1,x_2,\dots,x_{z}$ the number $x_y$ is the $y'^\text{th}$ to reach its value. Set $y=y'$ and repeat. We focus on how $y$ changes its value.

Fact 4

$y$ becomes $1$ for an infinite number of times. We call the duration between two occurrences of $y=1$ an interval.

Proof: Since $z$ is finite, the maximum of $x_1,x_2,\dots,x_{z}$ is unbounded as their sum grows indefinitely. Each time the maximum increases, $y$ becomes $1$.

$\square$

Fact 5

Suppose that $y$ goes through $(z',1,\dots,z',1)$ where $\dots$ does not include $z',1$. Furthermore, every other integer in $[z]$ appears exactly once in $\dots$. Then $y$ will go through this cycle including $z',1$ indefinitely and the periodicity sought for in $a_n$ is attained. In such case, we say $y$ locks in.

The rest of our proof is to show that $y$ eventually locks in. Note that before $y$ locks in $z$ may decrease.

Lemma 6

Eventually $y$ either has locked in or does not repeat itself immediately.

Proof: If there is immediate repetition of $y=1$, then $x_1$ is the largest among $x_1,x_2,\dots,x_z$ and $y$ has locked in. So within an interval we assume $y$ has not locked in, $y=k$ twice in a row, and right before that $y=k'\ne k$. This implies that after increment by $1$, $x_{k'}$ is the $k^\text{th}$ to reach its value. After increment by $1$, if $x_k\le x_{k'}$ then $x_k$ cannot be the $k^\text{th}$ to reach its value. If $x_k>x_{k'}$, then $x_k$ is the $k''^\text{th}$ to reach its value where $k''<k$. So either way $x_k$ cannot be the $k^\text{th}$ to reach its value and therefore $y$ cannot repeat itself as $k$ immediately.

$\square$

Lemma 7

Eventually $y$ either has locked in or does not repeat itself within an interval $A$.

Proof: We can assume that within an interval, $y$ has not locked in and there are two occurrences $B$ of $y=k$, and within $A$ there are no two other occurrences $C$ of the same value of $y$ that are strictly encompassed by $B$ nor the first and second occurrences in $C$ precedes those in $B$, respectively. Suppose that the first occurrence in $B$ comes from $y=k'\ne k$, i.e., before $y=k$, $x_{k'}$ was the $k^\text{th}$ to reach its value. By the previous lemma none of $A,B,C$ are immediate repetition. If the second $y=k$ comes from the one of the top $k$ indices, then some $y=k'$ precedes it and $C$ exists, a contradiction. Otherwise there exists some $k''$ not in the top $k$ indices such that $y=k''$ twice and $C$ exists.

$\square$

Lemma 8

There exists an integer $z\in[W]$ such that for any $z'\in [W]$ there are infinite occurrences of $y=z'$ if and only if $z'\in[z]$.

Proof: By Fact 4 we have $z\ge 1$. It suffices to show that if there are no infinite occurrences of $y=k$, then there are no infinite occurrences of $y=k+1$. It holds, because to have some $x_{k'}$ to be the $k+1^\text{th}$ to reach its value some $x_{k''}$ is required to be the $k^\text{th}$ to reach its value.

$\square$

Lemma 9

There exists an one-cycle permutation $\pi=\left(\pi(1),\pi(2),\dots,\pi(z)\right)$ such that eventually

for every $z'\in [z]$, $x_{\pi(z')}$ is always the $z'^\text{th}$ to reach its value. Thus $y$ eventually locks in.

Proof: By Lemma 7 eventually no interval has repetition. If $x_i$ was the first to reach its value, and the next time $x_j$ is the first to reach its value where $i\ne j$, then within this interval $y$ becomes some value at least twice, contradiction. Therefore $\pi(1)$ exists and occurs exactly once per interval. Similarly $\pi\left(\pi(1)\right),\pi\left(\pi\left(\pi(1)\right)\right),\dots$ exist and occur exactly once per interval. Note that this cycle $C'$ persists permanently in every interval because it contains $1$.

We show that eventually cycle $C'$ cannot have any holes, i.e., it consists of and only consists of the entire $[z]$. Since from the previous paragraph it is known that eventually once some $k\in[z]$ belongs to $C'$ it stays in $C'$ forever. Thus to the contrary we suppose that eventually some $k\in[z]$ is never in $C'$ again, and yet $k+1\in C'$ indefinitely, $x_{\pi(k+1)}$ is permanently the $k+1^\text{th}$ to reach its level, and increases by $1$ in every interval. So eventually no number ever becomes the $k^\text{th}$ to reach its value, and yet in every interval $x_{\pi(k+1)}$ increases by $1$ and becomes the $k+1^\text{th}$ to reach its value, which is impossible.

$\square$

======================

Proof 2:

Following Proof 1 to Fact 5 plus Lemma 8, the strategy is to show that the difference between any pair $x_i,x_j$ is bounded from below and above, and thus there are only finitely many states and they will eventually repeat themselves.

We use Theorem here to avoid confusion.

Theorem 6

For every $i\in[z-1]$ we have $x_{i+1}-x_{i}$ is bounded from above.

Proof: Before any $x_k$ to be the $i+1^\text{th}$ to reach its value, some $x_{k'}$ has to be the $i^\text{th}$ to reach its value.

$\square$

Theorem 7

For every $i\in[z-1]$ we have $x_{i}-x_{i+1}$ is bounded from above.

Proof: Suppose $x_{r}-x_{r+1}$ is unbounded from above, then with Theorem 6 we will have $\min\{x_1,x_2,\dots,x_r\}>\max\{x_{r+1},\dots,x_z\}$ at some point right after $x_r$ increases. Moreover none of $x_{r+1},\dots,x_z$ will update anymore, contradicting with the definition of $z$.

$\square$