0
$\begingroup$

Given $3$ piles containing $\{27, 24, 36\}$ pebbles in each. Players can take $\{1,4,5\} , \{2,3,7\}, \{3,4,6\}$ from first, second and third piles respectively.


I need to show that Sprague-Grundy function gives me the winning and loosing position of the compound game.

I started by drawing each sequence separately and observing the pattern. I found this repetitive Sprague-Grundy values from $0$ to $m,n,k$ as follows:

$\text{pile #1} \{0,1,0,1,4,5,4,5\}$, $\text{pile #2}\{0,0,2,2,4\}$, and $\text{pile #3}\{0,0,0,3,3,3,6,6,6\}$.

So the initial Sprague-Grundy is $g(27,24,36) =$ g1(27)^g2(24)^g_3(36) = 1^3^0 = 6, which is a losing position. From this state $(27,24,36)$ I can move to the winning position $(27,22,36)$ because it is a movable step and its Sprague-Grundy value is 1^1^0 = 0; At this point I know why result $0$ of xor gives winning position in nim game, there is no restriction to number of pebbles
to remove, but in take away game there is restriction.


Why even with this restriction there exists a move from loosing position(N) to winning position(P) in compound subtraction game?

$\endgroup$
  • $\begingroup$ I haven't been introduced to "Sprague-Grandie". Could you at least give a reference (I would give you a reference if had to make development about the not so well known von Hindenburg - Nekrasov - Yamamoto formula) $\endgroup$ – Jean Marie Mar 2 '17 at 23:37
  • $\begingroup$ Sure here $\endgroup$ – Baimyrza Shamyr Mar 2 '17 at 23:41
  • $\begingroup$ It is the Sprague-Grundy theorem, as in the Wikipedia page you cite. $\endgroup$ – Ross Millikan Mar 3 '17 at 0:28
1
$\begingroup$

The point of the Sprague-Grundy theorem is to calculate the nimber, the number of stones in a pile of unrestricted nim, that corresponds to a pile of stones in your game. The nimber of a position is the minimum nimber that you cannot move to from that position. In regular nim, a pile of six stones can move to $0,1,2,3,4,5$, so the nimber is $*6$. Taking your second game, a pile of $0$ or $1$ stones is $0$ because you can't move at all. A pile of $2$ stones is $*1$ because you can move to $0$ but not to $*1$. A pile of $3$ stones is $*1$ as well because both moves are to $0$. A pile of $4$ stones is $*2$ because you can move to $0$ by taking $3$ or to $*1$ by taking $2$. You need to recalculate all of your nimber values.

Assuming the values of the three piles were $*1,*3,0$, the value of the group of three piles would be $XOR(*1,*3,0)=*2,$ not $*6$. You could reach a winning position by moving from $*3$ to $*1$ because $XOR(*1,*1,0)=0$. You are guaranteed to be able to do this because $*3$ must be able to move to any of $0,*1,*2$. Then if your opponent takes one $*1$ to $0$ you take the other. Otherwise he must take the $0$ to some nimber which you can take back to $0$ or he can take one of the $*1$s to a higher nimber and you can take it back.

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