The undeserved status of the pigeon-hole principle
Right at the moment I was introduced to the pigeon-hole principle, I understood that there was something very special about it, for the Englishman from whom I learned it told it to me under its German name "das Schubfach prinzip". Later I learned that also in other languages it is honoured by a special name. It is, indeed, surrounded by some mystique, for proofs using it are often regarded as something special, something particularly ingenious. This feeling of awe is, for instance, nicely reflected by Ross Honsberger when he concludes one of his examples with the characterization "another triumph of the pigeon-hole principle". (Earlier he has called it "a fundamental tool of combinatorics".)
It is my feeling, however, that this mystique and the surprise when we see the pigeon-hole principle being applied successfully are closely connected to the clumsiness of the usual formulations of the principle: they contain a lot of misleading noise, are overspecific, and hide the principle's arithmetic nature. Instead of composing an average formulation, I quote a typical one verbatim from the literature:
| (0) | "if more than n objects are distributed into a set of n compartments, some compartment must receive more than one of the objects". |
(Instead of the above "more than n", one often encounters the more specific "n+1".) We shall compare (0) with the alternative
| (1) | "for a nonempty, finite bag of real numbers, the maximum is at least the average (and the minimum is at most the average). |
Comparing (1) and (0), we observe to begin with that the "distributing" and "receiving" have disappeared, and rightly so, for they are just noise: the pigeon-hole principle is equally applicable when no process of distribution and reception is involved, e.g. when we wish to conclude, from the fact that a month is longer than a week, that in a month some weekday occurs more than once.
The second thing we observe is that the "objects" and the "compartments" have disappeared. That is a great improvement, for it saves us the needless trouble of making a painful identification in all those circumstances in which (for visual or linguistic reasons) the metaphor of objects and compartments does not fit nicely. In the previous example, for instance, we should not talk about a month containing a number of Tuesdays, but about Tuesday ( = compartment ) containing a number of days-of the-month ( = objects ). The whole metaphor of objects and compartments is just a pain in the neck.
Another regrettable consequence of the metaphor is that it invites a misleading visualization. Formulation (0) is in the form of an implication; the contrapositive states equivalently
| (2) | "if each of n compartments contains at most one object, they contain together at most n objects". |
Formulation (0) evokes a picture of cramped, overstuffed compartments —2 or more pigeons squeezed into a 1-pigeon hole— , whereas formulation (2) rather evokes a picture of underoccupied compartments. The difference between the pictures hides the fact that (0) and (2) are equivalent.
Remark It is not uncommon to see people distinguish —not in meaning, but in rôle— between x≤y and y≥x . The former they read as expressing (in terms of y) an upper bound for x , the latter as giving (in terms of x) a lower bound for y . I advise against trying to make such distinctions: the charm of
average ≤ maximum and
maximum ≥ average
is that they state exactly the same and need not evoke different connotations as (0) and (2) seem to do. (End of Remark.)
Finally, the traditional pigeon-hole principle is much less general than it should be: expressed in average and maximum, (0) yields
average > 1 ⇒ maximum >1
which is much weaker than (1)'s
average ≤ maximum ;
this is why (1), being really stronger than (0), is referred to as the Generalized Pigeon-hole Principle.
As an example in which the Generalized Pigeon-hole Principle comes in handy, we consider now what is known as the Problem of the German Soccer Lotto.
Variables of type "outcome" have 1 of 3 possible values; variables of type "column" consist of 13 variables of type "outcome". In the following, dummies c and d range over type "column" and W is a set of constants of type "column". We are asked to construct a set W, as small as possible, such that
(A d :: (E c : c ∈ W : (N i : 0 ≤ i < 13 : d.i = c.i) ≥ 5))
In words: W should be such a set of columns that, whatever column we choose for d, W contains a column c that coincides with d in at least 5 positions.
Set W contains at least 3 columns, for with at most 2 columns in W it is possible to choose d such that it coincides in no position with a column in W. But 3 columns suffice. Let x, y, z be the three columns in W; we can choose them such that for any i in the range 0 ≤ i < 13
{ x.i, y.i, z.i }
is the triple of possible outcome-values. With such a choice, each value d.i coincides with one of the three { x, y, z }; 13 coincidences in 3 columns yields an average of 4⅓ coincidences per column, and hence at least 1 column coincides in at least 5 positions with d . And thus the Problem of the German Soccer Lotto has been solved.
The example has been included for two reasons. Firstly it is an example for which the traditional (0) does not suffice and the stronger (1) is really needed. Secondly, it shows the arithmetic reason for the surprise that the use of the pigeon-hole principle often evokes: the three constants 3, 13 and 5 of the problem statement fortunately satisfy the magical relation that 5 is the smallest integer that is at least 13/3. It is this arithmetic accident that makes the Problem of the German Soccer Lotto trivial. Replacing 5 by 6 we get a completely different problem, which is much harder to solve! Another way to phrase the same observation is that if you can get away with an argument as simple as the pigeon-hole principle, you have just been lucky.