Elisa has $2023$ treasure chests, all of which are unlocked and empty at first. Each day, Elisa adds a new gem to one of the unlocked chests of her choice, and afterwards, a fairy acts according to the following rules: if more than one chests are unlocked, it locks one of them, or if there is only one unlocked chest, it unlocks all the chests. Given that this process goes on forever, prove that there is a constant $C$ with the following property: Elisa can ensure that the difference between the numbers of gems in any two chests never exceeds $C$, regardless of how the fairy chooses the chests to unlock.
Problem
Source: IMO Shortlist 2023 C5
Tags: IMO Shortlist, combinatorics
17.07.2024 16:05
can i have the pdf file
17.07.2024 17:00
18.07.2024 17:11
In fact, when $n$ is even, the best $C$ is $n$ The solution of $n$ even is similar to $n$ odd
18.07.2024 18:18
I'm the author of this problem (and part of the solution). Hope you enjoyed it. I would love to see different solutions!
20.07.2024 09:19
Call a nonempty subset of unlocked chests a state. For each state $S \subseteq \{1, \dots, 2023\}, S \neq \emptyset$ and $x \in S$, let $f(S, x)$ be the number of times that the fairy has chosen to lock chest $x$ while in state $S$, and let $g(S, x)$ be the number of times that Elisa has chosen to add a gem to chest $x$ while in state $S$. Claim: Elisa has a strategy ensuring at all times that for all $S, x$, $|f(S, x) - g(S, x)| \le 1$. Proof: The strategy is as follows: when Elisa is in some state $S$, if this is the first time $S$ has been reached, then Elisa chooses an arbitrary unlocked chest to add a gem; otherwise, Elisa adds a gem to the chest that the fairy locked on the previous occurrence of state $S$. Then, for each state $S$ and chest $x \in S$, there is a bijection between gems added to $x$ in state $S$ and occasions where $x$ was locked while in state $S$, with the exceptions of at most one gem added on the first occurrence of $S$ and the most recent time that $x$ was locked. $\square$ Now we claim that $C = 2^{2023} + 1$ works. For each chest $x$, the number of gems in $x$ is given by $\sum_{S \subseteq \{1, \dots, 2023\}, x \in S} f(S, x)$. Then for two chests $x, y$, the difference in the number of gems is \begin{align*} &\sum_{S \subseteq \{1, \dots, 2023\}, x \in S} f(S, x) - \sum_{S \subseteq \{1, \dots, 2023\}, y \in S} f(S, y) \\ &\le \sum_{S \subseteq \{1, \dots, 2023\}, x \in S} g(S, x) + |f(S, x) - g(S, x)| - \sum_{S \subseteq \{1, \dots, 2023\}, y \in S} g(S, y) - |g(S, y) - f(S, y)| \\ &\le 2^{2023} + \sum_{S \subseteq \{1, \dots, 2023\}, x \in S} g(S, x) - \sum_{S \subseteq \{1, \dots, 2023\}, y \in S} g(S, y). \end{align*} This bound is $2^{2023}$ plus the difference in the number of times chest $x$ and chest $y$ were locked, which cannot exceed $1$.
14.09.2024 10:28
Claim: It is always possible for Elisa to place the gems such that if we let $N_i$ be the number of gems in the chest with the $i$-th most gems, that after $m$ rounds where a round is $n$ moves by Elisa the sequence \[m+\lfloor\frac{n}{2}\rfloor, m+\lfloor\frac{n}{2}\rfloor-1, \dots, m+\lfloor\frac{n}{2}\rfloor-n \succ N_1, N_2, \dots, N_n\] Proof: To do this Elisa can always play in the chest with the smallest number of gems that is avaliable. I will show this inductively, suppose that after $k$ moves in the $m$-th round \[m+\lfloor\frac{n}{2}\rfloor, m+\lfloor\frac{n}{2}\rfloor-1, \dots, m+\lfloor\frac{n}{2}\rfloor-k+1, m+\lfloor\frac{n}{2}\rfloor-k+1, \dots, m+\lfloor\frac{n}{2}\rfloor-n+1 \succ N_1, N_2, \dots, N_n\]I will show that by choosing the smallest avaliable option that \[m+\lfloor\frac{n}{2}\rfloor, m+\lfloor\frac{n}{2}\rfloor-1, \dots, m+\lfloor\frac{n}{2}\rfloor-k+2, m+\lfloor\frac{n}{2}\rfloor-k+2, \dots, m+\lfloor\frac{n}{2}\rfloor-n+1 \succ N_1, N_2, \dots, N_n\], on the $k+1$-th move, as we choose the smallest and there are only $k$ closed chests, we choose one of the $k+1$ smallest of the options, thus the result holds and thus after each round the claim holds.
14.11.2024 11:17
OG! We claim $C=2022$ suffices. Strategy for Elsa: Elsa always adds a gem to the unlocked chest with THE smallest number of gems. Proof that this strategy works: Will write later Remark: In general if 2023 is replaced by $k$, $C= 2(\lfloor \frac{k}{2} \rfloor)$ works