Alice and Bob Game 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 ﬁrst) to either:

  
*
  
*Decrease a number by one.  
  
*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 ﬁnally 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?

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

