Alice and Bob Game

Question

Alice and Bob just invented a new game. The rule of the new game is quite simple. At the beginning of the game, they write down N random positive integers, then they take turns (Alice first) to either:

1. Decrease a number by one.
2. Erase any two numbers and write down their sum.

Whenever a number is decreased to 0, it will be erased automatically. The game ends when all numbers are finally erased, and the one who cannot play in his(her) turn loses the game.

Here's the problem: Who will win the game if both use the best strategy?

Answer 1

The complete solution to this game is harder than it looks, due to complications when there are several numbers $1$ present; I claim the following is a complete list of the "Bob" games, those that can be won by the second player to move. To justify, I will indicate for each case a strategy for Bob, countering any move by Alice by another move leading to a simpler "Bob" game.

I will write game position as partitions, weakly decreasing sequences of nonnegative integers (order clearly does not matter for the game). Entries present a number of times are indicated by exponents in parentheses, so $(3,1^{(4)})$ designates $(3,1,1,1,1)$. Moves are of type "decrease" (type 1 in the question) or "merge" (type 2); a decrease from $1$ to $0$ will be called a removal.

Bob-games are:

• $(0)$ and $(2)$
• $(a_1,\ldots,a_n,1^{(2k)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, $(a_1,\ldots,a_n)\neq(2)$, and $a_1+\cdots+a_n+n-1$ is even. Strategy: counter a removal of one of the numbers $1$ by another such removal; a merge of a $1$ and an $a_i$ by another merge of a $1$ into $a_i$; a merge of two entries $1$ by a merge of the resulting $2$ into one of the $a_i$; a decrease of an $a_i$ from $2$ to $1$ by a merge of the resulting $1$ into another $a_j$; any other decrease of an $a_i$ or a merge of an $a_i$ and $a_j$ by the merge of two entries $1$ if possible ($k\geq1$) or else merge an $a_i$ and $a_j$ if possible ($n\geq2$), or else decrease the unique remaining number making it even.
• (to be continued...)

Note that the minimal possibilities for $(a_1,\ldots,a_n)$ here are $(4)$, $(3,2)$, and $(2,2,2)$. Anything that can be moved into a Bob-game is an Alice-game; this applies to any $(a_1,\ldots,a_n,1^{(2k+1)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, $(a_1,\ldots,a_n)\neq(2)$ (either remove or merge a $1$ so as to leave $a_1+\cdots+a_n+n-1$ even), and to any $(a_1,\ldots,a_n,1^{(2k)})$ where $k\geq0$, $n\geq1$, $a_n\geq2$, and $a_1+\cdots+a_n+n-1$ odd (either merge two of the $a_i$ or two entries $1$, or if there was just an odd singleton, decrease it). All cases $(3,1^{(l)})$ and $(2,2,1^{(l)})$ are covered by this, in a manner depending on the parity of $l$. It remains to classify the configurations $(2,1^{(l)})$ and $(1^{(l)})$. Moving outside this remaining collection always gives some Alice-game $(3,1^{(l)})$ or $(2,2,1^{(l)})$, which are losing moves that can be ignored. Then we complete our list of Bob-games with:

• $(1^{(3k)})$ and $(2,1^{(3k)})$ with $k>0$. Bob wins game $(1,1,1)$ by moving to $(2)$ in all cases. Similarly he wins other games $(1^{(3k)})$ by moving to $(2,1^{(3k-3)})$ in all cases. Finally Bob wins $(2,1^{(3k)})$ by moving to $(1^{(3k)})$ (unless Alice merges, but this also loses as we already saw).

Answer 2

Here is an almost complete solution.

If there is only one integer, then clearly it depends on the parity of the number to determine who wins. If the number is odd then Alice will win. If the number is even then Bob will win.

If there are two integers, then it depends on the parity of the sum of the two numbers $\Sigma$. There is one combine and $\Sigma$ reductions so the game will be won by Alice if $\Sigma + 1$ is odd. This will be true as long as there is not an opportunity to remove one of the integers (by reducing it to zero) before there is a chance to combine. It is sufficient to require that none of the integers are $1$.

Let us now prove this strategy by induction.

Suppose the game is played with $N$ positive integers greater than $1$. Call the sum of the $N$ integers $\Sigma$. Then Alice has a winning strategy if and only if $\Sigma + N - 1$ is odd.

Proof: This is clearly true for $N = 1$. Suppose that the statement holds for $N$ and consider $N+1$. If $\Sigma + N$ is odd, then Alice can choose to combine two integers on her first turn. This reduces to the case of $N$ numbers with $\Sigma + N - 1$ even. Since Bob is now starting, from the induction hypothesis, he loses.

Conversely suppose that $\Sigma + N$ is even. If Alice chooses to reduce a number by $1$, then Bob chooses to combine two numbers. Then we have $N$ numbers with $\Sigma + N - 1$ being even. It is now Alice's turn and she loses. Alternatively if Alice chooses to combine two numbers, then by the induction hypothesis $\Sigma + N$ is odd with Bob starting. Therefore Bob wins.

This leaves the problem of when the $N$ numbers contain $1$s.