Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I wrote a detailed article about the Sprague-Grundy theory 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. –  MJD Nov 1 '12 at 12:55

1 Answer 1

up vote 4 down vote accepted

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$.

share|improve this answer
2  
The losing positions $2, 5, 11, 23, 47\dots$ are, in binary, $10, 101, 1011, 10111, 101111\dots$. In other words, they are $2^{n} + 2^{n-1} - 1$ for $n \ge 1$. –  ShreevatsaR Nov 1 '12 at 13:16
    
thanks a lot. that's exactly what i needed, –  johnsmith Nov 1 '12 at 19:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.