The Pigeonhole Principle

Theorem: If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.

The abstract formulation of the principle: Let X and Y be finite sets and let

F : XY  be a function then,

1) If X has more elements than Y, then f is not one-to-one.

2)If X and Y have the same number of elements and f is onto, then f is one-to-one.

3)If X and Y have the same number of elements and f is one-to-one, then f is onto.

Pigeonhole principle is one of the simplest but most useful ideas in mathematics. We will see more applications that proof of this theorem.

Example –: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

Solution: Apply pigeonhole principle.
No. of colors (pigeonholes) n = 3
No. of marbles (pigeons) K+1 = 4
Therefore the minimum no. of marbles required = Kn+1
By simplifying we get Kn+1 = 10.
Verification: ceil[Average] is [Kn+1/n] = 4
[Kn+1/3] = 4
Kn+1 = 10
i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

Pigeonhole principle another form –

Theorem: Let a1, a2, . . . , an be positive integers.
If a1+ a2+ . . . + an – n + 1 objects are put into n boxes, then either the 1st box contains at least a1 objects, or the 2nd box contains at least a2 objects, . . ., the nth box contains at least an objects.

Application of this theorem is more important, so let us see how we apply this theorem in problem solving.

Example – 1: In a computer science department, a student club can be formed with either 9 members from first year or 7 members from second year or 6 from third year or 3 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed?

Solution: we can directly apply from the above formula where,
a1 =9, a2 =7, a3 =6, a4 =3 and n=4
Therefore the minimum number of students required to ensure department club to be formed is
9 + 7+ 6 + 3 – 4 + 1 = 22