Skip to main content

Chapter 18 Pigeonhole Principle

Exercises Practice Problems

1. Warm Up Questions.

  1. Each of the four cards below has a digit printed on one side and a letter printed on the other side.

    A classmate makes the following claim: "If there is a vowel on one side of a card then there is an odd number on the other side." Which cards must be turned over to check whether this statement is true? Solution.

    You must turn over the "E" card to ensure that there is an odd number, and you must turn over the "2" card to ensure that there is not a vowel on the other side.

  2. Suppose that four women are drinking in a bar. The owner wants to enforce the rule that no one under twenty-one is allowed to drink alcohol. The owner asks each person to tell him either (1) what she is drinking, or (2) how old they are. Here are their truthful answers:

    Table 18.0.1.
    Alice Barbara Clarice Daria
    "I am drinking Coke." "I am sixteen." "I am drinking beer." "I am twenty-five."

    Which of the people have to answer the second question in order for the owners to ensure that the law is being observed? Solution.

    The owner must find out what Barbara is drinking, and the owner must find out the age of Clarice.

  3. Which of the previous questions was easier, (a) or (b)? Why? Solution.

    Most people will find question (b) to be easier because it matches a context that we are already familiar with: the drinking age in the United States is 21. Meanwhile, the rule in part (a) is unfamiliar and we don't really know why the rule exists.

    But in fact, these two questions are variations of the same process: we are checking the validity of a statement of the form \(P \rightarrow Q\text{.}\) That also means that we have to check situations where \(\neg Q \rightarrow \neg P\) would apply.

2. First to Four Wins.

Two teams play basketball games until one team wins four games. What is the fewest number of games that they must play to be guaranteed that one team will four games? (What are your pigeons? What are your pigeonholes?) Solution.

The pigeonholes are the two teams, and the pigeons are the games being played. In order to ensure that one pigeonhole gets 4 pigeons, we need at least 7 total pigeons. This is the generalized pigeonhole principle.

Therefore, in the worst case scenario, we must play 7 games to determine the winner.

3. What's Your Birth Stone?

There 28 students enrolled in a math course. What is the largest number of these students that you can guarantee are born in the same month? (What are your pigeons? What are your pigeonholes?) Solution.

Keep in my that our worst enemy gets to decide when the birthdays are. So we must consider the worst case scenario, that the birthdays are as evenly divided as possible.

In this case, we have 12 pigeonholes (months) and 28 pigeons (students). The generalized pigeonhole principle guarantees that some month contains \(\lceil 28/12 \rceil = 3\) birthdays.

4. Tables and Chairs.

A conference room contains 8 tables and 99 chairs. What is the smallest possible number of chairs at a table having the most chairs? (What are your pigeons? What are your pigeonholes?) Solution.

In this case, the pigeonholes are the tables and the pigeons are chairs. Some table must get \(\lceil 99/8 \rceil = 13\) chairs by the generalized pigeonhole principle.

5. Coin Flips.

A coin is flipped 3 times and the outcomes are recorded (in order). For example, if heads comes up the first two times and tails the third time, then we write \(HHT\text{.}\) How many times must we flip a coin three time to be guaranteed that we have at least two outcomes that are identical? Remember: an outcome is an ordered list of the 3 flips. (What are your pigeons? What are your pigeonholes?) Solution.

We have 8 pigeonholes labeled by the possible outcomes.

\begin{equation*} HHH HHT HTH HTT THH THT TTH TTT \end{equation*}

The pigeons are the outcomes of our flips. By the pigeonhole principle, we must perform the flipping 9 times to be guaranteed that two of the outcomes are identical.

6. Midpoint Madness.

Suppose that we have 5 points \((x,y)\) in \(\R^2\) with integer coordinates. This means that both the \(x\)-coordinate and the \(y\)-coordinate are integers. Prove that the midpoint of the segment joining some pair of points also has integer coordinates. (Hint: this is a pigeonhole problem. The five "pigeons" are the points. What are the four "pigeonholes?") Solution.

This time, we have four pigeonholes, labeled by

\begin{equation*} \begin{array}{cccc} \mbox{(even, even)} & \mbox{(even, odd)} & \mbox{(odd, even)} & \mbox{(odd, odd)}. \end{array} \end{equation*}

The pigeons in this case are the points in \(\R^2\) with integer coordinates. We place a given point in the box that describes the parity (even/odd) of its two coordinates. By the pigeonhole principle, we must choose 5 points to guarantee that two end up in the same pigeonhole. Suppose that these two points are \((x_1, y_1)\) and \((x_2,y_2)\text{.}\) The midpoint is

\begin{equation*} \left( \frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2} \right). \end{equation*}

This point has integer coordinates because the sum of two odd numbers is even, and the sum of two even numbers is even. So either way, the first and second coordinates of this midpoint are integer values.

7. Points Inside a Square.

Suppose that we have 10 points \((x,y)\) in the unit square \([0,1] \times [0,1]\text{.}\) In other words, \(0 \leq x \leq 1\) and \(0 \leq y \leq 1\text{.}\) Prove that there are two points that are at distance at most \(\sqrt{2}/3\) from one another? (Hint: this time we have 10 pigeons. Create 9 pigeonholes in the unit square using a simple, geometric way.) Solution.

Once again, we must be clever about creating pigeonholes. This time, we will divide the unit square into 9 squares with side length \(1/3\text{.}\) By the pigeonhole principle, when we place 10 points in the unit square, one of these 9 squares must receive 2 (or more) points. The largest distance between these points is given by the length of the diagonal, which is

\begin{equation*} \sqrt{\left( \frac{1}{3} \right)^2 + \left( \frac{1}{3} \right)^2} = \sqrt{ \frac{2}{9} } = \frac{\sqrt{2}}{3}. \end{equation*}