Nim

related topics
{math, number, function}
{game, team, player}
{@card@, make, design}
{language, word, form}

Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.

Variants of Nim have been played since ancient times. The game is said to have originated in China (it closely resembles the Chinese game of "Jianshizi", or "picking stones"), but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century. Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German nimm meaning "take", or the obsolete English verb nim of the same meaning. It should also be noted that rotating the word NIM by 180 degrees results in WIN (see Ambigram).

Nim is usually played as a misère game,[citation needed] in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.

Normal play Nim (or more precisely the system of nimbers) is fundamental to the Sprague-Grundy theorem, which essentially says that in normal play every impartial game is equivalent to a Nim heap that yields the same outcome when played in parallel with other normal play impartial games (see disjunctive sum).

While all normal play impartial games can be assigned a nim value, that is not the case under the misère convention. Only tame games can be played using the same strategy as misère nim.

A version of Nim is played —and has symbolic importance— in the French New Wave film Last Year at Marienbad (1961).

Contents

Full article ▸

related documents
Zero-sum
Minimax
Shuffling
Knight's tour
Borel algebra
Special linear group
Automata theory
Quasigroup
Operator overloading
Golden ratio base
Graftal
Column space
Monotone convergence theorem
Theory of computation
Product topology
Spectrum of a ring
Generating trigonometric tables
De Morgan's laws
1 (number)
Discriminant
Stirling's approximation
Sylow theorems
Jacobi symbol
NaN
Isomorphism theorem
Tree (data structure)
Free variables and bound variables
Algebraic topology
Monotonic function
Generalized Riemann hypothesis