Skip to main content
Mathematics LibreTexts

9.2: The Pigeonhole Principle

  • Page ID
    23935
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    If a mail carrier has m letters to distribute among n mailboxes (or “pigeonholes”), and \(m > n\), then it is clear that at least one of the mailboxes will have to get more than one letter. This important observation is known as the “Pigeonhole Principle.” (See Exercise \(9.3.6\) for the proof.) In the language of sets, it can be stated as follows.

    Proposition \(9.2.1\) (Pigeonhole Principle).

    Let \(B\) and \(A_{1}, A_{2}, \ldots, A_{n}\) be finite sets. If \[B \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n} ,\]

    and \(\# B > n\), then \(\# A_{i} \geq 2\), for some \(i\).

    Here are a few of the many applications of the Pigeonhole Principle. In these real-world examples, our explanations will be a bit informal.

    Example \(9.2.2\).

    Bob’s sock drawer has many, many socks in it, and they come in 4 colours. Unfortunately, the light in his room has burned out, so he cannot see anything. How many socks should he grab from the drawer, so that he can be sure at least two of them are of the same colour?

    Solution

    Bob should grab 5 (or more) socks.

    To see this, note, first, that taking 4 socks may not be enough: If Bob grabs only 4 socks, it is possible that he has one sock of each of the 4 different colours. Then he would not have two socks of the same colour.

    Now suppose Bob grabs (at least) 5 socks. He can sort them into 4 piles, by colour. Since 5 > 4, one of the piles must have more than one sock. So there are (at least) 2 socks of the same colour.

    Example \(9.2.3\).

    If you pick 50 numbers from 1 to 98, then it is guaranteed that two of them will add up to exactly 99.

    Solution

    The numbers from 1 to 98 can be divided into 49 pigeonholes: \[\{1,98\},\{2,97\},\{3,96\}, \ldots,\{49,50\} .\]

    (So two different numbers \(x\) and \(y\) are in the same pigeonhole iff \(x+y = 99\).) Since 50 > 49, two of the numbers we chose must be in the same pigeonhole. Then the sum of these two numbers is exactly 99.

    Example \(9.2.4\).

    If you pick 5 points on the surface of a (spherical) orange, then there is always a way to cut the orange exactly in half, such that at least 4 of your points are in the same half. (We assume any point that is exactly on the cut is considered to belong to both halves.)

    Solution

    Any two of the points will lie on a great circle of the sphere, so we can cut the orange so that 2 of the points are exactly on the cut. The other 3 points are distributed in some way among the two halves of the orange. By the Pigeonhole Principle, at least two of those three points are in the same half. Then that half contains the 2 points on the cut, plus these additional 2 points, for a total of (at least) 4 of the points you picked.

    Exercise \(9.2.5\).

    1. There are ten people in a skating rink, playing hockey. Explain how you know that two of them were born on the same day of the week.
    2. If there are 400 students in an elementary school, explain how you know that (at least) two of them have the same birthday.
    3. If there are 700 employees at a company, explain how you know that there are two of them with the same initials. (That is, their first names start with the same letter, and their last names start with the same letter.)
    4. It is known that:
      • No one has more than 300, 000 hairs on their head.
      • More than a million people live in Calgary.
        Show that there are two people in Calgary who have exactly the same number of hairs on their heads.

    In addition to the above real-world examples, the Pigeonhole Principle has important applications in theoretical mathematics.

    Corollary \(9.2.6\).

    Suppose \(A\) and \(B\) are finite sets.

    1. If there exists a one-to-one function \(f: A \rightarrow B\), then \(\# A \leq \# B\).
    2. If there exists an onto function \(f: A \rightarrow B\), then \(\# A \geq \# B\).
    Proof

    Let \(m = \# A\) and \(n = \# B\).

    1. Suppose \(f: A \rightarrow B\) is one-to-one, and \(m > n\). Assume without loss of generality that \(B=\{1,2, \ldots, n\}\), so we may let \[A_{i}=f^{-1}(i) \quad \text { for } i=1,2, \ldots, n .\]
      For any \(a \in A\), we have \(a \in f^{-1}(f(a))=A_{f(a)}\), so \(a \in A_{1} \cup A_{2} \cup \cdots \cup A_{n}\). Since \(a\) is an arbitrary element of \(A\), this implies \(A \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n}\). Because \(\# A = m > n\), we conclude that \(\# A_{i} \geq 2\) for some \(i\). This means \(\# f^{-1}(i)>1\), which contradicts the fact that \(f\) is one-to-one.
    2. Suppose \(f: A \rightarrow B\) is onto, and \(m < n\). There is no harm in assuming \(A=\{1,2, \ldots, m\}\), and then we may let \[B_{i}=\{f(i)\}\]
      for \(i=1,2, \ldots, m\). Since \(f\) is onto, we know, for any \(b \in B\), there is some \(i \in A\), such that \(f(i) = b\). This means \(b \in B_{i}\) ; hence, \(b \in B_{1} \cup B_{2} \cup \cdots \cup B_{m}\). Since \(b\) is an arbitrary element of \(B\), this implies \(B \subset B_{1} \cup B_{2} \cup \ldots \cup B_{m}\). Because \(\# B = n > m\), we conclude that \(\# B_{i} \geq 2\) for some \(i\). This contradicts the fact that \(\# B_{i} = 1\) (because \(B_{i}=\{f(i)\}\) has only one element).

    Remark \(9.2.7\).

    Instead of Proposition \(9.2.1\), many mathematicians consider the contrapositive of Corollary \(9.2.6(1)\) to be the Pigeonhole Principle:

    If \(\# A > \# B\), then there does not exist a one-to-one function from \(A\) to \(B\).

    Exercise \(9.2.8\).

    1. Suppose \(A\) is a set of 10 natural numbers between 1 and 100 (inclusive). Show that two different subsets of \(A\) have the same sum. For example, if \[A=\{2,6,13,30,45,59,65,82,88,97\} ,\]
      then the subsets \(\{6, 13, 45, 65\}\) and \(\{2, 30, 97\}\) both add up to 129. [Hint: Compare the answers to two questions: How many subsets of \(A\) are there? Since there are only 10 elements of \(A\), and all of them are \(\leq 100\), how many different possible sums are there?]
    2. Show that if you put 5 points into an equilateral triangle of side length 2 cm, then there are two of the points that are no more than 1 cm apart. [Hint: Divide the triangle into 4 equilateral triangle of side length 1 cm.]
    3. The numbers 1, 11, 111, 1111, etc. are called repunits. (Their decimal representation consists entirely of 1’s.) Show that some repunit is divisible by 2017. [Hint: If \(n \times 10^{k}\) is divisible by 2017, for some \(k \in N\), then \(n\) is divisible by 2017. Why?]
    4. Show that \(\# A\) is well-defined. That is, if \(\# A = m\) and \(\# A = n\), for some \(m, n \in N\), then \(m = n\). [Hint: Apply Corollary \(9.2.6\) with \(B = A\).]
    5. Show \(\mathbb{N}\) is infinite. [Hint: Proof by contradiction. Apply Corollary \(9.2.6(1)\).]

    Remark \(9.2.9\).

    Here are two generalizations of the Pigeonhole Principle that are often useful.

    1. If a mail carrier has \(m\) letters to distribute among \(n\) mailboxes, and \(m > kn\), then at least one of the mailboxes has to get more than \(k\) letters.
    2. Suppose a mail carrier has \(m\) letters to distribute among \(n\) mailboxes. If \[k_{1}, k_{2}, \ldots, k_{n} \in \mathbb{N} \text { and } m>k_{1}+k_{2}+\cdots+k_{n} ,\]
      then there must be some \(i\), such that the \(i\)th mailbox gets more than \(k_{i}\) letters.

    Exercise \(9.2.10\).

    State (1) and (2) of Remark \(9.2.9\) analogously to:

    1. Proposition \(9.2.1\) (that is, in terms of a set \(B\) contained in \(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\)), and
    2. Corollary \(9.2.6(1)\) (that is, in terms of a function \(f : A \rightarrow B\)).

    Exercise \(9.2.11\).

    1. Strengthen the conclusion of Exercise \(9.2.5(4)\): show there is a collection of 4 people in Calgary who all have exactly the same number of hairs on their head.
    2. As in Example \(9.2.2\), Bob’s sock drawer has many, many socks in it, and they come in 4 colours. How many socks should he grab from the drawer, so that he can be sure at least 12 of them are of the same colour?
    3. Betty’s sock drawer has 6 blue socks, 10 red socks, 14 white socks, and 18 black socks. How many socks should she grab from the drawer, so that she can be sure at least 12 of them are of the same colour?

    This page titled 9.2: The Pigeonhole Principle is shared under a CC BY-NC-SA 2.0 license and was authored, remixed, and/or curated by Dave Witte Morris & Joy Morris.

    • Was this article helpful?