IMO Shortlist

We will prove that such a constant $C$ exists when there are $n$ chests for $n$ an odd positive integer. In fact we can take $C = n-1$. Elisa's strategy is simple: place a gem in the chest with the fewest gems (in case there are more than one such chests, pick one arbitrarily).

For each integer $t \geqslant 0$, let $a_{1}^{t} \leqslant a_{2}^{t} \leqslant \cdots \leqslant a_{n}^{t}$ be the numbers of gems in the $n$ chests at the end of the $t^{\text{th}}$ day. In particular, $a_{1}^{0} = \cdots = a_{n}^{0} = 0$ and
$$a_{1}^{t} + a_{2}^{t} + \cdots + a_{n}^{t} = t$$
For each $t \geqslant 0$, there is a unique index $m = m(t)$ for which $a_{m}^{t+1} = a_{m}^{t} + 1$. We know that $a_{j}^{t} > a_{m(t)}^{t}$ for all $j > m(t)$, since $a_{m(t)}^{t} < a_{m(t)}^{t+1} \leqslant a_{j}^{t+1} = a_{j}^{t}$. Elisa's strategy also guarantees that if an index $j$ is greater than the remainder of $t$ when divided by $n$ (i.e. the number of locked chests at the end of the $t^{\text{th}}$ day), then $a_{j}^{t} \geqslant a_{m(t)}^{t}$, because some chest with at most $a_{j}^{t}$ gems must still be unlocked at the end of the $t^{\text{th}}$ day.

Recall that a sequence $x_{1} \leqslant x_{2} \leqslant \cdots \leqslant x_{n}$ of real numbers is said to majorise another sequence $y_{1} \leqslant y_{2} \leqslant \cdots \leqslant y_{n}$ of real numbers when for all $1 \leqslant k \leqslant n$ we have
$$x_{1} + x_{2} + \cdots + x_{k} \leqslant y_{1} + y_{2} + \cdots + y_{k}$$
and
$$x_{1} + x_{2} + \cdots + x_{n} = y_{1} + y_{2} + \cdots + y_{n} .$$
Our strategy for proving $a_{n}^{t} - a_{1}^{t} \leqslant n-1$ is to inductively show that the sequence $(a_{i}^{t})$ is majorised by some other sequence $\left(b_{i}^{t}\right)$.

We define this other sequence $\left(b_{i}^{t}\right)$ as follows. Let $b_{k}^{0} = k - \frac{n+1}{2}$ for $1 \leqslant k \leqslant n$. As $n$ is odd, this is a strictly increasing sequence of integers, and the sum of its terms is 0. Now define $b_{i}^{t} = b_{i}^{0} + \left\lfloor \frac{t-i}{n} \right\rfloor + 1$ for $t \geqslant 1$ and $1 \leqslant i \leqslant n$. Thus for $t \geqslant 0$,
$$b_{i}^{t+1} = \begin{cases} b_{i}^{t} & \text{ if } t+1 \not\equiv i (\bmod n), \\ b_{i}^{t} + 1 & \text{ if } t+1 \equiv i (\bmod n) . \end{cases}$$
From these properties it is easy to see that
- $b_{1}^{t} + b_{2}^{t} + \cdots + b_{n}^{t} = t$ for all $t \geqslant 0$, and
- $b_{i}^{t} \leqslant b_{i+1}^{t}$ for all $t \geqslant 0$ and $1 \leqslant i \leqslant n-1$, with the inequality being strict if $t \not\equiv i (\bmod n)$.

Claim 1. For each $t \geqslant 0$, the sequence of integers $b_{1}^{t}, b_{2}^{t}, \ldots, b_{n}^{t}$ majorises the sequence of integers $a_{1}^{t}, a_{2}^{t}, \ldots, a_{n}^{t}$.

Proof. We use induction on $t$. The base case $t=0$ is trivial. Assume $t \geqslant 0$ and that $(b_{i}^{t})$ majorises $\left(a_{i}^{t}\right)$. We want to prove the same holds for $t+1$.

First note that the two sequences $\left(b_{i}^{t+1}\right)$ and $\left(a_{i}^{t+1}\right)$ both sum up to $t+1$. Next, we wish to show that for $1 \leqslant k < n$, we have
$$b_{1}^{t+1} + b_{2}^{t+1} + \cdots + b_{k}^{t+1} \leqslant a_{1}^{t+1} + a_{2}^{t+1} + \cdots + a_{k}^{t+1} .$$
When $t+1$ is replaced by $t$, the above inequality holds by the induction hypothesis. For the sake of contradiction, suppose $k$ is the smallest index such that the inequality for $t+1$ fails. Since the left hand side increases by at most 1 during the transition from $t$ to $t+1$, the inequality for $t+1$ can fail only if all of the following occur:
- $b_{1}^{t} + b_{2}^{t} + \cdots + b_{k}^{t} = a_{1}^{t} + a_{2}^{t} + \cdots + a_{k}^{t}$,
- $t+1 \equiv j (\bmod n)$ for some $1 \leqslant j \leqslant k$ (so that $b_{j}^{t+1} = b_{j}^{t} + 1$),
- $m(t) > k$ (so that $a_{i}^{t+1} = a_{i}^{t}$ for $1 \leqslant i \leqslant k$).

The first point and the minimality of $k$ tell us that $b_{1}^{t}, \ldots, b_{k}^{t}$ majorises $a_{1}^{t}, \ldots, a_{k}^{t}$ as well (again using the induction hypothesis), and in particular $b_{k}^{t} \geqslant a_{k}^{t}$.

The second point tells us that the remainder of $t$ when divided by $n$ is at most $k-1$, so $a_{k}^{t} \geqslant a_{m(t)}^{t}$ (by Elisa's strategy). But by the third point $(m(t) \geqslant k+1)$ and the nondecreasing property of $a_{i}^{t}$, we must have the equalities $a_{k}^{t} = a_{k+1}^{t} = a_{m(t)}^{t}$. On the other hand, $a_{k}^{t} \leqslant b_{k}^{t} < b_{k+1}^{t}$, with the second inequality being strict because $t \not\equiv k (\bmod n)$. We conclude that
$$b_{1}^{t} + b_{2}^{t} + \cdots + b_{k+1}^{t} > a_{1}^{t} + a_{2}^{t} + \cdots + a_{k+1}^{t},$$
a contradiction to the induction hypothesis. $\square$

This completes the proof as it implies
$$a_{n}^{t} - a_{1}^{t} \leqslant b_{n}^{t} - b_{1}^{t} \leqslant b_{n}^{0} - b_{1}^{0} = n-1 .$$

We solve the problem when 2023 is replaced with an arbitrary integer $n$. We assume that Elisa uses the following strategy:

At the beginning of the $(n t + 1)^{\text{th}}$ day, Elisa first labels her chests as $C_{1}^{t}, \ldots, C_{n}^{t}$ so that before she adds in the gem, the number of gems in $C_{i}^{t}$ is less than or equal $C_{j}^{t}$ for all $1 \leqslant i < j \leqslant n$. Then for days $n t + 1, n t + 2, \ldots, n t + n$, she adds a gem to chest $C_{i}^{t}$, where $i$ is chosen to be minimal such that $C_{i}^{t}$ is unlocked.

Denote by $c_{i}^{t}$ the number of gems in chest $C_{i}^{t}$ at the beginning of the $(n t + 1)^{\text{th}}$ day, so that
$$c_{1}^{t} \leqslant c_{2}^{t} \leqslant \cdots \leqslant c_{n}^{t}$$
by construction. Also, denote by $\delta_{i}^{t}$ the total number of gems added to chest $C_{i}^{t}$ during days $n t + 1, \ldots, n t + n$. We make the following observations.
- We have $c_{1}^{0} = c_{2}^{0} = \cdots = c_{n}^{0} = 0$.
- We have $c_{1}^{t} + \cdots + c_{n}^{t} = n t$, since $n$ gems are added every $n$ days.
- The sequence $(c_{i}^{t+1})$ is a permutation of the sequence $(c_{i}^{t} + \delta_{i}^{t})$ for all $t \geqslant 0$.
- We have $\delta_{1}^{t} + \cdots + \delta_{n}^{t} = n$ for all $t \geqslant 0$.
- Since Elisa adds a gem to an unlocked chest $C_{i}^{t}$ with $i$ minimal, we have
$$\delta_{1}^{t} + \delta_{2}^{t} + \cdots + \delta_{k}^{t} \geqslant k$$
for every $1 \leqslant k \leqslant n$ and $t \geqslant 0$.

We now define another sequence of sequences of integers as follows.
$$d_{i}^{0} = 3 n \left(i - \frac{n+1}{2}\right), \quad d_{i}^{t} = d_{i}^{0} + t$$
We observe that
$$d_{1}^{t} + \cdots + d_{n}^{t} = c_{1}^{t} + \cdots + c_{n}^{t} = n t$$
Claim 3. For each $t \geqslant 0$, the sequence $(d_{i}^{t})$ majorises the sequence $(c_{i}^{t})$.

Proof. We induct on $t$. For $t=0$, this is clear as all the terms in the sequence $\left(c_{i}^{t}\right)$ are equal. For the induction step, we assume that $(d_{i}^{t})$ majorises $(c_{i}^{t})$. Given $1 \leqslant k \leqslant n-1$, we wish to show that
$$d_{1}^{t+1} + \cdots + d_{k}^{t+1} \leqslant c_{1}^{t+1} + \cdots + c_{k}^{t+1}$$
Case 1: $c_{1}^{t+1}, \ldots, c_{k}^{t+1}$ is a permutation of $c_{1}^{t} + \delta_{1}^{t}, \ldots, c_{k}^{t} + \delta_{k}^{t}$.

Since $d_{1}^{t} + \cdots + d_{k}^{t} \leqslant c_{1}^{t} + \cdots + c_{k}^{t}$ by the induction hypothesis, we have
$$\sum_{i=1}^{k} d_{i}^{t+1} = k + \sum_{i=1}^{k} d_{i}^{t} \leqslant k + \sum_{i=1}^{k} c_{i}^{t} \leqslant \sum_{i=1}^{k} (c_{i}^{t} + \delta_{i}^{t}) = \sum_{i=1}^{k} c_{i}^{t+1}$$
Case 2: $c_{1}^{t+1}, \ldots, c_{k}^{t+1}$ is not a permutation of $c_{1}^{t} + \delta_{1}^{t}, \ldots, c_{k}^{t} + \delta_{k}^{t}$.

In this case, we have $c_{i}^{t} + \delta_{i}^{t} > c_{j}^{t} + \delta_{j}^{t}$ for some $i \leqslant k < j$. It follows that
$$c_{k}^{t} + n \geqslant c_{i}^{t} + n \geqslant c_{i}^{t} + \delta_{i}^{t} > c_{j}^{t} + \delta_{j}^{t} \geqslant c_{j}^{t} \geqslant c_{k+1}^{t} .$$
Using $d_{k}^{t} + 3 n = d_{k+1}^{t}$ and the induction hypothesis, we obtain
$$\begin{aligned} \sum_{i=1}^{k} c_{i}^{t+1} & \geqslant \sum_{i=1}^{k} c_{i}^{t} > c_{1}^{t} + \cdots + c_{k-1}^{t} + \frac{1}{2} c_{k}^{t} + \frac{1}{2} c_{k+1}^{t} - \frac{n}{2} \\ & = \frac{1}{2} \sum_{i=1}^{k-1} c_{i}^{t} + \frac{1}{2} \sum_{i=1}^{k+1} c_{i}^{t} - \frac{n}{2} \\ & \geqslant \frac{1}{2} \sum_{i=1}^{k-1} d_{i}^{t} + \frac{1}{2} \sum_{i=1}^{k+1} d_{i}^{t} - \frac{n}{2} = n + \sum_{i=1}^{k} d_{i}^{t} \geqslant k + \sum_{i=1}^{k} d_{i}^{t} = \sum_{i=1}^{k} d_{i}^{t+1} \end{aligned}$$
This finishes the induction step.

It follows that
$$c_{n}^{t} - c_{1}^{t} \leqslant d_{n}^{t} - d_{1}^{t} = 3 n (n-1)$$
From day $n t + 1$ to day $n(t+1) + 1$, Elisa adds $n$ gems, and therefore the difference may increase by at most $n$. This shows that the difference of the number of gems in two chests never exceeds $C = 3 n (n-1) + n$.