For which set $A$, Alice has a winning strategy?

Question

Alice and Bob are playing a game. They take an integer $n>1$, and partition the set $\{1,2,...n\}$ into two non-empty subsets $A,B$. Alice takes the set $A$ and Bob takes the set $B$. They take a paper and write $0$ on it. Alice plays first, and the rules are:

Each turn, let $x$ be the number written on the paper. The player has two choices:

• Erase $x$ and rewrite $0$ on the paper, or
• Choose a number $y>x$ to remove from their set, then erase $x$ and write $y$ on the paper.

The game ends if a player's set becomes empty, and that player wins the game.

Question: For which subsets $A$ of $\{1,2,...n\}$ does Alice have a winning strategy, and what is the number of such sets?

I think the best strategy for both players is to choose the smallest element possible that can be played from their set, except if the other player's set has only $1$ element, in which case they choose the largest element in their set. But I can't prove it or describe the winning sets for Alice using that strategy.

Update: The above strategy doesn't work, as @aschepler points out: for $n=6$, $A=\{1,4,5\}$, $B=\{2,3,6\}$, Alice wins by initially choosing $4$ or $5$, but not $1$.

Answer 1

Not a complete answer, but here are some thoughts. For two players, the hands are open as we know the starting sets and we can track what's remaining at each point. With 3 or more players, the game could have unknown information, making the strategies less deterministic. As an aside, this game is similar in mechanics to 6 nimmt! / Take 6!.

Winning States for Alice

1. a) It is Alice's turn, b) Alice has one number left, and c) the current number is less than Alice's number. The basic case.
2. a) All of Alice's remaining numbers are greater than Bob's, and b) Bob is not in a winning state. Alice can simply play in any order, and Bob is forced to do 0 everytime
3. a) Alice has $n$ and one other number, and b) Bob is not in a winning state. Alice plays $n$, Bob is forced to 0, Alice plays her final number.

So one approach is to try to end up in a winning state like the above, and avoid reaching a winning state for the opponent. For example, if you have only one number greater than your opponent's smallest, then don't spend it unless you're about to win. My hunch is the player with $n$ is more likely to have a guaranteed winning strategy.

When playing with humans, playing $1$ 'psychologically' forces the opponent to play a number (even though they could do 0, it's unlikely they'll pass on the freebie). Although I can't actually think up a situation where that is useful.