2
$\begingroup$

This is a follow-up question of my previous question : Optimal strategy for this Nim generalisation?

Consider the following game:

There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to N piles (at least 1). It is allowed to remove a different amount of stones from each of the up to N piles. The first player that can't move loses.

Given $N$, the number of piles $K$, and the sizes of the piles $k_1,k_2,...,k_K$, what is the sprague-grundy value/Nimber value of this game?

The optimal strategy is explained in my previous question and here: http://en.wikipedia.org/wiki/Nim#Index-k_Nim

$\endgroup$
2
$\begingroup$

As described in wikipedia: Convert all $k_i$ into binary. For each bit position, count how many $k_i$ have a $1$ bit at that position. If their number is a multiple of $N+1$ for all bit positions, then the game is lost. Otherwise it is possible by a suitable choice of piles to move to a lost position: Start with the highest bit that gives a nonzero count; by assumption there are enough piles with this bit set, so for these piles "unsetting" this bit is a decrease of number and hence a valid move (even if we should decide to "set" some lower bits); continue to lower bit positions.

So this settles, which positions are equivalent to $*0$: Those where all bit-position-sums are $0\pmod{N+1}$. In general, we need to look for the smallest unreachable nimber (mex). Let's numerically explore the case $N=2$, $K=3$ as a toy example.

  • Clearly, $(*a,*b,*c)\approx *(a+b+c)$ if one of $a,b,c$ is zero.
  • As seen above, $(*a,*a,*a)\approx *0$
  • By induction on the sum, we quickly find the bound $d\le a+b+c$ if $(*a,*b,*c)\approx *d$
  • If $a=1\le b\le c$ and $c>1$, we can move to $(*1,*1,*1)\approx * 0$, as well as $(*1,*0,*t)\approx *(1+t)$, $0\le t\le c$, as well as $(*0,*t,*c)\approx*(t+c)$, $0\le t\le b$. We conclude $(*a,*b,*c)\approx *(a+b+c)$
  • If $a=2\le b\le c$ and $c>2$, we can move to $(*2,*2,*2)\approx * 0$, as well as $(*2,*0,*t)\approx *(2+t)$, $0\le t\le c$, as well as $(*1,*t,*c)\approx*(1+t+c)$, $0\le t\le b$. We conclude that either $(*a,*b,*c)\approx*1$ or $(*a,*b,*c)\approx *(a+b+c)$. In fact, we have $(*2,*2,*3)\approx *1$ because in this case the list of considered moves is exhaustive; in all other cses, we can move to $(*2,*2,*3)\approx *1$ and conclude $(*a,*n,*c)\approx *(a+b+c)$.
  • More generally, if $1\le a\le b\le c$ and $c>a$ and $(*a,*b,*c)\approx *d$, then $0<d<a$ or $d=a+b+c$; and $d<a$ only if $b=a$ or $b=c$. This follows by induction on $a$ because we can move to $(*a,*a,*a)\approx *0$, as well as $(*a,*0,*t)\approx*(a+t)$, $0\le t\le c$, as well as $(*0,*t,*c)\approx *(t+c)$, $0\le t\le b$, as well as $(*t,*(b-1),*c)\approx*(t+b+c)$, $0\le t<a-1$; as $a<c$, also one of $(*(a-1),*b,*c)\approx *(a+b+c-1)$ (if $b<c$) or $(*a,*(b-1),*c)\approx*(a+b+c-1)$ (if $a<b-1$). If $b=a$, we have considered all moves (up to symmetry $a\leftrightarrow b$) (It seems I need to take a good night of sleep before continuing - there are a few borderline cases)

The rest is not an answer, but rather an overlong comment that states that the application of Sprague-Grundy is not trivial. Especially, if the "sub-games" are not already Nim games, one cannot simply replace each of them with the equivalent nimber! (And I am afraid that this fact does make this an answer to the question the OP is really interested in).

Definition. Let $G_0,G_1,\ldots, G_n$ be two impartial games. Define the game $G_0\vee G_1\vee\ldots \vee G_n$ (to make a notational distinction to the disjunctive sum $G_1+G_2+\ldots $ where a move is made in exactly one of the summand games) that has as positions all tuples $\langle p_1,p_2,\ldots, p_n\rangle$ where $p_i$ is a position of game $G_i$ and a move $\langle p_1,p_2,\ldots,p_n\rangle\to \langle q_1,q_2,\ldots,q_n\rangle$ is valid iff $p_i=q_i$ for all but either one or two indices $i$, and for these exceptional $i$, the move $p_i\to q_i$ is a valid move in $G_i$. In other words: All games are played in parallel and a move in the combined game consists of moving in either one or two of the games.

Proposition. The $\vee$ operator does not commute with equivalence. That is, $G_i\approx H_i$ does not imply that $G_1\vee\ldots \vee G_n\approx H_1\vee \ldots \vee H_n$.

Proof: First consider $ *0\vee *1\vee *1\vee *1$. Any valid first move in this game produces (up to reordering) either $*0\vee*0\vee*1\vee*1$ or $*0\vee*0\vee*0\vee*1$ and allows the second player to move to $*0\vee*0\vee*0\vee*0$ and win. Hence $ *0\vee *1\vee *1\vee *1$ is won for the second player.

Now consider the game $G=\{*1\}$, i.e. the only valid move for the first player produces $*1$, which allows the second player to win. Since the only nimber that is lost for the first player is $*0$, we conclude that $$\tag1G\approx *0.$$ However, in the game $G\vee *1\vee*1\vee*1$, the first player can move to $*1\vee*0\vee*1\vee*1$ and hence can force a win (see above). We conclude that $$\tag2G\vee *1\vee *1\vee*1\not\approx *0\vee *1\vee *1\vee*1.$$ But $(1)$ and $(2)$ together show the claim. $_\square$

$\endgroup$
  • $\begingroup$ The sprague-grundy theorem states that every impartial game is equivalent to a nimber. So we can apply the theorem here. For example the nimber value of 3 piles with 2 stones each is $0*$ because is is a losing position. 1 pile with 1 stone is the nimber $1*$. The method you gave settles if a position is a losing or winning position aka the nimber is $0*$ or something else. So if I am not mistaken you didn't completely answer the question, right? $\endgroup$ – Ward Beullens Sep 2 '14 at 18:59
  • $\begingroup$ Maybe this makes it a bit more clear: I want the nimber value for analysing the disjunctive sum "$+$" of games, not "$\vee$" using your notation $\endgroup$ – Ward Beullens Sep 2 '14 at 19:02
  • $\begingroup$ @WardBeullens I'm not sure. The way I see it, "$+$" is the case $N=1$ and "$\vee$" is the case $N=2$, isn't it? The first part of my answer rephrases the WP article, and I don't see what you are asking beyond that. The second part discusses why this is not directly applicable to A Game of Knights (even if you never mentioned that), where the sub-games are equivalent but not equal to nimbers. $\endgroup$ – Hagen von Eitzen Sep 2 '14 at 19:26
  • $\begingroup$ Oh, now I see your point - wait. $\endgroup$ – Hagen von Eitzen Sep 2 '14 at 19:28
  • $\begingroup$ This question is not directly about "A Game Of Knight" $\endgroup$ – Ward Beullens Sep 2 '14 at 19:35

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.