$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.9: Pigeonhole Principle

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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 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.