Image: Ivelin Radkov/Shutterstock

Exercise: From the above sums NIM or otherwise, find how much xÅx, where x is any natural number.

If 38Åx = 25, what is the x;

Solution
38Åx = (100110) 2Åx = (11001) 2, hence x = (111111) 2 = 63.

In games 2-3-6-7 Nimes, Nimes 09/03/10, 08/04/12 Nimes, Nimes 09/05/12 and 11/05/14 NIM which player wins the first or the second and why?
Solution: The second because each such NIM sum is 0.

Find the best moves (if any) in the NIM 5-3-7-3-1.
Solution: Because 5Å3Å7Å3Å1 = (011) 2 = 3 we victorious position. Writing numbers in the binary numeral system we have:

Looking at 3 digital columns from left to right we find the first for which the NIM sum is 1. In our case is the second from the left. We choose one of the three aces in this column (ie. There are three victorious movements corresponding to lines 3, 7 and 3. Let us choose the one line 7 (red). Then changing line 7 of 111 is 100, e.g. To 4 decimal places. This means that we will delete 7-4 = 3 items from line 7. (… otherwise, ignore the 3s and box 1-5-7 find the NIM sum of small stacks (4 + 1) Å1 = 4 means that 3 minutes remove objects from line 7 in order to balance again).

Exercise: What are the other two winning moves? (remove any of the piles with 3 items).

• In NIM 19-20-21 what the winning moves, if any?

Solution: There are 3 overall winning moves, as we see from the following binary representations:

These lead the lost to rival positions (1, 20, 21), (19, 6, 21) and (19, 20, 7).  Check. The last triad occurs practically as follows: find the NIM sum of two smaller carcasses: (16 + 2 + 1) Å (16 + 4) = 7 and reduces the large pile in 7 objects.

• In NIM 21-25-4-6 what the winning moves, if any?

Solution: The binary representations are:

• Find the best moves (if any) in the NIM 13-17-26.

Solution: 13Å17Å26 = (8 + 4 + 1) Å (16 + 1) Å (16 + 8 + 2) = 4 + 2 = 6 we victorious position. The only winning move is to delete two items from the line 13 leaving 11 because then 11Å17Å26 = 0. Here the quick way unfortunately does not work because the NIM sum of two smaller stacks is (8 + 4 + 1) Å (16 + 1) = 28> 26.

In this work the optimal strategy ie. NIM may find the sum of the sum and the NIM NIM stack: (4 + 2) Å (8 + 4 + 1) = 11, hence reduces the NIM pile, i.e.. The stack 13 items 11 items.

• Find the best moves (if any) in the NIM 13-17-19-23.

Solution: 3Å4Å9Å110 = (01101) 2Å (10001) 2Å (10011) 2Å (10111) 2 = (11000) 2 and the first three lines are 1 in fourth bin, there are three winning moves. Turns (10001) 2 = 17 in (01001) 2 = 9 or (10011) 2 = 19 in (01011) 2 = 11 or (10111) 2 = 23 in (01111) 2 = 15. The latter, for example means that we delete 8 items from the line 23 and can be justified by the fast way: I find the NIM sum of all stacks except the largest: 13Å17Å19 = (8 + 4 + 1) Å (16 + 1) Å (16 + 2 + 1) = 15 <23 thus reduces the biggest pile (23 items) in 15 items.

• Find the best moves (if any) in the NIM 3-4-9-11.

Solution :3Å4Å9Å11 = (2 + 1) Å4Å (8 + 1) Å (8 + 2 + 1) = 4 + 1 = 5 we winning position. The only winning move is to delete 3 items from line 4. And here it does not work the fastest way because 3Å4Å9 = (2 + 1) Å4Å (8 + 1) = 12> 11, so I find NIM sum of NIM sum and NIM heap: (4 + 1) Å4 = 1, which means that we reduce the NIM pile (of 4 items) in one object.

How quickly exploited the optimal strategy in practice? E.g. We can play correctly and quickly a game NIM without converting numbers to binary and then apply the procedure described in detail in the foregoing?

Fortunately, the answer is yes!

Under the optimal strategy in any variant of NIM defeats one who locks his opponent.
With these simple words reminiscent of Greek-Turkish dogfights in the Aegean, we mean the following:To beat a player must always playing to reset the NIM sum. The NIM sum (as described at the beginning of this article) is a binary number and as such will consist of a sum of powers of two.

1 = 2⁰

3 = 2 + 1 = 2¹ + 2⁰

5 = 4 + 1 = 2² + 2⁰

7 = 4 + 2 + 1 = 2² + 2¹ + 2⁰

We observe that the sum 1 + 3 + 5 + 7 have 4 zero power of two, two raw power of two and two second power of two. In other words, there is an uneven number of powers of 2. This applies generally to every NIM zero sum. This follows from the definition of the NIM sum and the most important: it gives us an alternative optimal play!

The following examples will enlighten us more:

4Å7 = (22) Å (22 + 21 + 20) = 20 + 21 = 3 so the first player wins.

Now we observe that an alternative definition for the NIM sum is as follows: For any positive integers x and y the NIM sum xÅy is the number we receive by writing addend sum power of 2, deleting the powers of 2 that appear even numbers times and summing everything stayed normal.

We play NIM and we are faced with the following position:

|| |

|

| | | |

| | | | |

How to play?
First, we distinguish two quartets, one doubles and three aces. The quartets are good (is 2, ie. Even number power of 2) contrary to the dyad and the ace. So let tetrads and we break the dyad to get another ace. This way we only have robust powers of 2, so a zero sum NIM. In practice, delete an item from the second row, as shown in the figure below:

|

|

|

| | | |

| | | | |

We count anymore two fours, zero twos (and zero is an even number) and four aces. All well and our opponent is heading for defeat!

• In NIM 12-19-27 what the winning moves, if any?

a) (with binary conversions) If 12Å19Å27 = (01100) 2Å (10011) 2Å (11011) 2 = (0100) 2 and only the line 19 is 1 in third bin, there is only winning Reduces (01100) 2 = 12 in (1000) 2 = 8 means that we delete four items from the line 12.

b) (with powers of 2) 12 = 8 + 4

19 = 16 + 2 + 1

27 = 16 + 8 + 2 + 1

The method of forces is equivalent to the method of conversion, but as seen in the last example, clearly more simple and fast in operation. But is all finished here? Or is there more simple way for excellent play?

First, let’s agree on the heap, which contains the largest power of 2 in Nimes sum, to call the NIM pile. As you will find in practice, the NIM heap is not necessarily the biggest pile of play. Now we formulate the concept of optimal strategy

Balance forces to 2

In practice, this can be done in many ways, for example in the following four:

– I spread the powers of 2 in each pile (mentally or on paper) and delete pairs of identical forces from different piles balancing the rest (the only way it can be done schematically)

– Convert numbers of stacks in two-own system and equilibrated columns

– Find the sum of NIM sum and NIM heap so it’ll be the objects that will be left from the NIM pile

– I find the NIM sum of all stacks apart from the longer and if it is less than larger heap reduces the latest in NIM sum found

Comments:
1) The first way is by far the best because it can be done mentally, while the latter does not always work, as we saw in the examples. Since the NIM sum never exceeds the normal sum, the possibility to work is great!

2) If we play NIM random number remains and objects then better to play first because we have a greater chance to win. Indeed in a random NIM sum of the probability of this is non-zero is greater than the probability is zero.

3) is obvious that the NIM with two piles, always taking care to balance the piles, that the opponent is facing a symmetrical situation. So the NIM with two piles a trivial case.

————————————————————————————————————————————————-

References – Bibliography

• Bouton, C.L. (1902), Nim, a game with a complete mathematical theory. Annals of Mathematics. Princeton, 2nd Series, 3(1/4), 35–39.
• In Woo, J. H., Lew, H. C., Park, K. S. & Seo, D. Y. (Eds.) (2007),  Proceedings of the 31st Conference of the International Group for the Psychology of Mathematics Education, Vol. 4, pp. 193-200. Seoul: PME. SangHun S., JaeHoon Y., EunJu S.and HyangHoo L. Posing Problems with use ‘What if not? Strategy in Nim game’
• Lujan, H. L. & DiCarlo, S. E. (2006). Too much teaching, not enough learning: What is the solution? The American Physiological Society, 30, 17‐22.
• National Council of Teachers of Mathematics. (2000). Principles and Standards for
• School Mathematics. Reston, VA: NCTM. Pfeiffer, S. (1998). Creating nim games: Math projects series. United States: Dale Seymour.
• Ralston, A. & Willoughby, S. (1997). Realistic problem formation and problem solving. The Mathematics Teacher, 90, 430‐435. Retrieved October 19, 2003, from Pro Quest Education Journals.
• Whitin, D., Whitin, P. (2002). Promoting communication in the mathematics classroom. Teaching Children Mathematics, 9, 205‐210. Retrieved October 18, 2003, from ProQuest Education Complete.
• Hostos Community College, New York, USA International Journal of Mathematical Education in Science and Technology, Vol. 38, No. 1, 15 January 2007, 43–54 Activity-based introduction to the binary system: Nim game winning strategy

I do not know if there are Greek references to the NIM, but the internet can offer us a lot, as well as the opportunity to play on line game. You can also download the game on our computer to play it whenever you want. Examples include the following websites:

• http://www.delphiforfun.org

Interesting site where you can download the game NIM, with several variants and many other math programs in small files directly executable (.exe) or another format if you prefer.

• http://www.cut-the-knot.org/nim_st.shtml

You can play on line the NIM with three random piles at a time and verify the minutes in the best way.

• http://www.pims.math.ca/pi/issue2/

where you among other things to discover and download  mathematical journal  ‘pi in the Sky’.

Article written by: Argyri Panagiota, Scientix Deputy Ambassador

Tags: game, lesson plan, math, Students