The Pigeonhole Principle

The following excerpt was taken from:
Kolman, Busby, & Ross(2009), Discrete Mathematical Structures, 6th ed. Upper Saddle River, NJ: Pearson Prentice Hall

“Theorem: The Pigeonhole Principle

The Pigeonhole Principle is a proof technique that often uses discrete math’s counting methods.

If n pigeons are assigned to m pigeonholes, and m < n, then at least one pigeonhole contains two or more pigeons.

Pigeonhole Principle – Proof

Suppose each pigeonhole contains at most 1 pigeon. Then at most m pigeons have been assigned. But since m < n, not all pigeons have been assigned pigeonholes. This is a contradiction. At least one pigeonhole contains two or more pigeons.

This informal and almost trivial-sounding theorem is easy to use and has unexpected power in proving intersting consequences.

Pigeonhole Principle – Example I

If we choose a group of 8 people, at least two of them will have a birthday on the same day of the week. Each person(pigeon) is assigned a day of the week(pigeonhole) on which he or she was born. Since there are eight people and only seven days of the week, the pigeonhole principle tells us that at least two people must be assigned to the same day of the week.

The pigeonhole principle provides an existence proof; there must be an object or ojbects with a certain characteristic. In this example, the characteristic is having been born on the same day of the week. The pigeonhole principle guarantees that there are at least two people with this characteristic, but gives no information on identifying these people. Only their existence is guaranteed. in contrast, a constructive proof guarantees that existence of an object or objects with a certain characteristic by actually contstructing such an object or objects. For example, we could prove that given two rational numbers p and q thre is a rational number bgetween them by showing that p+q/2 is between p and q.

In order to use the pigeonhole principle we must identify pigeons(objects) and pigeonholes(categories of the desired characteristic) and be able to count the number of pigeons and the number of pigeonholes.

Pigeonhole Principle – Example II

Shirts numbered consecutively from 1 to 20 are worn by 20 members of a bowling league. When any three of these members are chosen to be a team, the league propopses to use the sum of their shirt numbers as a code number for the team. Show if any eight of the 20 are selected, then from these eight one may form at least two different teams having the same code color.

8!/(8-3)! * 1/3! = 56 possible teams {6…57} = 52 code numbers

By the pigeonhole principle, at least two teams will have the same code number. The league needs another way to assign code numbers for each team.”

Reference:
Kolman, Busby, & Ross(2009), Discrete Mathematical Structures, 6th ed. Upper Saddle River, NJ: Pearson Prentice Hall
ISBN-13: 978-0-13-229751-6
ISBN-10: 0-13-229751-6

0
  Related Posts