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?

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?

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.

Take a straight string of finite length. Wrap the right half over and then under the left half so that it is pointing to the right again and there is a hoop. Pass the right pointing piece through the hoop from above. Glue the two ends together to form the figure-8 knot.

Draw a sequence of pictures to illustrate the formation of the figure-8 knot, seen below.