Problems

Red, blue and green chameleons live on an island. One day \(35\) chameleons stood in a circle. A minute later, they all changed colour at the same time, each changing into the colour of one of their neighbours. A minute later, everyone again changed their colours at the same time into the colour of one of their neighbours. Is it ever possible that each chameleon was each of the colours red, blue and green at some point? For example, it’s allowed for a chameleon to start off blue, turn green after one minute, then turn red after the second minute. It’s not allowed for a chameleon to start off blue, turn green after one minute, but then turn back to blue after the second minute.

Let \(p\) and \(q\) be two prime numbers such that \(q = p + 2\). Prove that \(p^q + q^p\) is divisible by \(p + q\).

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 taking the game from position \(g\) to position \(h\).

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?

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.