An Infinitely Long Game

(Drew here.) Let's take a dive into a problem from the 2023 IMO Shortlist. This is C5, one of the hardest shortlist problems this year (but let's be honest, the whole C list was devilishly hard).

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.

Here, the problem presents itself to us. An infinitely long game, with a finite goal. How is this even possible?

Let $n=2023$, and I'll just clean up the statement a bit here: after $n$ days, remove one gem from each of the $n$ chests. This resets us to a position with $0$ total gems... except some of them can be negative, and we'll allow that.

Let $n$ days be a year, and define a state to be a list of $n$ numbers, representing the number of gems in each chest, focusing on only those times multiples of a year. What does it mean for $C$ to be finite?

It means there's a finite number of total states that can be reached. So we want to find a finite set of states $S$, that Elisa can always ensure to stay within.

There are two classes of pathways which I wish to highlight, and will be comparing in this post:

1. A "memoryful" approach, where we keep track of how Elisa and the fairy played the game to get to this state, and characterise $S$ by the path taken to get there. We need to somehow "cancel" parts of the path strategically, to make sure $S$ is finite.
2. A "memoryless" approach, where we only look at the current state and decide what to do. This requires determining a possible $S$ and finding the strategy to remain in $S$, at the same time.

Before we continue, give it a think: which approach sounds easier? Which will yield a better value of $C$? Is it even possible to find the smallest value of $C$? Or, just try the problem yourself :)

Memoryful Approach

To illustrate this concept of "characterising $S$ by the path taken to get there", I'll use an example of flipping coins.

There are $3$ coins in a line, all starting with heads. Then we do the following flips:

1. Flip coin $1$.
2. Flip coin $2$.
3. Flip coin $3$.
4. Flip coin $2$.

The end result is that only coin $2$ is heads, and that's because the actions of flipping coin $2$ twice cancel each other out.

This way, our state space is just the three parities of the number of times each coin has been flipped, which has a size of $2^3$, even if the flip sequences can be as long as we want.

Back to the problem: Viewing this game in terms of years is quite limiting, it's trying to make you respond immediately to the fairy's move. Instead, what if Elisa only responds when reaching the same configuration of chests for the second time?

The configuration of chests (whether each of the $2023$ chests is open or closed), corresponds to the coins, and the current face of the "coin" corresponds to the last chest the fairy locked in that configuration (arbitrarily set in the beginning).

Elisa's job is to then, just read the face of the coin, and put a gem there. It isn't closed, because the fairy can close it after. Then the fairy rewrites it to something else.

That simple? Yes. Each of the moves just rewrites one of the coins, and at any point, the number of times Elisa has chosen a chest is approximately how many times the fairy has chosen it. The difference is bounded by how many coins we have, so with a bit of care for edge cases, we get $C=2^{2023}+1$ works here. (Alternatively, you can bound the size of $S$.)

Memoryless Approach

Let's experiment with the strategy where Elisa always chooses the chest with the fewest gems.

Starting with $n=3$, we get the two possible states $(0,0,0)$ and $(-1,0,1)$. Check that no matter what the fairy does, Elisa's strategy always stays in either one of these states after $n$ days.

In particular, by always closing the chest with the fewest gems, the fairy can always achieve $(-1,0,1)$ too.

Skipping to $n=5$, there are a bunch of states that can be reached; this fairy strategy eventually reaches $(-2,-1,0,1,2)$. By experimenting more, this stable state seems to be the best that the fairy can achieve. Other actions by the fairy get other states like $(-2,0,0,0,2)$, $(-1,-1,-1,1,2)$, or $(-1,-1,0,1,1)$.

But it's impossible to get to $(-3,0,0,0,3)$, or even $(-2,-2,0,2,2)$. Why? To get to a value of $-3$ as the lowest number of gems, we probably should have two $-2$s in the previous case, so... now what?

Here's the leap of faith moment: We claim that $(-2)+(-2)<(-2)+(-1)$ is the reason getting to $(-2,-2,0,2,2)$ is impossible. There are simply too few gems in the smallest chests, because Elisa's idea is to put gems in the smallest chests.

Then, the reason we can't get $(-2,-1,-1,2,2)$ is because $(-2)+(-1)+(-1)<(-2)+(-1)+0$.

The bold claim is that $S$ (for $n=5$) is exactly the set of states that are majorised by $(-2,-1,0,1,2)$. (The sum of the $k$ lowest terms in each state of $S$ is at least the sum of the $k$ lowest terms in $(-2,-1,0,1,2$.) This turns out to be true!

And how you prove this is showing that after one day, $(-1,-1,0,1,2)$ majorises the sequence, the next day $(-1,0,0,1,2)$, and so on, after which the problem is solved.

The value of $C$ obtained for $n=2023$ is $2022$, which is the best possible constant.

Comparing the Approaches

The memoryless approach seems like the obvious thing to do at first: if we can test small cases and see that the strategy of Elisa always choosing the chest with the fewest gems works, then why doesn't everyone get this solution? Why is the problem hard?

When trying this, it isn't obvious that it has to work. And here are other ways to look at this strategy, for example the fairy's POV. Can you show that the fairy's best strategy is to always lock the smallest chest? Or, can you show that the other strategies for Elisa are bound to yield worse results? (Yes, apparently you can, but it's much harder.)

The memoryful approach has its own motivation: getting a better way to handle the position. Instead of looking at only the current state, we maintain a useful history of moves and use that as a piece of information. It's no longer a matter of "what exactly do I do in this position", but rather "what can I do to maintain a position with a nice description".

The process we have encapsulates only the useful information of past moves, and tells us what moves we should do, only when we have reached a similar state before. Since we're letting go of the full control we have, it's expected that the value of $C$ obtained here increases, and it does by a lot.

Which solution you come with probably depends on which approach you are aiming for when you choose to lock in and dig deeper. Even though the solutions look simple, they're very hard to come up with, because of how many approaches don't work, such as a weights system to find $S$ (I didn't show them here).

Closing Remarks

These kinds of problem formulations are quite rare. The only very similar one I know of is USA TST 2017/4, in which you are cheating at a trivia contest, and must maintain the finite lead you start with, but the game plays for an infinite amount of time.

And that's also what makes it hard: people aren't familiar with these types of problems, and the ideas are usually much less straightforward. How much you can understand about the current state of the game is very different compared to other problems, and especially grasping the infinite part of the problem is hard.

The number of solutions to this problem (I've heard of around 5 other solutions) is also an indication of the open-ended nature - when you have the freedom to choose $C$ to be arbitrarily large, even wild strategies that care only about finitude while being hilariously inefficient work. Unfortunately, the formulation which requires you to find the optimal value of $C$ limits the possibilities that this problem gives.

There's this tradeoff between very carefully analysing Elisa's moves and taking a bird's eye view of the situation, which is what creates the various solution paths. It's uncommon to see so much freedom in a problem, which results in so many unique solutions and yet so many failed attempts. This problem will definitely remain in my memory :)