IMO 1J, Mock Exam 1

In general, for $n$ chests, we may take $C = n - 1$. Frieren's strategy is simple: in each year, among the unlocked chests, choose one with the fewest gems and add a gem to it. (Remark. This is not the only feasible strategy.)

To prove that this strategy works, let $x_1^t \le x_2^t \le \cdots \le x_n^t$ be the number of gems in the chests at the end of year $t$, and let $x_1^0 = x_2^0 = \cdots = x_n^0 = 0$. We have the following observations:

(a) For any $t$, there exists a unique $m = m(t)$ such that $x_m^{t+1} = x_m^t + 1$;

(b) For any $j > m$, $x_m^t < x_m^{t+1} \le x_j^{t+1} = x_j^t$;

(c) Since the number of locked chests at the end of year $t$ equals the remainder $r$ of $t$ divided by $n$, if $j > r$, there must exist an unlocked chest with a number of gems not exceeding $x_j^t$, so $x_j^t \ge x_m^t$.

Our goal is to prove that $x_n^t - x_1^t \le C = n - 1$ holds for all $t$. To do this, we will construct an increasing sequence $y_n^t$ satisfying $y_n^t - y_1^t \le C$, together with
$$y_1^t + \cdots + y_k^t \le x_1^t + \cdots + x_k^t \quad \text{for all}~1 \le k \le n, \quad (1)$$
$$y_1^t + \cdots + y_n^t = x_1^t + \cdots + x_n^t. \quad (2)$$
If this holds, then by (1) we have $x_1^t \ge y_1^t$ and by (2) we have $x_n^t \le y_n^t$, so $x_n^t - x_1^t \le y_n^t - y_1^t \le C$, which completes the proof.

To this end, let us construct $y_i^t$. Let $y_i^0 = i - \frac{n+1}{2}$, then it is easy to see that $y_i^0$ is increasing and $\sum y_i^0 = 0$. We then define
$$y_i^{t+1} = \begin{cases} y_i^t + 1 & \text{if } t+1 \equiv i \pmod{n}, \\ y_i^t & \text{otherwise.} \end{cases}$$
Then it is easy to see that $\sum_i y_i^t = t$, and
$$y_i^t \le y_{i+1}^t, \text{ with equality possible only when } t \equiv i \pmod{n}. \quad (3)$$
Now, (2) clearly holds, so we only need to prove that (1) holds. We proceed by induction on $t$. Suppose the original statement holds for $t$, and suppose we have
$$y_1^t + \cdots + y_k^t \le x_1^t + \cdots + x_k^t \text{ but } y_1^{t+1} + \cdots + y_k^{t+1} > x_1^{t+1} + \cdots + x_k^{t+1}. \quad (4)$$
Note that from $t$ to $t+1$, both sides of the inequality increase by at most $1$, so (4) implies that the following three things must occur simultaneously:

(d) There must exist $1 \le j \le k$ such that $y_j^{t+1} = y_j^t + 1$, that is, $t+1 \equiv j \pmod{n}$;

(e) For all $1 \le j \le k$, $x_j^{t+1} = x_j^t$, that is, $m(t) > k$;

(f) $y_1^t + \cdots + y_k^t = x_1^t + \cdots + x_k^t$.

However:
- By the induction hypothesis and (f), $y_k^t \ge x_k^t$;
- By (d), the remainder of $t$ modulo $n$ is at most $k-1$, so by the previous point and (3), $y_{k+1}^t > y_k^t \ge x_k^t$;
- By (d), the remainder of $t$ modulo $n$ is at most $k-1$, so by (c), $x_k^t \ge x_m^t$;
- But by (e), $m > k$, together with the non-decreasing property, gives $x_k^t \le x_m^t$; combined with the previous point, we get $x_k^t = x_{k+1}^t = \cdots = x_m^t$.

Combining the above, we have $y_{k+1}^t > y_k^t \ge x_k^t = x_{k+1}^t$, so by (f)
$$y_1^t + \cdots + y_{k+1}^t = (y_1^t + \cdots + y_k^t) + y_{k+1}^t > (x_1^t + \cdots + x_k^t) + x_{k+1}^t,$$
which contradicts the induction hypothesis. Therefore (1) holds. This completes the proof.