[1] The game is said to have originated in China—it closely resembles the Chinese game of jiǎn-shízi (捡石子), or "picking stones"[2]—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,[3] but the origins of the name were never fully explained.
The Oxford English Dictionary derives the name from the German verb nimm, meaning "take".
At the 1939 New York World's Fair Westinghouse displayed a machine, the Nimatron, that played nim.
[4] From May 11 to October 27, 1940, only a few people were able to beat the machine in that six-month period; if they did, they were presented with a coin that said "Nim Champ".
In 1952, Herbert Koppel, Eugene Grant and Howard Bailer, engineers from the W. L. Maxson Corporation, developed a machine weighing 23 kilograms (50 lb) which played nim against a human opponent and regularly won.
A version of nim is played—and has symbolic importance—in the French New Wave film Last Year at Marienbad (1961).
[8] Nim is typically played as a misère game, in which the player to take the last object loses.
In either normal play or a misère game, when there is exactly one heap with at least two objects, the player who takes next can easily win.
The normal game is between two players and is played with three heaps of any number of objects.
In misère play, the goal is instead to ensure that the opponent is forced to take the last remaining object.
The following example of a normal game is played between fictional players Bob and Alice, who start with heaps of three, four and five objects.
While all normal-play impartial games can be assigned a nim value, that is not the case under the misère convention.
An example of the calculation with heaps of size 3, 4, and 5 is as follows: An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct powers of 2, cancel pairs of equal powers, and then add what is left: In normal play, the winning strategy is to finish every move with a nim-sum of 0.
To find out which move to make, let X be the nim-sum of all the heap sizes.
These strategies for normal play and a misère game are the same until the number of heaps with at least two objects is exactly equal to one.
In a normal nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is not zero.
Proof: If there is no possible move, then the lemma is vacuously true (and the first player loses the normal play game by definition).
The first player can thus make a move by taking xk − yk objects from heap k, then The modification for misère play is demonstrated by noting that the modification first arises in a position that has only one heap of size 2 or more.
Notice that in such a position s ≠ 0, and therefore this situation has to arise when it is the turn of the player following the winning strategy.
Bouton's analysis carries over easily to the general multiple-heap version of this game.
The only difference is that as a first step, before computing the nim-sums we must reduce the sizes of the heaps modulo k + 1.
In particular, in ideal play from a single heap of n objects, the second player can win if and only if This follows from calculating the nim-sequence of S(1, 2, ..., k),
Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next answer can in any case be 100.
Greedy nim is a variation wherein the players are restricted to choosing stones from only the largest pile.
In the generalization to index-k nim, one forms the sum of each binary digit modulo k + 1.
Conversely, given a configuration with non-zero value, one can always take from at most k heaps, carefully chosen, so that the value will become zero.
[13] Once all the stones are placed, a game of Nim begins, starting with the next player that would move.
board, whereon any number of continuous pieces can be removed from any hyper-row.
[14] The starting board is a disconnected graph, and players take turns to remove adjacent vertices.