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 objects which we would like to split into sets. In this case the pigeonhole principle states that there must be at least objects77 7 Note that is referred to as the \sayceiling function, and it always \sayrounds up; for example, , and . 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 objects into 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 . That is, that there exists an such that the minimum number of objects in each set is(6.21)
The sum of the total numbers of objects in each set must equal the total number of elements, (e.g. if in set 1 there are objects and in set there are objects, then ). In case where every set has the minimum possible items, the total number of objects must be equal to
Here, the ceiling function is in the way (of our completing the proof). To remove it, we can apply the property that(6.23)
This is true, as . Therefore
(As in Equation 6.22) (6.24) (6.25) (6.26)
However, is a clearly false statement. Thus, we have completed the proof by contradiction.
6.5.1 Proof that at least one number is greater than or equal to the mean
Let be a set with members (which are all natural numbers). We can label the members of as . Let us partition the elements of into boxes (this isn’t hard, as we have 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 objects into boxes, giving that there is at least 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
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 . If we have two equally shaped wooden blocks, we can say this represents , and so on. In the general case88 8 We’re not literally going back to nursery if we have wooden blocks, we can build the number . The reverse also applies; by this line of \sayreasoning we can split the number into wooden blocks. If we then partition these blocks into sets, for any possible partitioning we will have at least objects in one set, where
Or, alternatively, we will have a number which is at least as big as . We also know that the earlier partition of into sets will satisfy this property. Therefore, there exists at least one such that
Note that the expression Equation 6.30 is equivalent to the average of the elements of , and thus there exists an element greater than or equal to the average.