Problems

Find the contrapositive of the statement: “If in every school there is a class with at least \(20\) students, then there is a school with at least \(10\) students".

Show that if \(a\) and \(b\) are numbers, then \(a^2-b^2=(a-b)\times (a+b)\).

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.

A point \(P\) and a line \(L\) are drawn on a piece of paper. What is the shortest path from \(P\) to \(L\)? You should give a proof that your path is indeed the shortest.

Each whole number is painted either blue or yellow, with the following rules:

• The sum of two numbers painted in different colours is painted yellow.

• The product of two numbers painted in different colours is painted blue.

There is at least one number of each colour. What possible colours can the product of two blue numbers have?

We make a long list of numbers in the following way. We start with \(1\) and \(1\). After that, each new number is the last digit of the sum of the two numbers right before it. For example, the beginning of the list is \[1,\,1,\,2,\,3,\,5,\,8,\,3,\,1,\,4,\ldots\]

Show that, if we keep making numbers like this forever, the list must eventually start repeating in a loop.

Let \(P(x)\) be a polynomial with integral coefficients. Suppose there exist four distinct integers \(a,b,c,d\) with \(P(a) = P(b) = P(c) = P(d) = 5\). Prove that there is no integer \(k\) with \(P(k) = 8\).