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

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$$.

• Given what you say in the last paragraph there seems to be something in the rules that are not currently stated. (Like they must have $y>x$?)
– Qise
Sep 25, 2023 at 11:31
• Just to clarify : For a given $n$ , we want to charaterize the subsets $A$ for which Alice has a winning strategy , right ? Sep 25, 2023 at 11:36
• Your strategy causes Alice to lose if $A = \{1,4,5\}, B = \{2,3,6\}$, but Alice can win by instead playing $4$ or $5$ first. Sep 25, 2023 at 12:58
• Observation: Curiously, this is equivalent to the simplest form of Climbing game, with no multi-card combos, for $2$ players. I.e. you must play a card which beats the previous card, or pass (write $0$). If you pass, your opponent can lead any card. Whoever plays all cards first wins. This family of games is very common in China. One version popular in the west is Tichu. Sep 29, 2023 at 0:41
• I've written a fairly simple Python script to calculate the winner... of the initial $2^n-2$ partitions where neither $A$ nor $B$ is empty, I find that the first player wins in the following number of cases: $2,5,9,20,41,78,162,314,630,1254,2476,4971,9806,19670,38960,77907,\ldots$. (This is for $n=2$ through $n=17$.) The sequence doesn't appear to be in the OEIS. The fraction of cases won by the first player seems to converge to about $3/5$. Oct 3, 2023 at 3:45

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.