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 nn objects which we would like to split into kk sets. In this case the pigeonhole principle states that there must be at least nk\left\lceil\frac{n}{k}\right\rceil objects77 7 Note that f(x)=xf(x)=\left\lceil x\right\rceil is referred to as the \sayceiling function, and it always \sayrounds up; for example, 1.3=2\lceil 1.3\rceil=2, 6.8=7\lceil 6.8\rceil=7 and 1.000001=2\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 nn objects into kk 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 nk\left\lceil\frac{n}{k}\right\rceil. That is, that there exists an a1a\in\mathbb{N}_{\geqq 1} such that the minimum number of objects in each set is

min=nka\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, nn (e.g. if in set 1 there are 55 objects and in set 22 there are 88 objects, then n=13n=13). In case where every set has the minimum possible items, the total number of objects must be equal to

n=k(nka)\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

nk<nk+a\left\lceil\frac{n}{k}\right\rceil<\frac{n}{k}+a (6.23)

This is true, as a1a\geqq 1. Therefore

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

However, n>nn>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 AA be a set with nn members (which are all natural numbers). We can label the members of AA as a1,a2,,ana_{1},a_{2},...,a_{n}. Let us partition the elements of AA into nn boxes (this isn’t hard, as we have nn 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 nn objects into nn boxes, giving that there is at least 11 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

1inai\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 11. If we have two equally shaped wooden blocks, we can say this represents 22, and so on. In the general case88 8 We’re not literally going back to nursery if we have yy wooden blocks, we can build the number yy. The reverse also applies; by this line of \sayreasoning we can split the number 1inai\sum_{1\leqq i\leqq n}a_{i} into 1inai\sum_{1\leqq i\leqq n}a_{i} wooden blocks. If we then partition these blocks into nn sets, for any possible partitioning we will have at least xx objects in one set, where

x=1inainx=\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 xx. We also know that the earlier partition of a1,a2,,ana_{1},a_{2},...,a_{n} into nn sets will satisfy this property. Therefore, there exists at least one kk such that

ai\displaystyle a_{i} 1inain\displaystyle\geqq\left\lceil\frac{\sum_{1\leqq i\leqq n}a_{i}}{n}\right\rceil (6.29)
1inain\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 AA, and thus there exists an element greater than or equal to the average.