
# 1.7: Pigeonhole Principle


INVESTIGATE!!

1. Suppose there are n people at a party, with n at least 2. Show that there are two people that have the same number of friends.
2. Suppose 5 points are selected from inside a $$1\times 1$$ square. Prove that two of the points must be within $$\frac{1}{\sqrt{2}}$$ of each other.

Pigeonhole principle

• Simple version: If n+1 pigeons are placed in n pigeonholes, then at least one pigeonhole contains two or more pigeons.
• General version: If n or more pigeons are placed in k pigeonholes, then at least one pigeonhole contains $$\lceil\frac{n}{k}\rceil$$ or more pigeons.

As a consequence, we can say that there must be two students at Notre Dame whose phone numbers end with the same four digits. Similarly, there must be two non-bald people in Chicago with the exact same number of hairs on their heads.

Example $$\PageIndex{1}$$:

Seven distinct numbers are selected from the set $$\{1,2,3,\ldots,11\}$$. Prove that two of these numbers must sum to 12.

Example $$\PageIndex{2}$$:

Prove that among any 7 integers there must be two whose difference is divisible by 6.

1.7: Pigeonhole Principle is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by LibreTexts.