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.