This elementary idea, thought to have been first articulated as such by Dirichlet and often known as Dirichlet’s principle, is simply a statement that if there are pigeons to be placed into pigeonholes, and there are more pigeons than pigeonholes, then some pigeonhole will contain more than one pigeon. The statement can be extended to cover cases where the number of pigeons is more than double, treble, and so on, the number of pigeonholes, requiring the existence of pigeonholes with at least three, four, and so on, pigeons inside. The following is an example (taken from International Mathematics Tournament of Towns) of an accessible problem whose solution is best wrapped up using this idea.
Example 2.1
Ten friends send greeting cards to each other, each sending 5 cards to different people. Prove that at least two of them sent cards to each other.
Strategy
The words “at least” are the ones which give the experienced student the clue that the pigeonhole principle will be useful here. The question is going to require a count of how many routes there are, and how many different routes are taken. Since routes occur in pairs (one for each direction) the objective of the proof will be to find that more than half the routes must be used, as then the pigeon hole principle will require that at least two are such a pair.
Solution 2.1
Since each of the ten friends can send to nine others, there are 90 available routes. However, each pair of friends is involved in 2 routes, so that there are 45 pairs. If more than 45 cards are sent, then by the pigeonhole principle, two of the transmissions must be on the same route in opposite directions. In this case since each student actually sends 5 cards, there are 10 times 5, or 50 (>45) transmissions altogether and thus there are two friends who send cards to each other.
Note
Such challenges can generate discussion as to other situations where the pigeonhole principle is applicable, such as in combinatorics, number theory and geometry. However, while a useful tool, it does require special circumstances for its application. Two problems can look quite similar. One can be handily dispatched by the principle and the other can be very difficult indeed. It requires judgment and insight to detect when the principle can be used and to be able to identify the “pigeons” and the “pigeonholes”.