IMO2024 Shortlisted Problems

Let $M>\max \left(a_1,\dots ,a_N\right)$. We first prove that some integer appears infinitely many times. If not, then the sequence contains arbitrarily large integers. The first time each integer larger than $M$ appears, it is followed by a $1$. So $1$ appears infinitely many times, which is a contradiction.

Now we prove that every integer $x⩾M$ appears at most $M-1$ times. If not, consider the first time that any $x⩾M$ appears for the $M^{\text{th}}$ time. Up to this point, each appearance of $x$ is preceded by an integer which has appeared $x⩾M$ times. So there must have been at least $M$ numbers that have already appeared at least $M$ times before $x$ does, which is a contradiction.

Thus there are only finitely many numbers that appear infinitely many times. Let the largest of these be $k$. Since $k$ appears infinitely many times there must be infinitely many integers greater than $M$ which appear at least $k$ times in the sequence, so each integer $1,2,\dots ,k-1$ also appears infinitely many times. Since $k+1$ doesn't appear infinitely often there must only be finitely many numbers which appear more than $k$ times. Let the largest such number be $l⩾k$. From here on we call an integer $x$ big if $x>l$, medium if $l⩾x>k$ and small if $x⩽k$. To summarise, each small number appears infinitely many times in the sequence, while each big number appears at most $k$ times in the sequence.

Choose a large enough $N^{\prime }$ $>$ $N$ such that $a_{N^{\prime }}$ is small, and in $a_1,\dots ,a_{N^{\prime }}$: - every medium number has already made all of its appearances; - every small number has made more than $\max (k,N)$ appearances.

Since every small number has appeared more than $k$ times, past this point each small number must be followed by a big number. Also, by definition each big number appears at most $k$ times, so it must be followed by a small number. Hence the sequence alternates between big and small numbers after $a_{N^{\prime }}$.

Lemma 1. Let $g$ be a big number that appears after $a_{N^{\prime }}$. If $g$ is followed by the small number $h$, then $h$ equals the amount of small numbers which have appeared at least $g$ times before that point.

Proof. By the definition of $N^{\prime }$, the small number immediately preceding $g$ has appeared more than $\max (k,N)$ times, so $g>\max (k,N)$. And since $g>N$, the $g^{\text{th}}$ appearance of every small number must occur after $a_N$ and hence is followed by $g$. Since there are $k$ small numbers and $g$ appears at most $k$ times, $g$ must appear exactly $k$ times, always following a small number after $a_N$. Hence on the $h^{\text{th}}$ appearance of $g$, exactly $h$ small numbers have appeared at least $g$ times before that point.

Denote by $a_{[i,j]}$ the subsequence $a_i,a_{i+1},\dots ,a_j$.

Lemma 2. Suppose that $i$ and $j$ satisfy the following conditions: (a) $j>i>N^{\prime }+2$, (b) $a_i$ is small and $a_i=a_j$, (c) no small value appears more than once in $a_{[i,j-1]}$.

Then $a_{i-2}$ is equal to some small number in $a_{[i,j-1]}$.

Proof. Let $\mathcal{I}$ be the set of small numbers that appear at least $a_{i-1}$ times in $a_{[1,i-1]}$. By Lemma 1, $a_i=|\mathcal{I}|$. Similarly, let $\mathcal{J}$ be the set of small numbers that appear at least $a_{j-1}$ times in $a_{[1,j-1]}$. Then by Lemma 1, $a_j=|\mathcal{J}|$ and hence by (b), $|\mathcal{I}|=|\mathcal{J}|$. Also by definition, $a_{i-2}\in \mathcal{I}$ and $a_{j-2}\in \mathcal{J}$.

Suppose the small number $a_{j-2}$ is not in $\mathcal{I}$. This means $a_{j-2}$ has appeared less than $a_{i-1}$ times in $a_{[1,i-1]}$. By (c), $a_{j-2}$ has appeared at most $a_{i-1}$ times in $a_{[1,j-1]}$, hence $a_{j-1}⩽a_{i-1}$. Combining with $a_{[1,i-1]}\subset a_{[1,j-1]}$, this implies $\mathcal{I}\subseteq \mathcal{J}$. But since $a_{j-2}\in \mathcal{J}\backslash \mathcal{I}$, this contradicts $|\mathcal{I}|=|\mathcal{J}|$. So $a_{j-2}\in \mathcal{I}$, which means it has appeared at least $a_{i-1}$ times in $a_{[1,i-1]}$ and one more time in $a_{[i,j-1]}$. Therefore $a_{j-1}>a_{i-1}$.

By (c), any small number appearing at least $a_{j-1}$ times in $a_{[1,j-1]}$ has also appeared $a_{j-1}-1⩾a_{i-1}$ times in $a_{[1,i-1]}$. So $\mathcal{J}\subseteq \mathcal{I}$ and hence $\mathcal{I}=\mathcal{J}$. Therefore, $a_{i-2}\in \mathcal{J}$, so it must appear at least $a_{j-1}-a_{i-1}=1$ more time in $a_{[i,j-1]}$.

For each small number $a_n$ with $n>N^{\prime }+2$, let $p_n$ be the smallest number such that $a_{n+p_n}=a_i$ is also small for some $i$ with $n⩽i<n+p_n$. In other words, $a_{n+p_n}=a_i$ is the first small number to occur twice after $a_{n-1}$. If $i>n$, Lemma 2 (with $j=n+p_n$) implies that $a_{i-2}$ appears again before $a_{n+p_n}$, contradicting the minimality of $p_n$. So $i=n$. Lemma 2 also implies that $p_n⩾p_{n-2}$. So $p_n,p_{n+2},p_{n+4},\dots$ is a nondecreasing sequence bounded above by $2k$ (as there are only $k$ small numbers). Therefore, $p_n,p_{n+2},p_{n+4},\dots$ is eventually constant and the subsequence of small numbers is eventually periodic with period at most $k$.

---

Alternative solution.

We follow Solution 1 until after Lemma 1. For each $n>N^{\prime }$, we keep track of how many times each of $1,2,\dots ,k$ has appeared in $a_1,\dots ,a_n$. We will record this information in an updating $(k+1)$-tuple $$\left(b_1,b_2,\dots ,b_k;j\right)$$ where each $b_i$ records the number of times $i$ has appeared. The final element $j$ of the $(k+1)$ tuple, also called the active element, represents the latest small number that has appeared in $a_1,\dots ,a_n$.

As $n$ increases, the value of $\left(b_1,b_2,\dots ,b_k;j\right)$ is updated whenever $a_n$ is small. The $(k+1)$ tuple updates deterministically based on its previous value. In particular, when $a_n=j$ is small, the active element is updated to $j$ and we increment $b_j$ by $1$. The next big number is $a_{n+1}=b_j$. By Lemma 1, the next value of the active element, or the next small number $a_{n+2}$, is given by the number of $b$ terms greater than or equal to the newly updated $b_j$, or $$\left|\left\{i\mid 1⩽i⩽k,b_i⩾b_j\right\}\right|.$$

Each sufficiently large integer which appears $i+1$ times must also appear $i$ times, with both of these appearances occurring after the initial block of $N$. So there exists a global constant $C$ such that $b_{i+1}-b_i⩽C$. Suppose that for some $r$, $b_{r+1}-b_r$ is unbounded from below. Since the value of $b_{r+1}-b_r$ changes by at most $1$ when it is updated, there must be some update where $b_{r+1}-b_r$ decreases and $b_{r+1}-b_r<-(k-1)C$. Combining with the fact that $b_i-b_{i-1}⩽C$ for all $i$, we see that at this particular point, by the triangle inequality $$\min \left(b_1,\dots ,b_r\right)>\max \left(b_{r+1},\dots ,b_k\right)$$ Since $b_{r+1}-b_r$ just decreased, the new active element is $r$. From this point on, if the new active element is at most $r$, by the previous formula, the next element to increase is once again from $b_1,\dots ,b_r$. Thus only $b_1,\dots ,b_r$ will increase from this point onwards, and $b_k$ will no longer increase, contradicting the fact that $k$ must appear infinitely often in the sequence. Therefore $|b_{r+1}-b_r|$ is bounded.

Since $|b_{r+1}-b_r|$ is bounded, it follows that each of $|b_i-b_1|$ is bounded for $i=1,\dots ,k$. This means that there are only finitely many different states for $\left(b_1-b_1,b_2-b_1,\dots ,b_k-b_1;j\right)$. Since the next active element is completely determined by the relative sizes of $b_1,b_2,\dots ,b_k$ to each other, and the update of $b$ terms depends on the active element, the active element must be eventually periodic. Therefore the small numbers subsequence, which is either $a_1,a_3,a_5,\dots$ or $a_2,a_4,a_6,\dots$, must be eventually periodic.