Problems

Let’s play some games today! We will play a classic game known as nim, which is thought to be one of the oldest games.

Typically people play nim using matchsticks, though stones and coins are popular too. There are a few heaps of matchsticks in nim. Players take turns to remove matchsticks from a heap of their choosing. The player can remove any number of matchsticks they wish from that heap. Whoever has no matchsticks left to take loses.

This following position will be written as \(\text{Nim}(3,3,3)\):

As another example, this is \(\text{Nim}(1,2,3,4)\):

We will omit heaps of size zero, so \(\text{Nim}(3,0,3,0,3)\) is the same as \(\text{Nim}(3,3,3)\).

Nim is important because a large class of games are equivalent to it despite its simple appearance. The interested reader should look up “Sprague-Grundy Theorem".

Let us introduce a few terms that will be helpful for analyzing games. A game \(G\) consists of some positions and a set of rules. A position \(g\) in the game \(G\) is called a winning position if the player starting this turn has a winning strategy. This means as long as the player starting this turn continues to play optimally, the second player has to lose. Conversely, a position \(g\) is a losing position if the player starting this turn has no winning strategy.

Explain why a position \(g\) is a winning position if there is a move that turns \(g\) into a losing position. On the other hand, explain why a position is a losing position if all moves turns it into a winning position.

A technique that can be used to completely solve certain games is drawing game graphs. Given a game \(G\), we draw an arrow pointing from a position \(g\) to a position \(h\) if there is a move from \(g\) to \(h\).

As a simple example, the game graph of \(\text{Nim}(2)\) is shown below.

Draw the game graph of \(\text{Nim}(2,2)\). Is \(\text{Nim}(2,2)\) a winning position or losing position?

Is \(\text{Nim}(2,5)\) a winning position or a losing position?

Let \(x,y\) be nonnegative integers. Determine when \(\text{Nim}(x,y)\) is a losing position and when it is a winning position.

Is \(\text{Nim}(1,2,3)\) a winning position or a losing position?

Is \(\text{Nim}(1,2,4,5,5)\) a winning position or a losing position?

When we write 137 in decimal, we mean \(1 \cdot 10^2 + 3 \cdot 10 + 7 \cdot 1\). If we write it instead using powers of 2, we have \(137 = 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\). To tell apart binary representation from decimals, we can use the following notation: \(137 = (10001001)_2\).

What is the number 273 in binary? Note that using binary is useful for finding whether a particular Nim game is a winning position or a losing position.

Let us define XOR (or addition mod 2). XOR is defined for 0 and 1 only. Here is a table recording the values of XOR:

Now we define the important concept of nim-sum. Given two natural numbers \(x\) and \(y\), we first convert them into binary representations and then compute XOR on individual digits. The resulting number, denoted \(x \oplus y\), is the nim-sum of \(x\) and \(y\). Here is an example.

This is simply saying \(22 \oplus 5 = 19\). Note that \(22=(10110)_2\) and \(5=(00101)_2\).

Verify \((x \oplus y) \oplus z = x \oplus (y \oplus z)\), so we can speak of \(x \oplus y \oplus z\) with no ambiguity.

Show that \(x \oplus y = 0\) if and only if \(x = y\). Remember that \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).