Problems

Elephants, rhinoceroses, giraffes. In all zoos where there are elephants and rhinoceroses, there are no giraffes. In all zoos where there are rhinoceroses and there are no giraffes, there are elephants. Finally, in all zoos where there are elephants and giraffes, there are also rhinoceroses. Could there be a zoo in which there are elephants, but there are no giraffes and no rhinoceroses?

Several natives of an island met up (each either a liar or a knight), and everyone said to everyone else: “You are all liars.” How many knights were there among them?

Explain why a position \(g\) is a winning position if there is a move that turns \(g\) into a losing position. On the other hand, explain why a position is a losing position if all moves turns it into a winning position.

A technique that can be used to completely solve certain games is drawing game graphs. Given a game \(G\), we draw an arrow pointing from a position \(g\) to a position \(h\) if there is a move from \(g\) to \(h\).

As a simple example, the game graph of \(\text{Nim}(2)\) is shown below.

Draw the game graph of \(\text{Nim}(2,2)\). Is \(\text{Nim}(2,2)\) a winning position or losing position?

Is \(\text{Nim}(2,5)\) a winning position or a losing position?

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?

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