Nim game for odd number of stones

Question

Consider the classical Nim game with total number of stones being odd. Then the first players wins, of course, what follows from the general description of winning positions. But is there some shorter (independent of full theory) explanation of this fact, maybe with implicit strategy or whatever?

Answer 1

The following strategy-stealing argument is similar to the one in my answer to "An unfair game involving an odd number of pieces of chocolate."

Inductively assume that all positions with a smaller odd number of stones are a win for the first player.

Consider taking one stone from a pile of odd size. If this is a winning play, we are done. If not, then your opponent has a winning response. This must not be an odd number of stones by induction. To have a chance of winning, your opponent must take an even number of stones. Now, try to take an even number of stones as long as possible, and your opponent's winning strategy must be to play even moves until you make another odd play. En route to winning, your opponent has to force you to take an odd number of stones while only taking even amounts.

To create a winning strategy, you steal this response to taking one stone from an odd pile. If your opponent took $2n$ from an originally even pile as a response to your first move, then it must be a winning first play for you to take $2n-1$ from that pile, then copy the strategy for forcing you to take an odd number of stones using only even moves. If your opponent took $2n$ from an originally odd pile (including the one from which you took a stone) as a response to your first move, then it must be a winning play for you to take $2n+1$ from that pile, then copy the strategy. This means you can leave an even number of stones after each move, and you can force your opponent to take an odd number of stones at some point. By induction, this gives you a winning position.

This theft works because you never change the greatest even integer smaller than each heap size. Every even move available to your opponent after you took one stone from an odd pile is available to you, and there are no extra even moves available for your opponent. $\square$

While this argument didn't require an understanding of the solution to Nim, it is easy to see what is going on when you understand that the second player wins are positions with balanced Nim sums. If you take one stone from an odd pile, you balance the ones digit without changing anything else. Your opponent's winning play, if any, tells you how to balance the other digits. A first play which takes one more or one less stone depending on the original parity of that heap balances all digits. For example, from $\star15 \star12 \star5 \star 3,$ suppose you take $1$ from $\star5$. Your opponent balances the position by taking $4$ from $\star15$, $\star12$, or $\star4$. This tells you that in the original position, taking $5$ from $\star15$ or $\star 5$, or taking $3$ from $\star 12$ will create a balanced position.

Answer 2

I am skeptical that there will be such an argument. The reason is that the winning Nim strategy is essentially unique. Namely, a Nim position is balanced if the binary digits of the heap sizes have altogether an even number of $1$s in each bit position, and the Nim theory consists of the facts that (1) any move on a balanced position will unbalance it, and (2) every unbalanced position has a balancing move. So the winning strategy is to leave balanced positions, which will ensure that you have the last move. It is easy to see that any Nim position with an odd number of stones must be unbalanced.

If someone were to describe as you request a simple winning strategy from a Nim position with an odd number of stones, then this strategy had better be sure to leave a balanced position, because if it doesn't, then the second player will be able to balance it and therefore win. So it would seem that any description of a winning strategy had better engage with the main ideas of the usual winning strategy or something equivalent to it.

So I don't think there will be an argument for an implicit strategy that avoids the balanced position concept. But I would be delighted to be proved wrong...

Answer 3

This doesn't answer the OP's question, but it occurred to me (while trying to answer the question) that there's a nice strategy-stealing argument in a somewhat artificial setting: Suppose one pile has more than half of all the stones. Then the first player has a winning strategy.

It's actually (I think) a little tricky to show that the usual analysis guarantees a first-player win: You need to show that the binary number for the dominant pile has a 1 where all the other piles' numbers have a 0. But here's the strategy-stealing argument:

Suppose there are $n+1$ piles of size $p_0,p_1,\ldots,p_n$ with $p_0 \gt P=p_1+\cdots+p_n$. The first player's opening move will be to take some number $1\le k\le P+1$ from pile "0." If the second player had a winning strategy, it couldn't possibly be to take additional stones from pile 0, because the first player could have stolen that move directly. This leaves the second player with only $P$ possible responses. A winning strategy, if there were one, would be to assign one of these responses to each of the first player's opening moves. (There may, in principle, be many many ways of making the assignment, but we need only imagine that the second player has decided in advance, "If the first player does this, I'll do that.") By the pigeonhole principle, there would be two numbers, $1\le i \lt j \le P$ for which the second player's move would be the same. There's the opening for the heist: First take $i$ stones from pile 0, then take $j-i$ on the next move.