Nim and simple mathematical proofs 2/3

Nimble is a game where there is a row of squares numbered 0, 1, 2, 3, … Each square can contain a coin, and a square may contain multiple coins. The game is played by two players, taking turns in moving a single coin to a lower-numbered square. A player must move and exactly one coin during his turn. A coin may only be mover to a lower-numbered square. The game is won by the player who moves the last coin into square 0. At first this game might look like a distant cousin of Nim, but actually this game is exactly Nim, just in disguise. Let’s see the “proof” for that.

I will present below the rules of Nim and the rules of Nimble to show that the games are identical. Each rule contains the analogous version of the rule for both games.

Rule 1:
Nim: Two players take turns in removing sticks from piles. In the beginning, there are at least three piles.
Nimble: Two players take turns in moving one coin from a square to a lower-numbered square.

Rule 2:
Nim: During his turn a player must remove at least one stick from one pile.
Nimble: During his turn a player must move one coin to at least the next lower-numbered square.

Rule 3:
Nim: A player may remove sticks from one pile only during one turn.
Nimble: A player may move only one coing during one turn.

Rule 4:
Nim: A player to remove the last stick wins
Nimble: A player to move the last coin to square 0 wins.

Rule 5:
Nim: The piles do not interact with each other.
Nimble: The squares and coins do not interact with each other.

From rules 1–5 it is easy to see that Nim and Nimble are the same game with slightly different representations. Especially from rules 2 and 3 we can observe that removing of k sticks from exactly one pile of n sticks and moving exactly one coin from square n to square k are equivalent.

Although this “proof” is hardly very deep-going, or even a real proof for that matter, it shows well how one concept can be presented in different ways and how seemingly different situations can be just different representations of the same idea. This observation is a good reminder for everyday life. When facing novel problems (e.g. Nimble), we should ask ourselves if we could draw parallels to known and familiar problems (e.g. Nim). On the other hand, when looking at existing ideas and concepts (e.g. Nim) we might want to try formulating them a bit differently (e.g. Nimble) to see if we can gain more insight into them.

Nim and simple mathematical proofs 1/3

A few weeks ago I discussed a game called Nim. In studying Nim, with the help of Thomas S. Ferguson’s book Game Theory, I have again found great joy in mathematical thinking, proving theorems and using logical thinking to come to conclusions.

Many people, as far as I know, have some kind of fear of mathematics and mathematical notation. Some people are even proud of their mathematical illiteracy, which is odd, considering that nobody boasts how their Spanish or Chinese skills are non-existent. Working with games and proofs, like those required by Nim, might help people see the value and true beauty of mathematical thinking. People might understand that extensive mathematical notation is not always necessary to prove mathematical theorems, and that mathematical notation is actually just another language that helps us formulate and formalize logical thinking, removing all ambiguity. In this post and two additional ones I will present three proofs related to Nim to show you, how mathematical thinking can be used quite cleverly to show interesting facts.

Bouton’s theorem

In his 1902 article Nim, a game with a complete mathematical theory in Ann. Math. 3, 35-39

L. Bouton proves the following theorem (Theorem 1, Bouton’s theorem): “In a game of Nim a position is a P-position if and only if the Nim-sum of its components is zero.”

A Nim-sum is calculated as follows:

• The number of sticks in each pile is expressed in base two.
• These figures are added without carry, so that the sum of each column is 1, if the column contains an odd number of ones. Otherwise, the sum of that column is 0.
• The Nim-sum is zero when the sum of each individual column is 0.

As an example of calculating the Nim-sum we take three piles with 4, 5, and 8 sticks respectively. The Nim-sum of these piles in base two is:

1000
1010
1000
1001

The result, in base 10, is 9. Since this Nim-sum is non-zero, according to Bouton’s theorem this would be an N-position. It is worth noting that a Nim-sum of two identical positive integers is also zero due to the definition of Nim-sum. Nim-sum is also associative and commutative and 0 is an identity for addition. (see Ferguson’s Game Theory, Part 1, Chapter 1, page 10)

Proving Theorem 1

Proving Bouton’s theorem is partially a constructive proof, relying on the definitions of P- and N-positions. The claim of the theorem is compared against these definitions to show that they are equal. We recall that P- and N-positions are defined as follows:

• The terminal position is a P-position.
• An N-position is such that there is at least one possible move into a P-position.
• A P-position is such that from it is possible to move only into an N-position.

Now we just have to show that the terminal position has a Nim-sum of zero, a P-position always has a Nim-sum of zero and that a Nim-sum of zero is never an N-position. If we can prove this, we will have proven Bouton’s theorem.

Let’s start by observing that the terminal position has a Nim-sum of zero, so condition 1 is fulfilled.

For condition number 2 we can construct such a move, where we can move from a position with a non-zero Nim-sum (a purported N-position) into a position with a Nim-sum of zero (a purported P-position). In our example we do this by reducing the number of ones in the leftmost column with an odd number of ones (the 4th column) so that each column will eventually contain an even number of ones. In our case, there is only one potential move, since there is only one number one in the leftmost column. Thus, the only move into a P-position is to remove 7 sticks from the pile of 8. By this example we see, that we can move from an N-position into a P-position, so condition 2 is also fulfilled. For a more formal and generalized proof for this part, see Bouton’s original article.

The third condition can be shown to be true by the following reasoning. If we are in a position with a Nim-sum of zero, removing any number of sticks from any pile will leave us witha non-zero Nim-sum (a purported N-position). This is because if we remove any number of sticks from a pile, the number of sticks in all the other piles remains the same. If the Nim-sum of the new position were zero, it would imply that the number of sticks remaining in the pile, from which sticks were removed, has stayed the same, but this is a contradiction. Thus, condition 3 also holds.

Collecting together the proofs for conditions 1, 2 and 3 we have shown the following:

• The terminal position has a Nim-sum of zero.
• From a position with a non-zero Nim-sum we can move into a position with a Nim-sum of zero.
• From a position with a Nim-sum of zero it is possible to move only into a potision with a non-zero Nim-sum.

We see that these statements are analogical to conditions 1, 2 and 3 and that a position is a P-position if and only if the Nim-sum of that position is zero.

I hope this post gave you an idea of how simple logical thinking with quite elementary mathematical notation can provide a powerful tool for analyzing problems. In my next post I will discuss a Nim variant called Nimble and show how Nim can come in disguise.

Up high – Mountaineering on Piz Buin

I spent the last weekend with a few colleagues from work climbing to Piz Buin, the highest peak in the Austrian state of Vorarlberg. For some people Piz Buin might be more familiar as a sun block brand, and sun block was much needed during the days as the snow reflected the still strong late summer sun shine.We were very lucky to have a clear blue sky with the sun shining on both days. Our group was lead by a professional guide who taught us some basics of  mountaineering, e.g. how to advance as a group when attached to a rope, how to act when someone falls into a crevasse (a chasm in the ice) and how to walk with crampons attached to your shoes.

We started our trip on Saturday morning by driving to Austria and climbing about 400 meters up to the cabin “Wiesbadener Hütte” on Saturday morning. The following afternoon we spent training with our guide on the glacier.

After the first training and introduction to hiking on glacier and a very brief peek into hiking on mountainous routes from our guide Moses , we were well equipped to climb to Piz Buin, with Moses’ help and guidance of course.

The Climb to Piz Buin

On Sunday morning, we started our climb at around 6.30 am from a height of 2443 meters above sea level (ASL). The first part of our trip took us through some stony landscape, broken by small streams flowing down from the melting glacier. As we climbed higher, we arrived at the edge of the glacier where we put on our crampons. Slowly and steadily making our way even higher, attached to the rope, we enjoyed the silence and whiteness of the surrounding landscape. After a while, the glacier became flatter, and eventually we reached the saddle (“Buinlücke”) between the Grand and Little Piz Buin, some 3000 meters ASL.

Our final leg was climbing the remaining 300 meters to the top the Grand Piz Buin. The leg consists of a hiking path and some simple rock climbing with a rope.

Finally, at the top, 3312 meters ASL, the view in all directions was simply beautiful. We were looking down at the surrounding peaks and could see far into the Swiss side. There was no wind and we were the only people there. Amusingly, we also saw a small single-engine airplane circling around the Grand Piz Buin. It passed us at nearly eye level, not 100 meters away from the peak and with its three passengers waving at us.

The trip back.

After a break of good 20 minutes at the top we started our way back from the summit, again rock climbing and after that hiking a steep path to the saddle point between the two peaks.

From there on we crossed again the glacier, feeling how the snow was already getting softer and softer as the afternoon sun was throwing its warm beams at it. Multiple groups passed us on the glacier on their way to Piz Buin, which was somewhat surprising, since the melting snow makes the trip a lot harder in the afternoon.

Arriving at the lower end of the glacier, we trotted down the stony path back and visited a glacier cave at the foot of the glacier. According to our guide Moses, the ice layers in the cave, reachable by bare hand, were a few hundred years old. The contrast between the glacier cave and the surrounding desert-like landscape just outside of the cave reminded me of a sci-fi film.

One experience richer

At about 2 pm, back at the cabin, we were admittedly tired but also full of joy after the experience and proud of having done the trip. A good part of the experience and our success are attributable to Moses and the excellent weather conditions. With his experience, calm and trust inducing manner Moses helped us through even the more difficult parts on the trip.

Our trip from the cabin to the Grand Piz Buin took us 3 hours and 45 minutes, while the whole round-trip, including a 20-25 minute lunch break and a visit to the glacier cave took us 7 hours and 30 minutes, so it was full day’s trip. I will add photos later on, since my writing doesn’t do justice to what we experienced.

I think I was bit by a mountaineering mosquito and might find myself next summer on a couple of such tours. But before that my colleagues and I are planning to take a rock climbing course to be better able to clear legs requiring rock climbing and gaining the confidence and skills to do it right and safely.

Edit from 4.9.2016: Photos added. Many thanks to Moses for the pictures. Also fixed some typos.

Recently I read Ivan Turgenev’s short story The Diary of a Superfluous Man. It is a story about a man on his deathbed writing his diary and thinking back how he and his whole life were superfluous.

On the surface, being a superfluous person is a contradiction, since a person’s very existence is a measurable difference when compared to an alternative world where he wouldn’t have existed.

Turgenev gives the expression superfluous man a somewhat different meaning. He does not say that a superfluous person’s existence is completely irrelevant; rather that such a person is unable or incapable of pursuing and realizing his dreams and passions. This inability is not due to lack of talent or intellect, rather a consequence of inability to act according to the prevailing social norms and thus ending up as a pariah outside of society. The superfluous man is also often plagued by cynicism due to his misfortune of not being able to live to his full potential. In Turgenev’s story the superfluous man tells how he was unable to win the love of a girl she fell in love with. Furthermore, he tells the reader how the girl fell in love with another man whom she also married, after being rejected by a nobleman. Our superfluous man ponders, how his whole role in these events was complete redundant, since the girl was rejected by the nobleman and she married another man, which would have happened even if our superfluous man had not played any part in the events, since, due to his own deeds, he was ignored by the girl he wanted to marry.

Be non-superfluous

When pursuing our dreams and passion, in the face of hardship we should always remember that we are not superfluous, and we do not have to be. Not all dreams may come true, but we can work towards them to make some come closer to reality.

Even when pursuing our dreams, we might want to adhere to some social norms. At least in the beginning, when creating something new, it might be essential to get the critical mass of people behind your cause and this might require an approach that reconciles the differences between your revolutionary thoughts and the prevailing norms. On the other hand, we have to be aware that breaking boundaries is often received with resistance and we should not give up and fall to cynicism just because we cannot please everyone. In the end, sticking to the existing paradigms is also a hindrance to progress, so reconciling all differences to cater for the existing norms and truths is unlikely to bring about and promote the most revolutionary ideas and movements.

For example, Einstein’s theory of relativity was a completely new paradigm in physics, and while the Newtonian mechanics can be brought together with Einstein’s ideas as approximations to the latter ones, explaining away the crucial differences, e.g. the constant speed of light in all coordinate systems, would have precluded the following progress in physics.

When building something new, we should still respect the old and understand why it was built the way it was. We should not dismiss history and the past, but rather improve on it. We should not dismiss the outdated ideas and opinions of others as simply wrong, but take them as milestones that were reached and continue the journey forward. We should step forward boldly, even when others are reluctant to take that step. We should take action and live our legend.

Berries, mushrooms and thorns

I just spent the last two weeks back at my home region. In addition to seeing my friends and relatives I spent some time in the forest, gathering berries and mushrooms. This year the harvest for blueberries was good and they were already ripening in mid-July, two weeks earlier than regular. The harvest for chanterelles on the other hand was just astonishing, even better than last year.

I did two trips to find chanterelles, and both times I looked for new areas where to find them, somewhere where other people would not have already been. It turned out to be quite easy. As a rule, when you find a chanterelle, you have found many, since they grow in groups. This year, when you had collected those in your immediate vicinity, walking ten or twenty meters further, or just taking a few steps, already revealed you the next ones. And they were big and many. I spent in total maybe four hours in the woods and ended up gathering some four to five liters. Later on I also spent an hour and a half with my mother gathering blueberries. Although this year’s early season for blueberries was already waning by the beginning of August, we managed to get some eight liters in total.

After returning home from my vacation I remembered that just before my vacation, in mid-July, I had spotted some blackberries quite near to my home. Today I went over to see, if they were not already taken by others. Arriving at the spot, I was happy to see that there were still plenty left. Most of them were even raw and I had to select quite carefully to pick out the truly ripe ones. Blackberries seem to be a bit tricky in that way, that for the untrained eye a still raw but a already dark-colored berry might look like a ripe one. I quickly learned that the ripe ones are not just nearly black but also have a more uneven shape than the raw ones, caused by the single “buds” of the berry getting larger and thus protruding further away from each other.

I also learned that blackberry bushes have larger and sharper thorns than raspberries. I was wearing a t-shirt, sandals and had my trouser legs rolled up to my knees when I went into the bushes. I spent two hours there, coming out with four liters of berries and having my hands, forearms and feet full of scratches. Now I know to wear more protective clothing, especially long sleeves the next time I go looking for blackberries.

Combinatorial games and Nim

Based on the most recent posts it seems that my blog in transforming into a learning diary on game theory. Because I started this blog as a tool for self-reflection, this change is by no means bad. It might even prove that I have found an area I am passionate about and wish to pursue even further.

In the beginning of July I finished the Open Yale course on game theory and was looking for new material on game theory to study further. I considered buying the course book by Mr. Dutta, but found Mr. Thomas S. Ferguson’s book on game theory as a free Internet version and decided to continue from there.

Mr. Ferguson’s books starts with an introduction on combinatorial games , and on impartial games in specific, something that was not included in deep detail in the Yale Course, so this book seems to have a different approach to the subject. I have started studying combinatorial games in the book and the first exercises have been quite nice, requiring some elementary skills in proving mathematical formulae. Below I introduce one example from the exercises and my work on it, a couple of weeks old now. But first I give a brief introduction on Nim

Nim

Nim is a combinatorial game where two players take turns in removing objects from a given set. In the easiest variation of the game, there is one pile of sticks and each player must remove at least one stick, while the amount of removed sticks may not exceed a predefined maximum. The possible amounts that may be removed from the pile form the subtraction set S. E.g. if one, two or three sticks are permissible moves, then S = (1, 2, 3). Under the normal play rule, the person to remove the last stick wins.

In a game of Nim the winner is decided by the initial amount of sticks and the order, in which the players start the game, presuming that the players play optimally. In Nim there are so called P- and N-positions in the game. These correspond to the number of sticks remaining in the pile after the last move. A P-position is such, that the player who moved previous to the current position, is winning. An N-position is such that the player to move next is winning.

Before going into the general case, a brief example should illustrate the P- and N- positions. As shown in figure 1, we have a game of Nim starting from a pile with 9 sticks and S = (1, 2, 3). Since the player to take the last stick wins, the terminal position (zero sticks left in the pile) is a P-position, since the player who will have moved previously will win. Due to S = (1, 2, 3), positions where there are 1, 2 or 3 sticks left in the pile are N-positions, since the player to move from those positions, or the next player to move, can reach zero and win. Likewise, 4 is a P-position, since from this position a player can only move to positions 1, 2 or 3, thus not being able to win, but leaving the next player in a position to win, should he play optimally. Working backwards to the start position of this example, we see that who ever starts can always win by removing one stick and moving to 8, which is a P-position.

Formally, P- and N-positions are defined recursively as follows:

1. The terminal position is a P-position.
2. A N-position is such that there is at least one possible move into a P-position.
3. A P-position is such that from it is possible to move only into an N-position.

The definition of P- and N-positions contains a noteworthy subtlety. From an N-position a move into at least one P-position is guaranteed, but there are also potential moves into further N-positions. Thus being in an N-position does not guarantee winning the game with any play, but a win is guaranteed, if the player in the N-position plays optimally, that is, moves to the available P-position.

A slightly generalized version of Nim

I will prove the general formula for finding the P-positions in a simple one-pile Nim under the normal play rule.

Let the initial number of sticks in the pile be N and let S = (1, 2, …, n), where S has no gaps in it, i.e. for all members of S s(i) it is true that s(1) = 1 and s(i+1) = s(i) + 1 for i = 2, 3, …, n-1.

Since the terminal position is the final and winning position, it is a P-position. Into this position we can move from any position ≤ n. I claim that the P-positions in this variant of Nim are given by the formula p(k) = (max(S) + 1)*k, where k = 0, 1, 2, … The proof follows by induction.

For k = 0 we get p(0) = 0, which is the terminal position, so the formula holds for k = 0. Now I will show that if the formula holds for some k = m, then it also holds for k = (m + 1).

Let us assume that the formula holds for k=n. Then we have a P-position p(m) = (max(S) + 1)*m = (n + 1)*m.

For (m + 1) we get a potential P-position p(m + 1) = (max(S) + 1)*(m + 1) = (n + 1)*(m + 1) = (n + 1) + (n + 1)*m.

Position p(m) can only be reached by removal of sticks from positions that are below p(m + 1) since p(m) + max(S) = n + (n + 1)*m < p(m + 1) = (n + 1) + (n + 1)*m. On the other hand, the mentioned positions can all be reached by removal of sticks from position p(m + 1), since p(m + 1) – max(S) = 1 + (n + 1)*m, and this is the last position before p(m), which is a P-position. Thus by the definition of P- and N-positions, when p(m) is a P-position, so is also p(m + 1), and the positions between these two are N-positions.

Since the proposed formula holds for case k=0 and it also holds for p(m + 1) when it holds for p(m), the formula holds for the general case p(k) q.e.d.

In conclusion, for single-pile game of Nim under the normal play rule, starting with N sticks and with S = (1, 2, …, n), the P-positions are

p(k) = (max(S) + 1)*k, where k = 0, 1, 2, …

Obviously we also required that p(k) =< N for all k.

The first player to move will win the game with optimal play if and only if   N ≠ p(k) for all k. Otherwise the second player to move will win, if he plays optimally. This can be proven quite easily. First we define optimal play as such, that a player will move from an N-position into a P-position, whenever possible. By definition then, optimal play is such that the player will win, if he gets to move first in a game starting from an N-position. Thus, the first player will win with optimal play, if he gets to start from a N-position. Conversely, if the first player wins after starting from N-position he must have played optimally, presuming that player two also plays optimally. Otherwise, at some point in the game, player one would have moved from an N-position into another N-position, leaving player two the possibility to move into a P-position and consequently win the game. Therefore, as stated before, when both players play optimally, the player who starts will win if and only if N ≠ p(k) for all k.