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 \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\).

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\).

I have three positive integers. When you add them together, you get \(15\). When you multiply the three numbers together, you get \(120\).

What are the three numbers?

If a magician puts \(1\) dove into his hat, he pulls out \(2\) rabbits and \(2\) flowers from it. If the magician puts \(1\) rabbit in, he pulls out \(2\) flowers and \(2\) doves. If he puts \(1\) flower in, he pulls out \(1\) rabbit and \(3\) doves. The magician starts with \(1\) rabbit. Could he end up with the same number of rabbits, doves, and flowers after performing his hat trick several times?

In the other room there are two doors. The statements on them say:

1. There is treasure behind at least one of the doors.

2. There is treasure behind the first door.

Your guide says: The first sign is true if there is treasure behind the first door, otherwise it is false. The second sign is false if there is treasure behind the second door, otherwise it is true. What would you do?