Problem 1968

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 \geqslant 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.