Math and Game: Nim (Part 1)
Image: Ivelin Radkov/Shutterstock
Introduction
Nim [1] is the most famous mathematical game in which two players take alternately articles by distinguished stacks. Each player in turn gets what objects it wants, provided they are in the same stack. In the normal version of the game, the player will get last, wins (laughs best who laughs last!). The Nim solved mathematically for any number of initial heap and objects. The Charles Leonard Bouton, Professor of Mathematics at Harvard University, published in 1902, the best strategy game.
We will present a simple math optimal strategy of NIM. We call simply [2] because the only mathematics necessary for understanding of the optimal strategy, is the binary numbering system, and the following specific mathematical operation: call NIM sum of binary numbers x and y ,sum x+y(mod2). This is symbolized by xÅy and a way to be found is the following: Place the binary numbers with digits aligned and any digital column count the number of 1. If it is an even number, then the result is 0 otherwise 1 (symbols: 0Å0 = 0, 0Å1 = 1, 1Å0 = 1 and 1Å1 = 0).
The Nim sum is a fundamental concept in mathematics branch called Combinatorial Game Theory (Combinatorial Game Theory). With NIM sum one can find the strategy in any combination game (like tic tac toe or chess etc.) And to determine whether defeating or losing [3]! The concept of NIM sum is a very effective tool not only in game theory, but also in other areas of mathematics. Finally, for a more comfortable reading this article, we present a table of the top 64 nonnegative integers appear written in the binary numeral system with 6 bits of each.
Finally, for a more comfortable reading this article, we present a table of the top 64 nonnegative integers appear written in the binary numeral system with 6 bits of each.
General winning strategy in any version of the game NIM
Which player wins? The first or the second?
This depends from the original piles of each variant. Specifically: If the NIM sum is 0 then the second player wins, otherwise the first. In other words:If in any digital column in the base 2 is an even number of 1, then the second player wins, otherwise the first defeats.
Eg. the NIM version 1497 we have:
Line Binary writing

and there is an even number of aces in each column, the second player wins. In contrast, in the variant NIM 17147:
Line Binary writing

There is not an even number of aces in each column (eg. in the first or second column from the left) the player will play now, ie. the first player wins.
Note: When we say eg. Line 17 mean the stack that consists of 17 items.
1. How should play the player who wins?
Calculates the sum NIM and it chooses the first on the left column has an odd number 1. From this column selects a 1 (one who has this column so victorious movements exist) and the corresponding line changes only the digits in the same column with one in Nimes sum. Eg. the NIM version 17147 :
Line Binary writing
17  10001 
14  01110 
7  00111 
ΝΙΜ sum:  11000 
Select the first column from the left and from that required the first line (here there is only winning move). The first line of the conversion will be 01001, ie. 9 in decimal writing. So, the player plays must now get 179 = 8 items from line 17.
2. Winning strategy in NIM 1357 where each line is drawn any number of objects
Created symmetry or positions (1, 2, 3), (1, 4, 5), (2, 4, 6), (2, 5, 7), (3, 4, 7), (3, 5, 6).
2.1 Remarks:
2.1.1 This can be done when playing the second always in accordance with the optimal strategy
2.1.2 The second or occlusive, e.g. You can ‘Hayes symmetry and simultaneously one from the above six asymmetric positions
2.1.3 In the third example, the notation. (1, 2, 3) we mean the gap that arises when the game residual three piles 1, 2 and 3 items respectively. Essentially the game NIM 123 denote the position (1, 2, 3)
2.1.4 Overall, Trinity (1, even, even + 1) is always victorious one that treats or creates.
2.1.5 Understood that when create symmetry it is sufficient to copies the movements of your opponent. This technique was named by Professor Bouton Tweedledum and Tweedledee Principle.
2.1.6 The above winning strategy (ie. When you create symmetry eg. The positions (1, 1), (2, 2), (1, 1, 3, 3) etc. Or 6 asymmetrical positions) with any other game NIM because the practical this way we follow the optimal strategy. In other words, Reset your NIM sum or, as we say otherwise, we balance the game.
3. Winning strategy in NIM 1357 where each line is drawn any number of consecutive items
Because in this case created fractures lines, the lines can be increased, but the winning strategy remains the same as the general case. If eg. The first erase the center of 5, then the second must be deleted 5 than 7 or lose!
Proof: The second is now faced with the NIM version 13227 for which we have:
Line  Binary writting 
1  0001 
3  0011 
2  0010 
2  0010 
7  0111 
ΝΙΜ sum:  0101 
From the second column on the left select the required one line 7 and change the 2 aces of (red and green) to zero. Line 7 then becomes (0010) 2 = 2 and in practice this means that we remove 72 = 5 items from the line 7.
4. Examples in Nim game
Find the following NIM totals:
i) 54Å27
ii) 27Å17
iii) 7Å11
iv) 1Å2Å3
v) 3Å5Å6
vi) 3Å5Å8
vii) 19Å20Å21
viii) 4Å5Å6Å7
ix) 3Å5
5. Solution
i) To calculate the NIM sum 54Å27 first convert the numbers 54 and 27 in binary. Is 54 = (110110) 2 and 27 = (11011) 2
So 54 Å 27 = (101101) 2 = 45
ii) 27Å17 = (11011) 2 Å (10001) 2 = (1010) 2 = 10
iii) (1100) 2 = 12
iv) (00) 2 = 0
v) (000) 2 = 0
vi) (1110) 2 = 14
vii) (10010) 2 = 18
viii) (000) 2 = 0
ix)
—————————————————————————————————————————————–
[1] hence the name of the game which means take the German word nimm.
[2]called normal because most math games follow this convention.
[3]Ο S. Goldberg το 1987 στο Some very deep mathematical problems that anyone can understand, J. Recreational Math., 19:2, pp. 119125: “There is a way to play chess so that you never lose: the good news is that this has been proved. The bad news is that all the computers in the world will never be able to discover it”.
Article written by: Argyri Panagiota, Scientix Deputy Ambassador
Tags: game, lesson plan, math, Students