3
$\begingroup$

Is there a name (and strategy) for this nim variant?

There are $n$ lists of objects, say $L_1,\ldots,L_n$ where $L_i = \{a_{i,1},a_{i,2},\ldots,a_{i,n_i}\}$. Players take turns choosing a list and any number of sequential elements to remove. If they do not remove from one of the endpoints of the list, the list becomes effectively partitioned into two lists.

Of course, there is a "regular" version of the game where the last player to remove an element wins, and the "misere" version where the last player to remove an element loses.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ At least the regular version has the same strategy as ordinary nim. To see this, note that if $b+c<a$, then the XOR of the binary representations of $b$ and $c$ will be strictly smaller than that of $a$. For the misere as well: you follow the same strategy as in the regular case until your opponent presents you a single row. Now you take all but one item from that row. $\endgroup$
    – Sebastian Goette
    Commented Oct 28, 2015 at 19:08
  • 2
    $\begingroup$ This sounds like an octal game with the octal code 0.77777... -- see en.wikipedia.org/wiki/Octal_game $\endgroup$
    – Max Alekseyev
    Commented Nov 5, 2015 at 4:27

1 Answer 1

Reset to default
2
$\begingroup$

Sebastian Goette and Max Alekseyev together answered this question almost completely.

The game you describe is equivalent to the Octal Game "$0.7777\ldots$". I do not believe it has another name.

Under normal play, it is easy to see that a single list of $n$ objects is equivalent (in the sense of the Sprague-Grundy theory) to a Nim heap of size $n$: By induction all the moves that don't split up the list are to the Nim heaps of size $<n$. And as Sebastian Goette points out, if $b+c<a$ then $b\oplus c<a$, so that a Nim heap of size $n$ won't appear among the options.

Since the same is so similar to Nim, the misère play should be similar as well. You should play as in normal-play Nim until your prescribed move would leave only lists of size 1, and then make a move which leaves your opponent an odd number of such lists.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .