Problems

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\times {10}^2+3\times 10+7\times 1$. If we write it instead using powers of $2$, we have $137=1\times 2^7+0\times 2^6+0\times 2^5+0\times 2^4+1\times 2^3+0\times 2^2+0\times 2^1+1\times 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$.

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 \cdots \oplus x_k=0$. $x\oplus y$ denotes the nim-sum of $x$ and $y$.

Suppose you have a coffee mug made of stretchy and expandable material. How do you mold it into a donut that has a hole inside?