Is \(\text{Nim}(1,2,4,5,5)\) 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:
| XOR | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
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.
| 1 | 0 | 1 | 1 | 0 | |
| XOR | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
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\).
Show that \(\text{Nim}(x,y,z)\) is a losing position if and only if \(x \oplus y \oplus z = 0\). Remember that \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).
Is \(\text{Nim}(7,11,15)\) a winning position or a losing position? If it is a winning position, what is the optimal move?
Show that \(\text{Nim}(x_1,\dots,x_k)\) is an losing position if and only if \(x_1 \oplus \dots \oplus x_k = 0\). \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).
Karl and Louie are playing the following game. There is a round table that has \(24\) seats around it. Karl and Louie place action figures around the table. However, no two figures are allowed to sit next to each other, regardless if they belong to Karl or Louie. The player, who cannot place their figure loses the game, Karl goes first - show that Louie will always win.
Katie and Andy play the following game: There are \(18\) chocolate bites on a plate. Each player is allowed to take \(1,2\) or \(3\) bites at once. The person who cannot take any more bites loses. Katie starts. Who has the winning strategy?
Arthur and Dan play the following game. There are \(26\) beads on the necklace. Each boy is allowed to take \(1,2,3\) or \(4\) beads at once. The boy who cannot take any more beads loses. Arthur starts - who will win?
Two goblins, Krok and Grok, are playing a game with a pile of gold. Each goblin can take any positive number of coins no larger than \(9\) from the pile. They take moves one after another. There are \(3333\) coins in total, the goblin who takes the last coin wins. Who will win, if Krok goes first?