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?

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.
