What is the sprague-grundy value of these games?

Question

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

Answer 1

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$