eXtreme Nim: A Game With *Lots* of Pebbles

Question

Two children are playing a game with several piles of rocks. Each turn they do the following:

• They choose some pile of rocks. They count how many rocks are in this - let this be $n$. We remove this pile.

• They may (optionally) then create as many new piles of rocks as the desire, each pile having less than $n$ rocks (not all new piles need to have the same amount of rocks).

For instance, starting from a pile of two rocks, the legal moves are:

• Remove the pile of rocks entirely.

• Remove the pile of rocks, and create any number of new piles, each containing $1$ rock.

The winner is the player to remove the last rock.

What is a winning strategy for the game? What are the winning positions? That is to say, if you have some number of piles and know how many rocks are in each, how can you know whether you can secure a win, and what the correct move to do would be?

(And yes, replacing a pile of two with $10^{100}$ piles of $1$ is legal, but very unsportsmanlike and never necessary in a winning strategy)

Answer 1

Call a position even if for every positive integer $n$, there are an even number of piles with exactly $n$ rocks. Call the position odd otherwise.

Claim 1: If a position is odd, there is a move which results in an even position.
From an odd position, find the largest $n$ such that there are an odd number of piles of size $n$, remove that pile, and for each $k<n$, create a single pile of size $k$ if and only if the number of piles of size $k$ that already exist is odd.

Claim 2: If a position is even, every move results in an odd position.
From an even position, if a player removes a pile of $n$ rocks, there will be an odd number of piles of $n$ rocks remaining.

This shows that:

The first player has a winning strategy if and only if the position is odd.

The winning strategy is to make a move resulting in an even position. This is always possible by Claim 1, and Claim 2 shows that your opponent's move must again result in an odd position. This means your opponent can never move into an even position, and therefore can never win (as removing the last rock makes the position even).

Answer 2

One approach to this problem whereby we can deduce the answer without any initial guessing is to calculate the nimber $f(n)$ of a game starting with $n$ pebbles in a single pile. This is helpful because our game has the property that, when we have two piles, its the same as if we had two games simultaneously, where each player chose to play in one, and the winner was the person who made the last legal move. That is to say, the nimber of a game with multiple piles is the nim-sum of the nimbers of each pile.

To calculate the $f(n)$, we compute the nimber of every position that can be moved to from a pile of $n$, then calculate the minimal nimber not achieved in that set - as is the standard method in impartial games. Given that a pile of $n$ may be replaced by piles $s_1,\ldots,s_k$ where all values of $s_i$ are less than $n$ and that all possible moves are of this form, we may write $$f(n)=\operatorname{mex}(\{f(s_1)\oplus f(s_2)\oplus \ldots \oplus f(s_k):0<s_i<k\})$$ where $\oplus$ is the nim-sum. Using the above, we may inductively show that $f(n)=2^n$ for $n\geq 1$. This is because if we let $s_k$ be the position of the ones in the binary expansion of $n'$ for some $n'<2^n$, then the expression $f(s_1)\oplus\ldots\oplus f(s_k)$ will equal $n'$ by inductive hypothesis. Thus, starting from position $n$, one can move to a position with any nimber less than $2^n$. However, since $2^n$ has a $1$ in the binary expansion in a position where no smaller $2^k$ does, it is not such a nim-sum, and hence must be the mex of the set.

Knowing this, we can say that a losing position is one whose nimber is $0$. Given that $f(n)=2^n$ happen to be linearly independent with respect to the nim-sum, it follows that the only way for this to happen is if there are an even number of piles with $n$ rocks for all $n$. Knowing that these are exactly the losing positions, we find that a winning position is one where there is some - and the proper move is to move to a losing position, meaning you must take the largest $n$ such that there are an odd number of piles with $n$ rocks, remove it, and ensure that all $k<n$ have an even number of piles of $k$.

Answer 3

Winning positions : (A) those that have only odd number of 1-piles or (B) those that have odd number of N-piles (for some N) and even number of X-piles , for all other values of X or (C) those that have odd number of N-piles and odd number of M-piles and even number of X-piles for all other values of X or (D) those that contain an odd number of Y-piles for 3 or more values of Y, and even number of X-piles for all other values of X.
Winning strategy :
Case (A) : keep taking out one pile and give you opponent and even state. Your opponent will give you an odd state, so take the last pile and win the game.
Case (B) : Select the odd number of N-piles and remove it.
Now, we have even number of N-piles and even number of all other X-piles.
If your opponent removes one of these, you also remove one of these, so we always give him even number of X-piles.
If your opponent converts one of these piles to small piles, you also convert one of these to the same number of smaller piles, so we always give him even number of X-piles.
If, from the even state, he takes the last but one, then you get the odd state, so you can also take one and win the game.
Case (C) : Take the larger odd number of N-piles and convert that into one M-pile, so the state now has an even number of N-piles and an even number of M-piles.
Now all piles are even for your opponent, who has to give you some odd state.
Move as per Case (B) or eventually Case (A) for a Win.
Till here, we can restrict the games moves to (1) remove a pile & (2) remove a pile and put back many piles of same size. This completes the winning strategy with that restriction.
When we have no restriction on the sizes of the piles we put back, then we can win in even more cases.
Case (D) : Remove the largest N for which we have odd number of N-piles.
Put back one pile each for the smaller odd-size piles of odd-count, thereby making all those piles have even-count, so we give an even state to our opponent who has to give back an odd state.
Move as per Case (C) or Case (B) or eventually Case (A) for a win.