2
$\begingroup$

Let us assume that we play a nim-game (last person who draws a card, wins) and are in a position $a_1, a_2$ (sizes of piles). Assume that we have nim-sum (NS) $a \neq 0$.

  1. How many moves are there?

  2. How many winning moves are there from this position?

Question 1: Since the sizes of my piles are $a_1,a_2$, there should be a total of $a_1+a_2$ moves that I could make, correct?

Question 2: If I want to win, I need to be in a position where every time it's my turn, the NS $\neq0$. Then, I need to make sure that every move I make creates a situation where the other person always gets a NS $=0$. We know that if the other person gets a NS $=0$, then when it's my turn it will always be true that the NS $\neq 0$, and this loop will continue until I win.

But how many winning moves are there? To go from a NS $\neq 0$ to NS $=0$, one winning strategy is to always take the pile with the biggest size (we know that $a_1\neq a_2$ when NS $\neq 0$), and re-arrange it in a way such that NS $=0$, but I'm in a bind as to how many winning moves there are.

EDIT: See this link for an explanation of the game and what the nim-sum is.

$\endgroup$
  • 1
    $\begingroup$ Ok, I think I get it... Since there are 2 piles, and you know that re-arranging the biggest pile in a particular way should give you a NS $=0$, there is always 1 winning move. This would also imply that the possibility to win with a random move is $\frac{1}{a_1+a_2}$. $\endgroup$ – armara Feb 22 at 13:37
1
$\begingroup$

There is only one winning move. I will use $+_2$ to indicate nim-addition. If we write the numbers in the piles in binary, then nim-addition is simply addition modulo $2$ in each bit, so that $+_2$ is associative and commutative. Say $$a_1+_2 a_2=x$$ Then $$(a_1 +_2 x)+_2 a_2 = a_1 +_2 (a_2+x) = x+_2 x = 0$$ so that we may nim-add $x$ to either pile to get to a winning position. However, such a move is legal only if it reduces the number of counters in the pile.

Say that the leading bit of $x$ occurs in position $n$. For bit positions to the left of $n$, $a_1$ and $a_2$ agree, and in bit position $n$ they differ. Say $a_1$ has a $1$ in this position, and $a_2$ has a $0$. Then $a_2 +_2 x> a_2$ so this is not a legal move, and $a_1 +_2 x< a_1,$ so this move is legal.

In the general case, where there may be $m$ piles, we see that there is a winning move in pile $k$ if and only if $a_k$ has a $1$ in bit position $n$, where the leading bit 0f $$a_1+_2a_2+_2\cdots+_2 a_m$$ is in position $n$.

Therefore, there are always an odd number of winning moves, and at most one such move in each pile.

$\endgroup$
0
$\begingroup$

Interesting question! How do you prove that you can rearrange the largest pile and always get the NS=0? And also then you know that is a least one winning move but could there maybe be more than one winning move?

$\endgroup$

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.