Nim
Wikimedia disambiguation page
≈ 8 min read
Names in other languages
- DeutschNim
- EnglishNim
- FrançaisNim
- עבריתנים
- ItalianoNIM
- 日本語NIM
- NederlandsNim
- PortuguêsNim
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Nim is a mathematical two player game. Nim or NIM may also refer to: * Nim (programming language) * Nim Chimpsky, a signing chimpanzee * Nim (name), name list
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 (when regarded as a subgame of a larger impartial game) to a nim game with a single pile.
History
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 ( ), 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 , 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 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). 010 2 2 10 The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2 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: 3 = 0 + 2 + 1 = 2 1 Heap A 4 = 4 + 0 + 0 = 4 Heap B 5 = 4 + 0 + 1 = 4 1 Heap C -------------------------------------------------------------------- 2 = 2 What is left after canceling 1s and 4s In normal play, the winning strategy is to finish every move with a nim-sum of 0.
This is always possible if the nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the heap sizes.
Find a heap where the nim-sum of X and heap-size is less than the heap-size; the winning strategy is to play in such a heap, reducing that heap to the nim-sum of its original size with X. In the example above, taking the nim-sum of the sizes is . The nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are A ⊕ X = 3 ⊕ 2 = 1 [Since (011) ⊕ (010) = 001 ] B ⊕ X = 4 ⊕ 2 = 6 C ⊕ X = 5 ⊕ 2 = 7 The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).
As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal. After that, no matter what move the opponent makes, the player can make the same move on the other heap, guaranteeing that they take the last object.
When played as a misère game, nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps).
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. At that point, the next player removes either all objects (or all but one) from the heap that has two or more, so no heaps will have more than one object (in other words, so all remaining heaps have exactly one object each), so the players are forced to alternate removing exactly one object until the game ends.
In normal play, the player leaves an even number of non-zero heaps, so the same player takes last; in misère play, the player leaves an odd number of non-zero heaps, so the other player takes last. In a misère game with heaps of sizes three, four and five, the strategy would be applied like this: Proof: Notice that the nim-sum (⊕) obeys the usual associative and commutative laws of addition (+) and also satisfies an additional property, x ⊕ x = 0.
Let be the sizes of the heaps before a move, and y 1 , ..., y n the corresponding sizes after a move. Let s = x 1 ⊕ ... ⊕ x n and t = y 1 ⊕ ... ⊕ y n . If the move was in heap k, we have x i = y i for all , and x k > y k . By the properties of ⊕ mentioned above, we have \begin{align} t & = 0 \oplus t \\ & = s \oplus s \oplus t \\ & = s \oplus (x_1 \oplus \cdots \oplus x_n) \oplus (y_1 \oplus \cdots \oplus y_n) \\ & = s \oplus (x_1 \oplus y_1) \oplus \cdots \oplus (x_n \oplus y_n) \\ & = s \oplus 0 \oplus \cdots \oplus 0 \oplus (x_k \oplus y_k) \oplus 0 \oplus \cdots \oplus 0 \\ & = s \oplus x_k \oplus y_k \\[10pt] (*) \quad t & = s \oplus x_k \oplus y_k \end{align} That is, to update the total nim sum s after updating the x_k heap, we need to cancel it from s by nim summing with x_k , and then nim sum in y_k . The theorem follows by induction on the length of the game from these two lemmas.
Lemma 1. If s = 0, then t ≠ 0 no matter what move is made. Proof: If there is no possible move, then the lemma is vacuously true (and the first player loses the normal play game by definition).
Otherwise, any move in heap k will produce t = x k ⊕ y k from (*). This number is nonzero, since x k ≠ y k . Lemma 2. If s ≠ 0, it is possible to make a move so that t = 0.
Proof: Let d be the position of the leftmost (most significant) nonzero bit in the binary representation of s, and choose k such that the dth bit of x k is also nonzero. (Such a k must exist, since otherwise the dth bit of s would be 0.)
Then letting y k = s ⊕ x k , we claim that y k k : all bits to the left of d are the same in x k and y k , bit d decreases from 1 to 0 (decreasing the value by 2 d ), and any change in the remaining bits will amount to at most 2 d −1. The first player can thus make a move by taking x k − y k objects from heap k, then t = s ⊕ x k ⊕ y k (by (*)) 0 = n (mod k + 1) (in normal play), or 1 = n (mod k + 1) (in misère play).
This follows from calculating the nim-sequence of S(1, 2, ..., k), 0.123\ldots k0123\ldots k0123\ldots = \dot0.123\ldots\dot{k}, from which the strategy above follows by the Sprague–Grundy theorem. Let the largest number of stones in a pile be m and the second largest number of stones in a pile be n. Let p m be the number of piles having m stones and p n be the number of piles having n stones.
Then there is a theorem that game positions with p m even are P positions. This theorem can be shown by considering the positions where p m is odd. If p m is larger than 1, all stones may be removed from this pile to reduce p m by 1 and the new p m will be even.
If p m = 1 (i.e., the largest heap is unique), there are two cases: If p n is odd, the size of the largest heap is reduced to n (so now the new p m is even). If p n is even, the largest heap is removed entirely, leaving an even number of largest heaps. Thus, there exists a move to a state where p m is even.
Conversely, if p m is even, if any move is possible (p m ≠ 0), then it must take the game to a state where p m is odd. The final position of the game is even (p m = 0). Hence, each position of the game with p m even must be a P position.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378865753 under CC BY-SA 4.0; modifications have been made.