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$

IMO 2024 Problem 5

Many people think that this problem was chose by mistake, as it is too easy, even as P1 or P4 for IMO. It turns out to have an interesting corner case that I did not recognized!

Turbo the snail plays a game on a board with $2024$ rows and $2023$ columns. There are hidden monsters in $2022$ of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.

Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.

Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n$-th attempt or earlier, regardless of the locations of the monsters.

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

Solution:

For simplicity we ignore the first and last rows, and denote by $(r, c)$ the cell in the $r$-th row and $c$-th column where $1\le r\le 2022, 1\le c\le 2023$.

The answer is $n=3$. To show that we could not do better, note that in the first attempt it is always possible to hit the monster in the first row. Then, with this information it is still possible to hit the monster in the second row. Therefore we cannot do better than $n=3$.

The following strategy guarantees a successful third attempt. In the first attempt locate the monster in the first row. Two cases arise.

[Case 1] The monster in the first row is not in the leftmost nor rightmost cell.

In the second attempt locate the monster in the second row, which is either to the lower right or lower left of the monster in the first row. Thus in the third attempt, with these information we can always go to the cell right below the monster in the first row, which cannot contain a monster. Then we go down to the last row.

[Case 2] The monster in the first row is in the leftmost or rightmost cell.

Without loss of generality suppose it is in the rightmost cell $(1,2023)$. We go to the leftmost cell of the second row, then go right until hitting a monster or until we get to $(2,2021)$ safely. In the latter case, we know that $(2,2022)$ has a monster so we move back to the leftmost cell in the second row, go down to the third row, and again go right until hitting a monster or until we get to $(3,2020)$ safely. In the latter case we know that $(3,2021)$ has a monster, so again we move back to the left end and go down to the next row, and then go right until hitting a monster etc. In essence, for any $2\le r\le 2022$, in row $r$ we start from the left end to go right until hitting a monster or reaching $(r,2023-r)$. In the latter case we know that $(r,2024-r)$ has a monster, so we increase $r$ by $1$ if $r<2022$ or claim the second attempt successful if $r=2022$. Anytime we hit a monster at $(r,c)$ in this attempt, in the next attempt we can go from $(1,c+1)$ to $(r,c+1)$ to $(r,2023)$ to $(2022,2023)$.

$\square$