2
$\begingroup$

Say that there are two players, and two piles of chips. The first pile of chips has $m$ chips in it, where $m \geq 0$, but the second pile has exactly $1$ chip in it. The players alternate in taking turns removing any number of chips they'd like from one of the piles. So far, so Nim.

Add an additional allowed move: a player can choose to remove one chip from both piles, if such a move is possible.

Can the game with the additional rule be analyzed as two separate, but parallel games? My rough intuition for this is that it is not possible to do so as there is a move that affects both piles, so there is no way to consider the two piles as being independent of each other?

However, I am not sure how to formally prove or disprove this "intuitive conjecture". In general, is it even always possible to break a game down into a disjunctive sum of games?

$\endgroup$
  • $\begingroup$ You might want to look at the analysis of Wythoff's game, of which your game is a special case. $\endgroup$ – MJD Sep 27 '18 at 3:33
  • $\begingroup$ @MJD sure, but that's just a big generalization about which little is known. I want to see if the special case can be studied in a way that allows us to quickly apply the Sprague-Grundy theorem. $\endgroup$ – user89 Sep 27 '18 at 4:52
  • $\begingroup$ Looks to me as if the Grundy number of (m,1) is $m - 2$ when $m = 2 \mod 3$ and $m-1$ otherwise, i.e. 1,2,0,4,5,3,... for m=0,1,2,... $\endgroup$ – pepster Sep 27 '18 at 6:32
  • $\begingroup$ @pepster Yes, but that is only an observation. Also, it is $m + 1$, not $m - 1$? One must still prove this. $\endgroup$ – user89 Sep 27 '18 at 15:39
  • $\begingroup$ Yes, Typo, m+1. It is quite easy to prove by induction. $\endgroup$ – pepster Sep 27 '18 at 19:59
1
$\begingroup$

Background and Notation

A single Nim heap of size $n$ will be denoted "$*n$", with $*1$ abbreviated "$*$" and $*0$ abbreviated "$0$".

"$+$" denotes the disjunctive sum, so that $*+*3$ is a Nim position with one heap of size $1$ and one heap of size $3$.

This is not standard, but we can take a page from Topology and call a game $G$ connected if it is not isomorphic to a disjunctive sum other than $G+0$ and $0+G$.

Edit: "$\vee$" denotes a variant of the selective sum, so that when $G$ and $H$ are nim heaps, $G\vee H$ is a game in which a player can move in $G$ or $H$ or both simultaneously but if both then only one token/chip is removed from each.

The game described by user89 is one in which there are two Nim heaps (one being $*$), and a player can move in one or both of them on their turn. This means that this game with $n+1$ chips is $*n\vee*$.

Question:

Is $*n\vee*$ connected for each $n$?

Nim heaps are connected

$0$ and $*$ are connected since a nontrivial disjunctive sum must have a line of play (a "run") of length at least $2$, since each summand must have at least one move.

For $n\ge2$, $*n$ is connected since it has a move to $0$, but a disjunctive sum $G+H$ does not if neither $G$ nor $H$ are $0$.

The OP's game is connected

Note that $0\vee*$ is isomorphic to $*$, which is connected. Note that $*\vee*$ is isomorphic to $*2$, which is connected.

If $n\ge2$, then $*n\vee*$ has a move to $0\vee*$ and a move to $*\vee*$. Suppose $*n\vee*=G+H$ with $G,H$ nonzero. Since there is a move to $*$, then one of $G$ and $H$ must be $*$ since otherwise there is no run of length $2$. Suppose $H$ is $*$. But, then, since there is a move to $*2$, and $*2$ is connected, we $G$ must be $*2$. For $n>2$ we have a contradiction since $*n\vee*$ has a longer run than any run of $*2+*$.

For $n=2$, we have a contradiction since $*2+*$ has a move to $*+*$, but $*2\vee*$ only has moves to $*2$ (two of them) and to $*$.

A generalization

Suppose, for sake of induction, that for some $k\ge 1$ we have shown that $*n\vee*k$ is connected. Then if we have a position like $*m\vee*(k+1)$, it has moves to $*(k+1)$ and to $*m\vee*k$, both of which are connected, distinct (unless $m=1$ and $k=1$, which was handled earlier) and nonzero. Then if $*m\vee*(k+1)$ is a disjunctive sum, it must be the sum of those two. But the length of the longest run in the disjunctive sum is $m+2k+1$, and the length of the longest run in $*m\vee*(k+1)$ is the smaller $m+k+1$.

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