5-pile Same-Nim

If a Same-Nim board position $G$ has Nim-score $N(G) \neq 0$ , then two of the five piles are equal, and hence the Nim-sum of the sizes of the other three piles must be equal to $N(G)$ , and is therefore nonzero. Thus there is a standard Nim move on those three piles which gives them a Nim-score of $0$ ; since this move does not affect the two equal piles, this is a legal Same-Nim move, and the Nim-score of the Same-Nim board is now $0$ .

On the other hand, if $G$ is a Same-Nim board position with Nim-Score $N(G)=0$ , then any possible legal Nim move, and so certainly any legal Same-Nim move, will result in a Same-Nim board position with nonzero Nim-score.

Thus the additional requirement of Same-Nim is largely unimportant, since the opening positions that are winning ones for the first player are those with nonzero Nim-score, and the losing positions are those with Nim-score zero. The Nim-score of the board position $(10,10,a,b,c)$ is the Nim-sum $a \oplus b \oplus c$ . Thus losing positions for the first player are those for which $c = a \oplus b$ . The following table for $a \oplus b$ : $\begin{array}{|c|cccccccccc|} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 & 9 & 8 & 11 \\ 2 & 3 & 0 & 1 & 6 & 7 & 4 & 5 & 10 & 11 & 8 \\ 3 & 2 & 1 & 0 & 7 & 6 & 5 & 4 & 11 & 10 & 9 \\ 4 & 5 & 6 & 7 & 0 & 1 & 2 & 3 & 12 & 13 & 14 \\ 5 & 4 & 7 & 6 & 1 & 0 & 3 & 2 & 13 & 12 & 15 \\ 6 & 7 & 4 & 5 & 2 & 3 & 0 & 1 & 15 & 14 & 12 \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 & 15 & 14 & 13 \\ 8 & 9 & 10 & 11 & 12 & 13 & 14& 15 & 0 & 1 & 2 \\ 9 & 8 & 11 & 10 & 13 & 12 & 15 & 14 & 1 & 0 & 3 \\ 10 & 11 & 8 & 9 & 14 & 15 & 12 & 13 & 2 & 3 & 0 \\ \hline \end{array}$ shows that there are $60$ triples $(a,b,c)$ with $1 \le a,b,c \le 10$ and $c = a \oplus b$ . Thus there are $940$ winning opening positions for the first player.

Winning Formula

Theorem . In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum (or vastly known as xor. $\oplus$ , sum) of the sizes of the heaps is nonzero. Otherwise, the second player has a winning strategy.

Proof : Notice that the nim-sum ( $\oplus$ ) obeys the usual associative and commutative laws of addition ( $+$ ), and also satisfies an additional property, $x \oplus x = 0$ (technically speaking, the nonnegative integers under $\oplus$ form an Abelian group of exponent 2).

Let $x_{1}$ , $\dots$ , $x_{n}$ be the sizes of the heaps before a move, and $y_{1}$ , $\dots$ , $y_{n}$ the corresponding sizes after a move. Let $s = x_{1} \oplus \dotsm \oplus x_{n}$ and $t = y_{1} \oplus \dotsm \oplus y_{n}$ . If the move was in heap $k$ , we have $x_{i} = y_{i}$ for all $i \neq k$ , and $x_{k} > y_{k}$ . By the properties of $\oplus$ mentioned above, we have

$t = 0 \oplus t$
$= s \oplus s \oplus t$
$= s \oplus (x_{1} \oplus \dotsm \oplus x_{n}) \oplus (y_{1} \oplus \dotsm \oplus y_{n})$
$= s \oplus (x_{1} \oplus y_{1}) \oplus \dotsm \oplus (x_{n} \oplus y_{n})$
$= s \oplus 0 \oplus \dotsm \oplus 0 \oplus (x_{k} \oplus y_{k}) \oplus 0 \oplus \dotsm \oplus 0$
$= s \oplus x_{k} \oplus y_{k}$

(*) $t = s \oplus x_{k} \oplus y_{k}$ .

The theorem follows by induction on the length of the game from these two lemmas.

Lemma 1 . If $s = 0$ , then $t \neq 0$ no matter what move is made.

Proof : If there is no possible move, then the lemma is vacuously true (and the first player loses the normal play game by definition). Otherwise, any move in heap $k$ will produce $t = x_{k} \oplus y_{k}$ form (*). This number is nonzero, since $x_{k} \neq y_{k}$ .

Lemma 2 . If $s \neq 0$ , it is possible to make a move so that $t = 0$ .

Proof : Let $d$ be the position of the leftmost (most significant) nonzero bit in the binary representation of $s$ , and choose $k$ such that the $d$ -th bit of $x_{k}$ is also nonzero. (Such a $k$ must exist, since otherwise the $d$ -th bit of $s$ would be $0$ .) Then letting $y_{k} = s \oplus x_{k}$ , we claim that $y_{k} < x_{k}$ : all bits to the left of $d$ are the same in $x_{k}$ and $y_{k}$ , bit $d$ decreases from $1$ to $0$ (decreasing the value by $2^{d}$ ), and any change in the remaining bits will amount to at most $s^{d} - 1$ . The first player can thus make a move by taking $x_{k} - y_{k}$ objects from heap $k$ , then, by (*)

$t = s \oplus x_{k} \oplus y_{k}$
$= s \oplus x_{k} \oplus (s \oplus x_{k})$
$= 0$ .

Solution

So, based on the winning formula, we only need list of combinations of ( $a$ , $b$ , $c$ ) which makes $S = 0$ , where $S = 10 \oplus 10 \oplus a \oplus b \oplus c = a \oplus b \oplus c$ . To make every combinations have such property, we could make a simple list based on $a$ 's value,
for $a = 1$ , ( $b$ , $c$ ) would be permutation of ( $2$ , $3$ ), ( $4$ , $5$ ), ( $6$ , $7$ ), and ( $8$ , $9$ ),
for $a = 2$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $3$ ), ( $4$ , $6$ ), ( $5$ , $7$ ), and ( $8$ , $10$ ),
for $a = 3$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $2$ ), ( $4$ , $7$ ), ( $5$ , $6$ ), and ( $9$ , $10$ ),
for $a = 4$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $5$ ), ( $2$ , $6$ ), and ( $3$ , $7$ ),
for $a = 5$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $4$ ), ( $2$ , $7$ ), and ( $3$ , $6$ ),
for $a = 6$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $7$ ), ( $2$ , $4$ ), and ( $3$ , $5$ ),
for $a = 7$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $6$ ), ( $2$ , $5$ ), and ( $3$ , $4$ ),
for $a = 8$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $9$ ) and ( $2$ , $10$ ),
for $a = 9$ , ( $b$ , $c$ ) would be permutation of ( $1$ , $8$ ) and ( $3$ , $10$ ),
for $a = 10$ , ( $b$ , $c$ ) would be permutation of ( $2$ , $8$ ) and ( $3$ , $9$ ).
Therefore, there would be $4 * 3 * 2 + 3 * 4 * 2 + 2 * 3 * 2 = 60$ ways for the player that moves second to have foolproof winning strategy, which equivalent to $1000 - 60 = 940$ order of triples ( $a$ , $b$ , $c$ ) that makes the first player wins.

The main idea of this problem is that winning strategies in Same Nim correspond to winning strategies in regular Nim as long as the starting position has at least one pair of piles with the same number of stones.

In fact, we can prove this: Suppose $(a_1,a_2,...,a_n)$ is a position in regular Nim. Then $(b,b,a_1,a_2,...,a_n)$ is a losing position in Same-Nim if $(a_1,a_2,...,a_n)$ is losing. The analogous result is true if $(a_1,a_2,...,a_n)$ is winning. In other words, we can predict the result of a game of Same-Nim which begins with a pair of piles which contain the same number of stones by removing that pair of piles and looking at the resulting position in a game of regular Nim.

Proof: We treat the set of piles as two sets: pile $A = (a_1,a_2,...,a_n)$ and pile $B = (b,b)$ . Then the entire set (the position) is $A \cup B$ .

Suppose that $A$ is a losing position in regular Nim. It is clear that $B$ is a losing position in regular Nim, and so if the second player develops a winning strategy for each of the two positions separately, he can win by playing according to the winning strategy for the position that the first player played in. For example, if the first player plays some move in position $A$ , $A$ is transformed into a winning position (by the definition of a losing position) and then the second player has a winning move in $A$ , which he plays.

The added condition of Same-Nim does not change this game at all. The winning strategy for the second player in position $B$ is to ensure that the two piles have the same number of stones after his move, and so any move is possible in position $A$ at any point in the game if the second player plays optimally (since there will be at least one pair of piles which have the same number of stones, namely the two in position $B$ ).

Very similarly, we can show that if $A$ is a winning position in regular Nim, then $A \cup B$ is a winning position in Same-Nim. Essentially, since $A$ is winning and $A \cup B$ has a pair of piles which have the same number (the two piles in $B$ ), there is some move which transforms $A$ into a losing position with the second player acting as the first player, and so the second player loses, which means that $A \cup B$ is a winning position. This is precisely what we wanted to show. $\square$

We now apply this to the given games, namely those with starting position $(10,10,a,b,c)$ where $10 \geq a,b,c \geq 0$ . We showed above that a game of Same-Nim with a starting position of the form $(10,10,a,b,c)$ is losing if and only if $(a,b,c)$ is losing in regular Nim (replace $b$ with $10$ above). We can very simply calculate the number of losing positions in regular Nim with this form, using nim-sums, a simple computer program, or even brute-force, and we get that there are $60$ such losing positions. Since there are $1000$ total starting positions, and any of these $60$ losing positions in regular Nim is losing in Same-Nim, there must be $1000 - 60 = \fbox{940}$ starting positions in Same-Nim which satisfy the conditions of the problem and are winning.

This title is appropriate, as "Same-Nim" is just the same as standard 3-pile Nim on the three piles $a,b,c$ .

More specifically, if a position is $L$ (i.e. loses for the current player) in standard 3-pile, then it is also $L$ in Same-Nim, so long as the first two piles maintain equal sizes; and similarly for $W$ positions.

This is because if the first two piles have equal sizes then there are no restrictions on moves in the other 3 piles, so the player who would win the standard 3-pile Nim can execute his strategy without restriction; and if the losing player takes stones from one of the first two piles, the winning player takes the same number of stones from the other one of the first two piles, restoring his ability to continue his winning strategy on the last 3 piles.

We have looked at standard Nim in a Calvin vs Lino problem several weeks ago, and it turned out that a position is $L$ if and only if it has a "Nim-sum" of $0$ , where the Nim-sum is the binary XOR of the sizes of the piles.

Actually this is easy to prove: If the Nim-sum is $0$ then any move must toggle at least one bit leaving a non-zero Nim-sum. And if the Nim-sum is nonzero then the following move will make it $0$ : select a pile that has a $1$ -bit in the same position as the most significant bit of the Nim-sum, and remove the number of stones that is the XOR of that pile's size, and the Nim-sum.

Finally we just have to count how many positions have a Nim-sum of $0$ and subtract that from $1000$ .

I actually did this by counting positions with $a \le b \le c$ by inspection and then considering the number of combinations of each. The losing positions are:

(1,2,3) (1,4,5) (1,6,7) (1,8,9) (2,4,6) (2,5,7) (2,8,10) (3,4,7) (3,5,6) (3,9,10)

and each one has six possible orderings for a total of $60$ losing positions. So there are $\boxed{940}$ winning positions.