1.3 The Pigeonhole Principle 111.3 The Pigeonhole Principle........................................
Thepigeonhole principle(orDirichlet’s box principle) is usually applied to problems
in combinatorial set theory, combinatorial geometry, and number theory. In its intuitive
form, it can be stated as follows.
Pigeonhole principle.Ifkn+ 1 objects(k≥ 1 not necessarily finite)are distributed
amongnboxes, one of the boxes will contain at leastk+ 1 objects.
This is merely an observation, and it was Dirichlet who first used it to prove non-
trivial mathematical results. We begin with an easy problem, which was given at the
International Mathematical Olympiad in 1972, proposed by Russia.
Example.Prove that every set of 10 two-digit integer numbers has two disjoint subsets
with the same sum of elements.
Solution.LetSbe the set of 10 numbers. It has 2^10 − 2 =1022 subsets that differ from
bothSand the empty set. They are the “pigeons.’’ IfA⊂S, the sum of elements ofA
cannot exceed 91+ 92 +···+ 99 =855. The numbers between 1 and 855, which are all
possible sums, are the “holes.’’ Because the number of “pigeons’’ exceeds the number of
“holes,’’ there will be two “pigeons’’ in the same “hole.’’ Specifically, there will be two
subsets with the same sum of elements. Deleting the common elements, we obtain two
disjoint sets with the same sum of elements.
Here is a more difficult problem from the 26th International Mathematical Olympiad,
proposed by Mongolia.
Example.Given a setMof 1985 distinct positive integers, none of which has a prime
divisor greater than 26, prove thatMcontains at least one subset of four distinct elements
whose product is the fourth power of an integer.
Solution.We show more generally that if the prime divisors of elements inMare among
the prime numbersp 1 ,p 2 ,...,pnandMhas at least 3· 2 n+1 elements, then it contains
a subset of four distinct elements whose product is a fourth power.
To each elementminMwe associate ann-tuple(x 1 ,x 2 ,...,xn), wherexiis0ifthe
exponent ofpiin the prime factorization ofmis even, and 1 otherwise. Thesen-tuples
are the “objects.’’ The “boxes’’ are the 2npossible choices of 0’s and 1’s. Hence, by the
pigeonhole principle, every subset of 2n+1 elements ofMcontains two distinct elements
with the same associatedn-tuple, and the product of these two elements is then a square.
We can repeatedly take aside such pairs and replace them with two of the remaining
numbers. From the setM, which has at least 3· 2 n+1 elements, we can select 2n+ 1
such pairs or more. Consider the 2n+1 numbers that are products of the two elements
of each pair. The argument can be repeated for their square roots, giving four elements
a, b, c, dinMsuch that
√
ab√
cdis a perfect square. Thenabcdis a fourth power and
we are done. For our problemn=9, while 1985> 3 · 29 + 1 =1537.