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 non-negative integers appear written in the binary numeral system with 6 bits of each.

Tags: mathematical game, binary writting, game theory

Finally, for a more comfortable reading this article, we present a table of the top 64 non-negative 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 14-9-7 we have:

and there is an even number of aces in each column, the second player wins. In contrast, in the variant NIM 17-14-7:

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 17-14-7 :

                    Line                 Binary writing

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 17-9 = 8 items from line 17.

2. Winning strategy in NIM 1-3-5-7 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 1-2-3 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 1-3-5-7 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 1-3-2-2-7 for which we have:

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 7-2 = 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. 119-125: “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