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?

  • $\begingroup$ This appears to be a question from a programming puzzle; see here. $\endgroup$ – Douglas S. Stones Nov 4 '12 at 6:01
  • 1
    $\begingroup$ Moreover, your question here is identical to this; your question here is identical to this. None of which give any attribution or display any attempt to answer the question. $\endgroup$ – Douglas S. Stones Nov 4 '12 at 6:16
  • $\begingroup$ @DouglasS.Stones These are archived questions. They are not part of any live tournaments. Hence there is no harm in asking any of these for an optimal solution. $\endgroup$ – Adwait Kumar Nov 4 '12 at 6:29
  • 2
    $\begingroup$ So, why not just say where it's from when you ask the question? (And, ideally, where you're stuck in solving the problem.) It helps whoever might answer the question. $\endgroup$ – Douglas S. Stones Nov 4 '12 at 7:55
  • 2
    $\begingroup$ The concept of "random positive integer" is not defined: there is no uniform probability distribution on the positive integers. $\endgroup$ – Carl Mummert Nov 4 '12 at 12:47

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.