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.)
proof that for N>20 player 1 wins Comment 5 of 5 |
"Proof" that N=20 is the last losing game for the player
who goes first in this revised Nim. 

First some axioms. 
Removing one from N leaves N-1 split in one or two groups 
Removing two from N leaves N-2 split in one or two groups
To win, you must move to give your opponent a loser (marked) 
with "x" below. If you do not hand your opponent a loser, they
have a winner and will win.


In the table, the rows are indexed N, number of objects. 
The columns (G) are indexed from 1 to the maximum number of groups we can break N into, which is N. E.g. 111 maximally breaks into 1 1 1, three groups of one.  An "x" has been placed in all (N,G) cells which contain at least one losing arrangement. e,g, grid(1,1)=g(1,1) has an x because the arrangement 1 is a loser. g(3,3) has 1 1 1 which is a loser, and g(6,2) contains 111 111 which is a loser. Note importantly, in the table, directly above grid(4,1) we see is block of winners looking like::
oo
oo

This is the condition for a start-of-game losing position. The pattern is there above g(4,1), g(9,1), g(12,1), and g(20,1). It is the necessary and sufficient condition for a loser. This is true because there are no N-1, or N-2 arrangements of one or two groups that are losers to hand to your opponent. Whatever you hand them will be a winner.

We see a pattern established after N=20 on the right side of the grid. The lone "x"s are at odd Ns at grid(N,N). These are losing patterns because the player drawing first will also draw last, and draw the last 1. These propagate downward and to the left to make g(N+1,G+1) a winner, We have N+1 even and a sequence ending in ... 1 1 1 11, making it a winner. Line g(N+2,G+1) is a winner with ... 1 1 1 111. (Take the last two and get g(N,N). In this way the right side of x's propagates downward and to the left and the 
oo
oo
pattern never reappears. [This proof still requires a bit of checking that _all_ the  x's propagating downward and to the left man be accounted for.] 
   

 N 123456...   (G)
--------------
 1|x                           
 2|oo                           
 3|oox                           
 4|xxo                           
 5|ooo x                         
 6|oxxx                          
 7|ooo   x                       
 8|oooxxx                        
 9|xxxx    x                     
10|oooxxxxx                      
11|ooxxxx    x                   
12|xxxxxxxxxx                    
13|ooxxxxxx    x                 
14|oxxxxxxxxxxx                  
15|oooxxxxxxx    x               
16|oxxxxxxxxxxxxx                
17|oxxxxxxxxxxx    x             
18|ooxxxxxxxxxxxxxx              
19|ooxxxxxxxxxxxx    x           
20|xxxxxxxxxxxxxxxxxx            
21|oxxxxxxxxxxxxxxx    x         
22|oxxxxxxxxxxxxxxxxxxx          
23|ooxxxxxxxxxxxxxxxx    x       
24|oxxxxxxxxxxxxxxxxxxxxx        
25|ooxxxxxxxxxxxxxxxxxx    x     
26|oxxxxxxxxxxxxxxxxxxxxxxx      
27|ooxxxxxxxxxxxxxxxxxxxx    x   
28|oxxxxxxxxxxxxxxxxxxxxxxxxx    
29|oxxxxxxxxxxxxxxxxxxxxxxx    x 
30|oxxxxxxxxxxxxxxxxxxxxxxxxxxx  

Edited on December 25, 2021, 6:58 am
  Posted by Steven Lord on 2021-12-24 15:24:33

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 (1)
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