The Pigeonhole Principle

Drs. Slamin, M.Comp.Sc.,Ph.D

Introduce by German Mathematician, Johann Peter GustavLejeune Dirichlet on 1834.

Also known as Dirichlet Drawer Principle.

Theorem

If n pigeons are assigned to m pigeonholes, and n > m, then there is pigeonhole contains at least two pigeons.

Proof

Prove by contradiction that the conclusion is not correct, so that every pigeonhole contains at most one pigeon. Since there are m pigeonholes, then at most m pigeons that can be contained. We know that there are n pigeons available and n > m, which is a contradiction.

Example

When lecturer divided students into six teams to do assignments, seven students did not attend the lecture so that they were not included in any team. Show that if the seven students join the team, then there are at least two students are in the same team!

Solution

Assume that the seven students are the pigeons, and the six  teams are the pigeonholes. The Pigeonhole Principle tells us that there are at least two students must be assigned in the same team! Assume that the seven students are the pigeons, and the six teams are the pigeonholes. The Pigeonhole Principle tells us that there are at least two students must be assigned in the same team!

Example

A scholar in a village is always asked to provide a name for a new born baby. In certain month, he prepares 3 names for first names and 3 names for second names. 11 babies are born on that month. By assuming that the scholar always gives first name and second name for one baby, show that there are atleast two babies have the same name.

Solution

Combining first names and second names gives nine names. Assume that the nine names are the pigeonholes, and the eleven babies are the pigeons. The Pigeonhole Principle tells us that there are at least two babies must be assigned in the same name!

Theorem

If n pigeons are assigns to m pigeonholes, then one of the pigeonholes must contain at least ⌊n−1/m + 1⌋ pigeons.

Proof

If each pigeonhole contains no more than ⌊n−1/m ⌋ pigeons, then there are at most m · ⌊ n – 1/m ⌋ ≤ m·n− 1/m = n − 1

pigeons in all. This contradicts our assumptions, so one of the pigeonholes must contain at least

 ⌊n−1/m + 1⌋ pigeons.

Example

Show that if any 30 students are selected, then at least 5 of them will have been born in the same day of the week.

solution

Assign each student to the day of the week on which he or she was born. Then n = 30 pigeons are being assigned to m = 7 pigeonholes. By the extended pigeonhole principle, at least

 ⌊ n – 1/m+ 1⌋ = ⌊ 29/7 + 1⌋ = 5

of the students must have been born in the same day of the week.

Related Post