# 1.7: Pigeonhole Principle

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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.