Pigeonhole Principle with Examples

Here we will see how obvious the pigeonhole principle is. Its proof is very simple, and amazingly, it has several useful applications. Let us start by considering a situation where we have 10 boxes and 11 objects to be placed in them. Wouldn’t you agree that regardless of the way the objects are placed in the two boxes at least one box will have more than one object in it? On the face of it, this seems obvious. This is actually an application of the pigeonhole principle, which we now state.

Theorem 1 (The Pigeonhole Principle):

Let there be n boxes and (n+1) objects. Then, under any assignment of objects to the boxes, there will always be a box with more than one object in it.

Proof:

Let us label the n pigeonholes 1, 2, …, n, and the m pigeons p₁, p₂, …, p_m. Now, beginning with p₁, we assign one each of these pigeons the holes numbered 1,2, …, n, respectively. Under this assignment, each hole has one pigeon, but there are still (m−n) pigeons left. So, in whichever way we place these pigeons, at least one hole will have more than one pigeon in it. This completes the proof!

This result appears very trivial but has many applications. For example, using it you can show that:<br>• if 8 people are picked in any way from a group, at least 2 of them will have been born on the same weekday.<br>• in any group of 13 people, at least two are born in the same month.

Let us consider some examples of its application, in detail.

Example 01

Assuming that friendship is mutual, show that in any group of people we can always find two persons with the same number of friends in the group.

Solution:

If there are n persons in the group, then let the number of friends the ith person has be f(i), i = 1,…, n. Clearly, f(i) can take values only between 0 and (n − 1).

If some f(i) is 0, it means that the ith person does not have any friends in the group. In this case, no person can be friends with all the other (n − 1) people. So, no f(i) can be (n − 1). So, only one of the values 0 or (n − 1) can be present among the f(i)’s. So, then f(i)’s can take only (n − 1) distinct values. Therefore, by the pigeonhole principle, two f(i)’s must be equal. Then the corresponding i’s have the same number of friends in the group.

Example 02

Suppose 5 points are chosen at random within or on the boundary of an equilateral triangle of side 1 meter. Show that we can find two points at a distance of at most ½ meter.

Solution:

Divide the triangle into four equilateral triangles of side ½ m by joining the midpoints of the sides by three line segments (see Fig). These four triangles may now be considered as boxes and the five points as objects. By the pigeonhole principle, at least one of these smaller triangles will have two points in or on it. Clearly, the distance between these two points is at most ½ meter.

Example 03

Given any ten different positive integers less than 107, show that there will be two disjoint subsets with the same sum.

Solution:

The highest numbers we could be given would be 97, 98, …, 106, which add up to 1015. So, consider pigeonholes marked 0, 1, 2,…, 1015. The set of 10 positive integers have 2¹⁰ = 1024 subsets. Put a subset in the pigeonhole marked with the sum of the numbers in the set. The 1024 subsets have to be put in 1016 pigeonholes. So, some pigeonhole will have more than one subset with the same sum. Now, note that two subsets that we get with the same sum, may not be disjoint. But, by dropping the common elements in them, we are left with disjoint subsets with the same sum.

Example 04

If 10 points are chosen in an equilateral triangle of side 3 cm, show that we can find two points at a distance of at most 1 cm.

Solution:

By drawing lines parallel to the sides and through the points trisecting each side, we can divide the equilateral triangle into 9 equilateral triangles of side 1 cm. Thus, if 10 points are chosen, at least two of them must lie in one of the 9 triangles.

Example 05

On 11 occasions a pair of persons from a group of 5 was called for a function. Show that some pair of persons must have attended the function at least twice.

Solution:

5 persons can be paired in C(5, 2) =10 ways. Hence, if pairs are invited 11 times, at least one pair must have been invited twice or more times, by the pigeonhole principle.

Example 06

Four persons were found in a queue, independently, on 25 occasions. Show that at least on two occasions they must have been in the queue in the same order.

Solution:

Four persons can be arranged in a line in 4! = 24 ways. Hence, if we consider 25 occasions, at least on two occasions the same ordering in the queue must have been found, by the pigeonhole principle.

As you know, mathematics develops through a process of generalization. You know that the principle is valid for n+1 objects and n boxes. It is natural to ask: what if we have, say, 4n+1 objects and 4 boxes? Can we prove a similar principle? In fact, we can, as given below.

Theorem 2 (The Generalized Pigeonhole Principle):

If nm + 1 objects are distributed among m boxes, then at least one box will contain more than n objects. This can be reworded as: Let k and n be positive integers. If k balls are put into n boxes, then some box contains at least \left[ \frac{k}{n} \right]+1 balls, where [x] denotes the greatest integer less than x.

Proof:

We prove this by contradiction. Suppose all the m boxes have at most n objects in them. Then the total number of objects is at most nm, a contradiction. Hence, the theorem.

Applying this result, we see, for example, that suppose 479 students have enrolled in the course Discrete Mathematics, consisting of 6 units. Then, at least \left[ \frac{479}{6} \right]+1=80 students are studying the same unit at a given point of time.

Example 07

Show that in any group of 30 people, we can always find 5 people who were born on the same day of the week.

Solution:

30 people can be assigned to 7 days of the week. Then at least \left[ \frac{30}{7} \right]+1=5 of them must have been born on the same day.

Example 08

20 cards, numbered from 1 to 20, are placed face down on a table. 12 cards are selected one at a time and turned over. If two of the cards add up to 21, the player loses. Is it possible to win this game?

Solution:

The pairs that can add up to 21 are (1, 20), (2, 19),…, (10,11). So, there are 10 such pairs. In turning 12 cards, at least one of these pairs will be included. Therefore, the player will lose.

Example 09

Show that every sequence of n² + 1 distinct integers includes either an increasing subsequence of n + 1 numbers or a decreasing subsequence of n + 1 numbers.

Solution:

Let the sequence be a₁, a₂, ….,{{a}_{{{n}^{2}}+1}}. Suppose there is no increasing subsequence of n + 1 numbers. For each of these a_k’s, let s(k) be the length of the longest increasing subsequence beginning at a_k. Since all n² + 1 of the s(k)’s are between 1 and n, at least \left[ \frac{{{n}^{2}}+1}{n} \right]+1=n+1 of these numbers are the same. [The s(k)’s are the objects and the numbers from 1 to n are the boxes.]

Now, if I < j and s(i) = s(j),  then a_i > a_j. Otherwise ai followed by the longest increasing subsequence starting at a_j would be an increasing subsequence of length s(j) + 1 starting at a_i. This is a contradiction, since s(i) = s(j).

Therefore, all the n + 1 integers a_k, for which s(k) = m, must from a decreasing subsequence of length at least n + 1.

Example 10

Take n integers, not necessarily distinct. Show that the sum of some of these numbers is a multiple of n.

Solution:

Let S(m) be the sum of the first m of these numbers. If for some r and m, r < m, S(m) − S(r) is divisible by n, then a_r+1 + a_r+2 + … + a_m is a multiple of n. This also means that S(r) and S(m) leave the same remainder when divided by n. So, if we cannot find such pairs m and r, then it means that the n numbers S(1), S(2),…, S(n) leave different remainders when divided by n. But there are only n possible remainders, viz., 0, 1, 2,…, (n − 1). So, one of these numbers must leave a remainder of 0. This means that one of the S(i) s is divisible by n. This completes the proof.

In fact, in this example we have proved that one of the sums of consecutive terms is divisible by n. 

Example 11

If any set of 11 integers is chosen from 1, …,20, show that we can find among them two numbers such that one divides the other.

Solution:

Consider the following grouping of numbers: {1, 2, 4, 8, 16}, {3, 9, 18}, {5, 15}, {6, 12}, {7, 14}, {10, 20}, {11}, {13}, {17}, {19}.

There are 10 groupings, exhausting all the 20 integers from 1 to 20. If 11 numbers are chosen it is impossible to select at most one from each group. So two numbers have to be selected from some group. Obviously one of them will divide the other.

Example 12

If 100 balls are placed in 15 boxes, show that two of the boxes must have the same number of balls.

Solution:

Suppose x₁, x₂,…, x₁₅ are the number of balls in the 15 boxes, listed in increasing order, assuming that all these numbers are different. Then, clearly, x_i ≥ i − 1 for i = 1, 2, …,15. But then, \sum\limits_{i=1}^{15}{{{x}_{i}}}\ge 14.15/2=105.

But the total number of balls is only 100, a contradiction. Thus, the x_is cannot all be different.

<< Previous Topic Inclusion and Exclusion

Next Topic >> Permutation

;