The general solution of a Nim-heap game

The general solution of a Nim-heap game

[Abstract] As a combinatorial one, the game Nim turns out to be extremely useful in certain types of combinatorial game analysis. It has given the general solution of the game a Nim-heap game and the result has proved true.

[Keywords] Combinatorial game Nim game

1. Introduction

Nim is a simple combinatory game with finite possibilities. But unlike tic-tac-toe, that other game of limited possibilities, there is tremendous variety in both Nim’s conception and implementation. The theory of the Nim game was discovered by mathematics professor Charles Bouton at Harvard University in 1901. In fact, Bouton, who wanted to use the game to demonstrate the advantage of the binary number system, found a simple formula, with which, from the state of play, players can determine correct moves immediately.

An example of a combinatorial game is the game of Nim: given several heaps of tokens, on her turn, a player picks a heap and removes some tokens from that heap. Play continues until no heaps remain. Under the normal convention, the player who takes the last token is the winner.

2.The result

2.1 A Nim-heap game G(n,2)

Definition: A combinational game G is impartial if from any position for all of its followers, the options of the players are equal.

Note: Nim game is impartial by the definition.

Theorem 1:Given an impartial game G played under the normal play convention, then G is equivalent to the Nim heap which correspond to the least possible number that is not the size of any of the heaps which correspond to the options of G.

The valid option of G(n,2) is that:

n→n-1

→n-2

So, by Theorem 2, we conclude that the game is equivalent to