Nim
Nim
Main page
2320047

Nim

logo
Community Hub0 subscribers
What are your thoughts?
Be the first to start a discussion here.
Be the first to start a discussion here.
Nim

Nim is a mathematical combinatorial game in which two players take turns removing (or "nimming") objects from distinct heaps or piles. 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 or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

Nim is fundamental to the Sprague–Grundy theorem, which essentially says that every impartial game is equivalent to a nim game with a single pile.

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 jiǎn-shízǐ (捡石子), 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 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. 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". It was also one of the first-ever electronic computerized games. Ferranti built a nim-playing computer which was displayed at the Festival of Britain in 1951. In 1952, Herbert Koppel, Eugene Grant and Howard Baller, 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 nim playing machine has been described made from tinkertoys.

The game of nim was the subject of Martin Gardner's February 1958 Mathematical Games column in Scientific American. A version of nim is played—and has symbolic importance—in the French New Wave film Last Year at Marienbad (1961).

Nim is typically played as a misère game, in which the player to take the last object loses. Nim can also be played as a "normal play" game whereby the player taking the last object wins. 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. If this removes either all or all but one objects from the heap that has two or more, then no heaps will have more than one object, so the players are forced to alternate removing exactly one object until the game ends. If the player leaves an even number of non-zero heaps (as the player would do in normal play), the player takes last; if the player leaves an odd number of heaps (as the player would do in misère play), then the other player takes last.

The normal game is between two players and is played with three heaps of any number of objects. The two players alternate taking any number of objects from any one of the heaps. The goal is to be the last to take an object. 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.

See all
User Avatar
No comments yet.