Pigeonhole Principle

“The Pigeonhole principle” ~ Students who have never heard may think that it is a joke. The pigeonhole principle is one of the simplest but most useful ideas in mathematics. Let’s learn the Pigeonhole Principle with some applications.

Pigeonhole Principle Definition:

In Discrete Mathematics, the pigeonhole principle states that if we must put $N + 1$ or more pigeons into N Pigeon Holes, then some pigeonholes must contain two or more pigeons.

Example:

If $Kn+ 1$ (where k is a positive integer) pigeons are distributed among n holes than some hole contains at least $k + 1$ pigeons.

Applications of Pigeonhole Principle:

This principle is applicable in many fields like Number Theory, Probability, Algorithms, Geometry, etc.

Problems and Solutions:

Problem 1

A bag contains beads of two colours: black and white. What is the smallest number of beads which must be drawn from the bag, without looking so that among these beads, two are of the same colour?

Solution: We can draw three beads from bags. If there were no more than one bead of each colour among these, then there would be no more than two beads altogether. This is obvious and contradicts the fact that we have chosen their beads. On the other hand, it is clear that choosing two beads is not enough. Here the beads play the role of pigeons, and the colours (black and white) play the role of pigeonhole.

Problem 2

Find the minimum number of students in a class such that three of them are born in the same month?

Solution: Number of month $n =12$

According to the given condition,

$K+1 = 3$

$K = 2$

$M = kn +1 = 2×12 + 1 = 25$.

Problem 3

Show that from any three integers, one can always choose two so that $a^3$b – a$b^3$ is divisible by 10.

Solution: We can factories the term $a^3$b – a$b^3$ = $ab(a + b)(a - b)$, which is always even, irrespective of the pair of integers we choose.

If one of three integers from the above factors is in the form of 5k, which is a multiple of 5, then our result is proved.

If none of the integers is a multiple of 5 then the chosen integers should be in the form of $(5k)+-(1)$ and $(5k)+-(2)$ respectively.

Clearly, two of these three numbers in the above factors from the given expression should lie in one of the above two, which follows by the virtue of this principle.

These two integers are the ones such that their sum and difference is always divisible by 5. Hence, our result is proved.

Problem 4

If n is a positive integer not divisible by 2 or 5 then n has a multiple made up of 1's.

Problem 5

Let $X \subseteq{1,2, \ldots, 99}$ and $|X|=10$. Show that it is possible to select two disjoint nonempty proper subsets $Y, Z$ of $X$ such that $\sum(y \mid y \in Y)=\sum(z \mid z \in Z)$.

Problem 6

Let $A_{1} B_{1} C_{1} D_{1} E_{1}$ be a regular pentagon. For $2 \leq n \leq 11$,
let $A_{n} B_{n} C_{n} D_{n} E_{n}$ be the pentagon whose vertices are the midpoints of the sides of the pentagon $A_{n-1} B_{n-1} C_{n-1} D_{n-1} E_{n-1}$. All the 5 vertices of each of the 11 pentagons are arbitrarily coloured red or blue. Prove that four points among these 55 points have the same colour and form the vertices of a cyclic quadrilateral.

Some Useful links:

• A Magical Age Problem - Watch the video
• Triangular Number Sequence - Explanation with Application
• Math Olympiad Program at Cheenta