Pigeonhole Principle

The Pigeonhole Principle, also known as the Dirichlet Principle (after its inventor, the famous mathematician Peter Gustav Dirichlet, 1805–1859). This simple principle does wonders. It is amazing how easy it is to understand this idea, and how difficult it sometimes is to discover that this idea can be applied! When you look at the problems that are solved by the Pigeonhole Principle, many of

them appear to have nothing in common with each other. That is why, in April 1986, I called my lecture for the participants of the Colorado Springs Mathematical Olympiad “Invisible Pigeonhole Principle”.

Example 1:

Also Read:

New York City has 7,500,000 residents. The maximal number of hairs that can grow on a human head is 500,000. Prove that there are at least 15 residents in New York City with the same number of hairs.

Solution.

Let us set up 500,001 pigeonholes labeled by integers the 0 to 500,000, and put residents of New York into the holes labeled by the number of hairs on their heads. Since 7,500,000 > 14 ×500,001 +1

we conclude by the Pigeonhole Principle that there is a pigeonhole with at least 14 +1 pigeons, i.e., there are at least 15 residents of New York with the same number of hairs.

Example 2:

(Third Annual Colorado Springs Mathematical Olympiad, 1986)

Santa Claus and his elves paint the plane in two colours, red and green. Prove that there exist two points of the same color exactly one mile apart.

Solution.

Consider an equilateral triangle with each side equal to one mile on the given plane. Since its three vertices (pigeons) are painted in two colors (pigeonholes), we can choose two vertices painted in the same color (at least two pigeons in a single hole).

Example 3:

(Third Annual Colorado Springs Mathematical Olympiad, 1986)

Given n integers, prove that either one of them is a multiple of n, or some of them add up to a multiple of n.

Solution.

Denote the n given integers by a1, a2, …,an. Define:

If one of the numbers S1,S2,…,Sn is a multiple of n, we are done. Assume now that none of the numbers S1, S2, …,Sn is a multiple of n. Then all possible remainders upon the division of these numbers by n are 1, 2,…,n – 1, i.e., we get more numbers (namely n, our pigeons) than possible remainders (n -1 possible remainders, our pigeonholes). Therefore, among the numbers S1, S2, …,Sn there exist two numbers, say Sk and Sk+t, that give the same remainders upon the division by n.

We are done, because

  1. Sk+t – Sk is a multiple of n
  2. Sk+t – Sk = ak+1 + ak+2 + …+ak+t

In other words, we found some of the given numbers, namely ak+1 + ak+2 + …+ak+t whose sum is a multiple of n.

×

Like us on Facebook

%d bloggers like this: