All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
A nim variation (Posted on 2021-12-09) Difficulty: 3 of 5
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?

No Solution Yet Submitted by Jer    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
more solns (up to N=30) | Comment 4 of 5 |
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
  Posted by Steven Lord on 2021-12-23 22:32:39

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (13)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information