2
$\begingroup$

In sprague-grundy , I've seen that the answer is the XOR of all the numbers of coins in each pile. But what if a player is only allowed to remove at least one and at most half of the coins from each pile? Suppose if a pile is contain 7 coins than at least 1 and at most 3 ($\lfloor\frac72\rfloor$) coins can be removed. If the number is 6 then 1 to 3.

If the number of coins is 1 in a pile than only 1 coin can be removed(not $\lfloor\frac12\rfloor$), otherwise the above rule is applied.

  • 1
    I wrote [a detailed article about the Sprague-Grundy theory](http://blog.plover.com/math/sprague-grundy.html) that explains how to use it to analyze any impartial game, including yours. The example is a different game, but the application to your game is straightforward. You might find this article helpful.2012-11-01

1 Answers 1

4

It sounds like you're asking about a variant of Nim in which the legal moves on a heap of $n$ beans are to either remove $1$ bean, or to remove no more than half the beans. As you already know, for Nim one defines the nim-sum of two heap sizes as their binary XOR; the nim-value of a position is then the nim-sum of all the heap sizes; a winning position is just one with a nonzero nim-value; and a winning move is a move that leaves the nim-value at zero. The most fundamental result in the theory of impartial games is that any position has an associated nim-value that is the nim-sum of the nim-values of its components. This is not always useful, because the components are not always easy to identify, but in your case each heap is still a single component. The only difference is that the nim-value of a single heap in your game will be $f(n)$ instead of $n$, for a function $f(n)$ given by $ f(n)=\text{mex}\{f(n-k):k=1\vee 2k\le n\},$ where the "mex" of a set of natural numbers is the minimum excluded value. So $ \begin{eqnarray} f(0)&=&\text{mex}\{\}=0 \\ f(1)&=&\text{mex}\{0\}=1 \\ f(2)&=&\text{mex}\{1\}=0 \\ f(3)&=&\text{mex}\{0 \}=1 \\ f(4)&=&\text{mex}\{0,1 \}=2 \\ f(5)&=&\text{mex}\{1,2\}=0 \\ f(6)&=&\text{mex}\{1,2,0\}=3 \\ f(7)&=&\text{mex}\{2,0,3\}=1 \\ f(8)&=&\text{mex}\{2,0,3,1\}=4 \\ f(9)&=&\text{mex}\{0,3,1,4\}=2 \\ f(10)&=&\text{mex}\{0,3,1,4,2\}=5 \\ f(11)&=&\text{mex}\{3,1,4,2,5\}=0 \\ f(12)&=&\text{mex}\{3,1,4,2,5,0\}=6 \end{eqnarray} $ and so on. The losing single-heap sizes are those with nim-value zero: $2,5,11,...$; each is double the previous size plus one.


Update: Looking further at the sequence of nim-values reveals the pattern. At each odd $n=2k+1$, the size $k$ becomes unreachable, and as a consequence $f(2k+1)=f(k)$. At each even $n=2k$, a new value is attained: $f(2k)=k$ for $k>1$. This recursion makes it easy to determine the nim-value for any $n$: $f(1)=1$, $f(0)=f(2)=0$, $f(2k+1)=f(k)$ for $k>1$, and $f(2k)=k$ for $k>1$.

  • 0
    thanks a lot. that's exactly what i needed,2012-11-01