Problems
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:
| 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\).
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?
Take a straight string of finite length. Put the right half on top of the left half to form a hoop, and then pass it (the piece now on top) through the hoop from underneath. Glue the two ends together to form the trefoil knot.
Draw a sequence of pictures to illustrate the formation of the trefoil knot.
In the picture below, each side is glued in the same direction as its opposite side. Draw a sequence of pictures to show the gluing process and the final shape.
