Nim games are two player strategy games where players take turns removing objects by some rules until none remain.
For this version, place N counters in a row numbered 1 to N.
A player's turn consists of taking either one counter or two counters from consecutive positions.
Whomever takes the last counter loses (this is called a misère game.)
If you were to play this game, for what values of N would you prefer go first and what should be your first move?
I wrote a program that looks at this NIM game variant up to N=30. The bottom line is that for N = 1, 4, 9, 12, and 20, you will lose if you go 1st (if the opponent plays right). For the other starting Ns, you are assured a win. How to win is given below.
(1,4,9,20,..?) does not present an obvious pattern. Further, it is not listed, per se, in the OEIS (n.b., here, 30 is absent). Are there more losing games at higher N? Is there a proof there are none?
In this study, in addition to the
normal starting positions, e.g: 111, or 1111, or 11111, etc, I looked at
all possible arrangement of objects where there are N total present - the partitions of N objects into groups. The number of partitions for each N are listed
here and a table of the partitions is
here. As and example, with zeros used for padding, one position (or partition) for six objects remaining is: 11101101 or 111 11 1, with a group structure [1:1][2:1][3:1] (1 group of one, 1 of two and 1 of three)
A table of all
normal starting positions (all objects adjacent) showing the winning moves is given
here. A large, 3 MB, Table with _all_ possible partitions (positions) of N objects and _all_ winning moves is
here.
The relevant programs to generate the arithmetic partitions is
here, and the program that works to find winning and losing positions and moves is
here. It generates all its results starting simply from the N=1 losing position.
One final note: according to wikipedia, the Nim name was coined by Charles L. Bouton of Harvard University, who developed the complete theory of the game in 1901. (The game is old, and existed in many cultures for centuries under different names, e.g., "picking stones" in China. But the motivation for Bouton's name is unknown. My thought: the word "nim" is archaic (ME) for steal or filch - so its adoption for this reason seems natural.
Maybe Bouton's work contains the answer to what happens for this variant when N>30?
Edited on December 24, 2021, 11:38 am