Chapter 19 Pigeonhole Principle
Exercises Practice Problems
1. 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.
2. 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.
3. 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.
4. 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.
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.
5. 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
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
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.
6. 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