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|**oo**x

4|xxo

5|ooo x

6|oxxx

7|**oo**o x

8|**oo**oxxx

9|xxxx x

10|**oo**oxxxxx

11|**oo**xxxx x

12|xxxxxxxxxx

13|ooxxxxxx x

14|oxxxxxxxxxxx

15|oooxxxxxxx x

16|oxxxxxxxxxxxxx

17|oxxxxxxxxxxx x

18|**oo**xxxxxxxxxxxxxx

19|**oo**xxxxxxxxxxxx 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**