Problems

Remainder is the number that is “left over" from division. Even if a number is not divisible by another number fully, we can still divide, but leaving a remainder. The remainder is less than the number we’re dividing by. For example, a remainder of \(44\) in division by \(7\) is \(2\), because \(44 = 6 \times 7 + 2\). More generally, we can write \(n=qk+r\), where \(0\leq r<k\). We say that \(k\) goes into \(n\) \(q\) times, and a little bit (\(r\)) is left. If that little bit was larger than \(k\), it could “go into" \(n\) once more.

The general rule is that a remainder of a sum, difference or a product of two remainders is equal to the remainder of a sum, difference or a product of the original numbers. What that means is if we want to find a remainder of a product of two numbers, we need to look at the individual remainders, multiply them, and then take a remainder.

For example, \(10\) has remainder \(3\) when dividing by \(7\) and \(11\) has remainder \(4\) when dividing by \(7\). The product \(10\times11=110\) will have the same remainder as the product of the individual remainders. We first multiply \(3\times4=12\) and then take a remainder upon division by \(7\), which is \(5\) because \(12=7+5\). That means that \(110\) gives a remainder \(5\) in division by \(7\) - and it does, because \(110=15\times7+5\). If a number is divisible by a number we are dividing it, nothing remains and we say the remainder is \(0\).

Let’s have a look on some examples:

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 \dots \oplus x_k = 0\). \(x \oplus y\) denotes the nim-sum of \(x\) and \(y\).

Imagine the Earth is a perfectly round solid ball. Let us drill from the North Pole, London and Beijing simultaneously and meet at the centre of Earth. A ball with three openings is formed. The surface of this ball is shown on the left of the picture below. Describe how to stretch this surface so that it looks like the surface of a donut with two holes as shown on the right.

The pigeonhole principle is often called “Dirichlet’s box principle". Dirichlet made good use of this tool to show a fundamental result in Diophantine approximation, now commonly known as the Dirichlet Approximation Theorem. You will now prove it yourself!

Suppose \(\alpha\) is any irrational real number and \(N\geq 1\) is any positive integer. Show that there is an integer \(1\leq q\leq N\) and an integer \(p\) such that \[\left| q \alpha - p \right| < \frac{1}{N}.\]

Does there exist an irreducible tiling with \(1\times2\) rectangles of a \(6\times 6\) rectangle?

Irreducibly tile a floor with \(1\times2\) tiles in a room that is a \(6\times8\) rectangle.