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?
Two fractions sum up to \(1\), but their difference is \(\frac1{10}\). What are they?
On her birthday, my grandma was asked how old she was. She said: "Start with the year I was born. Add the current year to it. Then, from the sum subtract the year I celebrated by \(20\)th birthday. From that, take away the year I was \(30\). The result will be \(16\)." How old is my grandma?
In the long addition above, each letter corresponds to a different digit. What is the sum \(D + O +G + C +A +T\)?
Let \(ABCDE\) be a regular pentagon. The point \(G\) is the midpoint of \(CD\), the point \(F\) is the midpoint of \(AE\). The lines \(EG\) and \(BF\) intersect at the point \(H\). Find the angle \(EHF\).
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\).