Explosive Nim

Logic Level 5

In explosive Nim , the usual rules of Nim are followed. However, whenever a pile is exhausted, all other piles double in size. For example, from the position $1,2,3$ , taking a stone from the 2-pile acts usually to $1,1,3$ , but taking another stone from the 2-pile "explodes" the other piles, turning to $2,0,6$ .

Alpha and Beta play an explosive Nim on the piles $1, 2, 3, 4, \ldots, 2015$ . Alpha plays first. Will the game end, and who wins?

A. The game will end in finitely many moves, and Alpha wins
B. The game will end in finitely many moves, and Beta wins
C. The game will end in finitely many moves, but it cannot be known who wins
D. The game might not end, but Alpha wins in a finite number of moves
E. The game might not end, but Beta wins in a finite number of moves
F. The game might not end, and with perfect play the game will last forever

Clarification:

This is two questions in one.

The first question, "will the game end", means that "will the game end for any sequence of moves that Alpha and Beta play?" If there's any sequence of moves where Alpha and Beta can keep playing indefinitely, then the game might not end (the answer is one of D, E, F); if there's no such sequence, then the game will always end (the answer is one of A, B, C).

The second question, "who wins", means that "who wins if both players play perfectly ?" If there's any move that is not perfect (the moving player was winning before the move, but after the move it's their opponent that is winning), the whole play is not counted.

B E D C A F

1 solution

Ivan Koswara
Aug 8, 2015

First, we claim that the game must end.

On the $i$ -th move, let there be $p_i$ nonzero piles and let the total number of stones be $n_i$ . We claim that $2^{p_i} n_i$ is strictly decreasing. (If you want to be fancy, use $p_i \cdot \omega + n_i$ where $\omega$ is the smallest infinite ordinal.)

If the number of piles remain the same, the total number of stones clearly decreases, so $2^{p_i} n_i > 2^{p_i} n_{i+1} = 2^{p_{i+1}} n_{i+1}$ .

If the number of piles decrease, then the total number of stones doubled. But before the doubling, some of the stones are removed (the stones in the pile that becomes zero). So the doubling is not complete; that is, $2n_i > n_{i+1}$ , and thus $2^{p_i} n_i = 2^{p_i -1} (2n_i) > 2^{p_i - 1} n_{i+1} = 2^{p_{i+1}} n_{i+1}$ .

Thus the sequence $2^{p_i} n_i$ is strictly decreasing. But it is a sequence of nonnegative integers. By the well-ordering property, there can be no infinite strictly decreasing sequence on the nonnegative integers, thus the sequence is finite, meaning that the game ends.

This proves the claim, and thus only A, B, C remains. In fact, since this game must end for someone's win, the current position must be winning for one of the two players, so C is not the answer either. We only need to figure out whether it's Alpha or Beta that wins.

The trick is, we actually don't need to care about the doubling! Suppose a position has nim-sum 0. When all piles are doubled, the nimber of each pile is simply shifted one place to the left; the nim-sum remains 0. (For example, we have the piles $1 = 2^0, 2 = 2^1, 3 = 2^1 + 2^0$ . Doubled, they become $2 = 2^1, 4 = 2^2, 6 = 2^2 + 2^1$ . All powers of two gain one additional exponent, so everything still cancels.) Likewise, if a position has nim-sum not 0, after doubling the nim-sum remains not 0. (The nim-sum is doubled, however.)

Thus it suffices to assume that this is a regular Nim game. The nim-sum of $1, 2, \ldots, 2015$ is $0$ , so the second player wins; that is, Beta wins.

Moderator note:

An easier way to argue that the game must end, is that each pile can explode at most 2015 times, and so the game must end in at most $2^{2014} \times ( 1 + 2 + 3 + \ldots + 2015 )$ turns.

Good observation about the invariance of the Nimber.

What is a nim-sum?

Siva Budaraju - 4 years, 1 month ago

Explosive Nim

1 solution

Moderator note:

0 pending reports