IMO2024 Shortlisted Problems

Lemma 1. For any set $\mathcal{S}$, $\mathcal{S}$ wins if and only if $J(\mathcal{S},\varnothing )$ wins. Similarly, $\mathcal{S}$ wins if and only if $J(\varnothing ,\mathcal{S})$ wins.

Proof. Let $(k,m)$ be a move on $\mathcal{S}$, and let $\mathcal{T}$ be the result of applying the move. Then we can reduce $J(\mathcal{S},\varnothing )$ to $J(\mathcal{T},\varnothing )$ by applying the move $(k+1,2m-1)$.

Conversely, let $(k,m)$ be a move on $J(\mathcal{S},\varnothing )$. We can express the result of this move as $J(\mathcal{T},\varnothing )$ for some $\mathcal{T}$. Then we can reduce $\mathcal{S}$ to $\mathcal{T}$ by applying the move $(\max (k-1,0),(k+1)/2)$.

This gives us a natural bijection between games starting with $\mathcal{S}$ and games starting with $J(\mathcal{S},\varnothing )$ and thus proves the first part of the lemma. The second part follows by a similar argument. $\square$

Lemma 2. If $\mathcal{S}$ and $\mathcal{T}$ are nonempty and at least one of them loses, then $J(\mathcal{S},\mathcal{T})$ wins.

Proof. If $\mathcal{S}$ is losing, then we can delete $J(\varnothing ,\mathcal{T})$ using the move $(1,t)$ for some $t\in J(\varnothing ,\mathcal{T})$, which leaves the losing set $J(\mathcal{S},\varnothing )$. Similarly, if $\mathcal{T}$ is losing, then we can delete $J(\mathcal{S},\varnothing )$ using the move $(1,s)$ for some $s\in J(\mathcal{S},\varnothing )$, leaving the losing set $J(\varnothing ,\mathcal{T})$. $\square$

Lemma 3. If $\mathcal{S}$ is nonempty and wins, then $J(\mathcal{S},\mathcal{S})$ loses.

Proof. From this position, we can convert any sequence of moves into another valid sequence of moves by replacing $(k,2n-1)$ with $(k,2n)$, and vice versa. Thus we may assume that the initial move $(k,m)$ has $m$ odd. We want to show that any such move results in a winning position for the other player.

The move $(0,m)$ loses immediately. Otherwise, the move results in the set $J(\mathcal{T},\mathcal{S})$ for some set $\mathcal{T}$. There are three cases.

If $\mathcal{T}$ is empty then the other player gets the winning set $J(\varnothing ,\mathcal{S})$.

If $\mathcal{T}$ is losing then the other player can choose the move $(1,s)$ for some $s\in J(\varnothing ,\mathcal{S})$, which leaves the losing set $J(\mathcal{T},\varnothing )$.

If $\mathcal{T}$ is nonempty winning then the other player can choose the move $(k,m+1)$, which results in the position $J(\mathcal{T},\mathcal{T})$. We can then proceed by induction on $|\mathcal{S}|$ to show that this is a losing set. $\square$

Lemma 4. $[2n]$ wins if and only if $[n]$ loses.

Proof. Note that $[2n]=J([n],[n])$. The result then follows directly from the previous two lemmas. $\square$

Lemma 5. For any integer $n⩾1$, $[2n+1]$ wins.

Proof. By Lemma 4, either $[n]$ or $[2n]$ loses. If $[n]$ loses, then by Lemma 2 we have that $[2n+1]=J([n+1],[n])$ wins. Otherwise, $[2n]$ loses, and therefore $[2n+1]$ wins by choosing the move $(k,2n+1)$ for sufficiently large $k$ so that only $2n+1$ is eliminated. $\square$

It remains to verify the original answer. We have two cases to consider:

- Suppose $N=2^n$ for some $n$. For $N=1$, every move is an instant loss for Geoff. Then by Lemma 4, Geoff wins for $N=2^n$ if and only if Geoff loses for $N=2^{n-1}$, and thus by induction we have that Geoff wins for $N=2^n$ if and only if $n$ is odd.

- Otherwise, $N=t{2}^n$, for some $n$ and some $t>1$ with $t$ odd. By Lemma 5, Geoff wins when $n=0$. Then by Lemma 4, Geoff wins for $N=t{2}^n$ if and only if Geoff loses for $N=t{2}^{n-1}$, and thus by induction on $n$ we have that Geoff wins for $N=t{2}^n$ if and only if $n$ is even.