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?
"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
proof that for N>20 player 1 wins
