Problems

One of the most important tools in maths is the Pigeonhole Principle. You may have already met it before, but if not, let’s recap it quickly. Simply put: the Pigeonhole Principle states that if you have \(n\) pigeons (or objects) that you want to place into a number of pigeonholes (or containers) that is strictly smaller than \(n\), e.g: \(10\) pigeons but only \(9\) pigeonholes, then there will be a pigeonhole with at least two pigeons. Why is this true? Imagine that every pigeonhole had at most one pigeon. Since we have \(9\) pigenholes in total, there would be at most \(9\) pigeons, not \(10\), as we are told. Today we will see how this principle can be used to solve problems about numbers and their divisibility properties.
Before we get started, we need to recap a very important concept: if we have two numbers, say \(a\) and \(b\), we can divide \(a\) by \(b\), and we will obtain a quotient \(q\) and a remainder \(r\), and write \[a=q\times b + r\] for example: if we divide \(9\) by \(4\), we can write \(9=2\times 4 + 1\), i.e: the quotient will be \(2\) and the remainder will be \(1\). A final key fact that we need to recap is the following: imagine we want to divide two numbers, for example \(11\) and \(6\) by the same number, say \(4\). We can write \[11=2\times 4 + 3\qquad \text{and}\qquad 6=1\times 4 + 2\] So we can imagine \(11\) as two packs of \(4\) little squares and \(3\) “left over" squares, and \(6\) as one pack of four little squares with \(2\) left over squares. We can combine these \(5\) “left over" squares into one new pack of four, with now one “left" over square. With this way of thinking, we see that the remainder of a sum of two numbers \(a\) and \(b\) is precisely the remainder of the sum of the remainder of \(a\) plus the remainder of \(b\).

A final remark: in today’s sheet, when we say positive whole numbers, or natural numbers, we will mean the numbers \(1,2,\cdots\)

Show that given any three numbers, at least two of them will have the same parity. Recall that the parity of a number is whether it is odd or even.

Show that given any \(6\) whole numbers - not necessarily consecutive - at least two of them will have the same remainder when divided by \(5\).

Show that given any \(3\) numbers, there will be two of them so that their difference is an even number.

There are six kids in the math circle. Each kid has their own seat, and they always sit in the same one. One day, however, the head tutor decided to rearrange the seating, and it turned out that every kid ended up in a different seat from their usual one. In how many ways can the head tutor do this?

Seven students are standing on a straight line, one after the other. Three of the students, let’s call them \(A,B,\) and \(C\) behave badly and can’t be next to each other. For example: \(\star \star AB\star \star C\) and \(\star ABC\star \star \star\) are invalid arrangements, where the star denotes any other student. However, \(A\star B\star \star \star C\) is an example of a valid arrangement. How many valid arrangements are there?

Show that if \(x,y,z\) are distinct nonzero numbers such that \(x+y+z = 0\), then we have \[\left(\frac{x-y}{z}+\frac{y-z}{x}+\frac{z-x}{y}\right)\left(\frac{z}{x-y}+\frac{x}{y-z}+\frac{y}{z-x}\right) = 9.\]

The Chinese remainder theorem is a fundamental result in number theory that allows one to decompose congruence problems to into simpler ones. The theorem says the following.

Suppose that \(m_1,m_2\) are coprime (i.e: they have no prime factors in common) natural numbers and \(a_1,a_2\) are integers. Then there is a unique integer \(x\) in the range \(0\leq x \leq m_1m_2-1\) such that \[x \equiv a_1 \pmod{m_1} \quad \text{ and } \quad x \equiv a_2 \pmod{m_2},\] where the notation \(x\equiv y \pmod{z}\) means that \(x-y=kz\) for some integer \(k\). Prove the Chinese remainder theorem using the pigeonhole principle.

We have ten positive integers \(x_1,\dots,x_{10}\) such that \(10\leq x_i\leq 99\) for \(1\leq i\leq 10\). Prove that there are two disjoint subsets of \(x_1,\dots,x_{10}\) with equal sums of their elements.

In Problemtown there are \(n\) farms and also \(n\) wells which we think of as points on a plane. We know that no three points lie on a straight line. The mayor wants to build straight roads so that each farm is connected to exactly one well, and each well is connected to exactly one farm. The mayor insists that no two roads are allowed to cross each other. Prove that this is always possible.