6.5 The pigeonhole principle

NOTE: this is not part of A Level maths (or even further maths)

The pigeonhole principle is deceptively simple. The essence is something like this: imagine that there are 13 people in a room; at least two of them must have a birthday in the same month (as there are only 12 months, but 13 objects, so no matter how hard one tries, it is impossible to have fewer than or equal to one birthday per month).

This can be generalised; suppose that we have $n$ objects which we would like to split into $k$ sets. In this case the pigeonhole principle states that there must be at least $\left\lceil\frac{n}{k}\right\rceil$ objects⁷⁷ 7 Note that $f(x)=\left\lceil x\right\rceil$ is referred to as the \sayceiling function, and it always \sayrounds up; for example, $\lceil 1.3\rceil=2$ , $\lceil 6.8\rceil=7$ and $\rceil 1.000001\lceil=2$ . in each set.

Proof of the pigeonhole principle

This can be proved by contradiction. Let us assume that it is the case that we can partition $n$ objects into $k$ sets (i.e. the negation of what we are trying to prove) in such a way that the minimum number of objects in each set is smaller than $\left\lceil\frac{n}{k}\right\rceil$ . That is, that there exists an $a\in\mathbb{N}_{\geqq 1}$ such that the minimum number of objects in each set is

\min=\left\lceil\frac{n}{k}\right\rceil-a

(6.21)

The sum of the total numbers of objects in each set must equal the total number of elements, $n$ (e.g. if in set 1 there are $5$ objects and in set $2$ there are $8$ objects, then $n=13$ ). In case where every set has the minimum possible items, the total number of objects must be equal to

\displaystyle n=k\left(\left\lceil\frac{n}{k}\right\rceil-a\right)

(6.22)

Here, the ceiling function is in the way (of our completing the proof). To remove it, we can apply the property that

\left\lceil\frac{n}{k}\right\rceil<\frac{n}{k}+a

(6.23)

This is true, as $a\geqq 1$ . Therefore

$\displaystyle n$	$\displaystyle=k\left(\left\lceil\frac{n}{k}\right\rceil-a\right)$	(As in Equation 6.22)
	$\displaystyle>k\left(\left(\frac{n}{k}+a\right)-a\right)$	(6.24)
	$\displaystyle=k\left(\frac{n}{k}\right)$	(6.25)
	$\displaystyle=n$	(6.26)

However, $n>n$ is a clearly false statement. Thus, we have completed the proof by contradiction. $\Box$

6.5.1 Proof that at least one number is greater than or equal to the mean

Let $A$ be a set with $n$ members (which are all natural numbers). We can label the members of $A$ as $a_{1},a_{2},...,a_{n}$ . Let us partition the elements of $A$ into $n$ boxes (this isn’t hard, as we have $n$ elements, so we just put one element in each box). How does this help us? Sure, we have technically applied the pigeonhole principle (as we have placed $n$ objects into $n$ boxes, giving that there is at least $1$ element in each box - not particularly helpful) but we haven’t proven our statement. To actually prove the statement, we can combine this partitioning of our objects with a different way of considering them; let us combine them into one big number. We know that the total value of all the elements in our set is

\sum_{1\leqq i\leqq n}a_{i}

(6.27)

Now we return to nursery! You have probably played with wooden blocks, and seen how if we start with a single wooden block, we can say this represents the number $1$ . If we have two equally shaped wooden blocks, we can say this represents $2$ , and so on. In the general case⁸⁸ 8 We’re not literally going back to nursery if we have $y$ wooden blocks, we can build the number $y$ . The reverse also applies; by this line of \sayreasoning we can split the number $\sum_{1\leqq i\leqq n}a_{i}$ into $\sum_{1\leqq i\leqq n}a_{i}$ wooden blocks. If we then partition these blocks into $n$ sets, for any possible partitioning we will have at least $x$ objects in one set, where

x=\left\lceil\frac{\sum_{1\leqq i\leqq n}a_{i}}{n}\right\rceil

(6.28)

Or, alternatively, we will have a number which is at least as big as $x$ . We also know that the earlier partition of $a_{1},a_{2},...,a_{n}$ into $n$ sets will satisfy this property. Therefore, there exists at least one $k$ such that

	$\displaystyle a_{i}$	$\displaystyle\geqq\left\lceil\frac{\sum_{1\leqq i\leqq n}a_{i}}{n}\right\rceil$		(6.29)
		$\displaystyle\geqq\frac{\sum_{1\leqq i\leqq n}a_{i}}{n}$		(6.30)

Note that the expression Equation 6.30 is equivalent to the average of the elements of $A$ , and thus there exists an element greater than or equal to the average.