Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/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?
Some results from MSE:
The natural strategy for both players: "choosing 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" doesn't work for $n=6$, $A=\{1,4,5\}$, $B=\{2,3,6\}$, Alice wins by initially choosing $4$ or $5$, but not $1$.
This problem is actually the simplest form of Climbing game, with no multi-card combos, for $2$ players. But I can't find any mathematic references about Climbing game.
The number of sets $A$ such that Alice win for $n=2$ to $17$ is $2,5,9,20,41,78,162,314,630,1254,2476,4971,9806,19670,38960,77907$, and the fraction of cases won by the first player seems to converge to about $\frac{3}{5}$.
Update: The case $n=18,19$ the number of sets $A$ are $154948, 309081$ respectively (Karl Fabian).
EDIT: a professional formulation/definition of the game.
Let $$X_0\cup X_1\subseteq\mathbb N,\quad X_0\ne\emptyset\ne X_1, \quad |X_0\cup X_1|<\infty $$ $(X_0\ X_1)$-game is a sequence of ordered pairs:
$$ ((X_n\ p_n):\ n=0...N)\qquad(\text{where}\ n\in\mathbb N) $$ where:
- $\quad X_n\ne\emptyset\ \ $ for $\ \ n<N,\quad $ and $\ X_N=\emptyset$;
- $\quad p_{\,0}=p_1=0;$
- $\quad$if $\ 1<n\le N\ $ then either $\ p_n=0\ $ and $\ X_n:=X_{n-1} or $$\quad p_{n-1}\le p_n\in X_{n-2} \quad\text{and}\quad X_n=X_{n-2}\setminus {p_n}.$$
Players Alice and Bob, one after another, control consecutive integers $\ p_{2\cdot k}\ $ and $\ p_{2\cdot k+1}\ $ respectively. Alice wins the game if $\ N\ $ is even, while Bob wins if $\ N\ $ is odd.
