Chapter 2 Pigeonhole Principle
Exercises Practice Problems
1. Sums of Subsets.
Suppose that six distinct integers are chosen from \([10] = \{ 1, 2, 3, \ldots, 10 \}\text{.}\) Must there be two whose sum is 11? Explain. Solution.
Yes. Create five boxes with labels \(1,10\text{,}\) \(2,9\text{,}\) \(3,8\text{,}\) \(4,7\text{,}\) \(5,6\text{.}\) We have six balls whose labels are chosen from \([10]\text{.}\) We place an element \(k\) in the box whose label includes \(k\text{.}\) Some box must receive two balls, and their sum is 11.
Suppose that five distinct integers are chosen from \([9] = \{ 1, 2, 3, \ldots, 9 \}\text{.}\) Must there be two whose sum is 10? Explain. Solution.
No. Choose the numbers \(1,2,3,4,5\text{.}\) The sum of two elements is at most 9.
2. Student Birthdays.
There 28 students enrolled in a combinatorics course. What is the largest number of these students that you can guarantee are born in the same month? Solution.
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. Fewest Chairs at a Table.
A conference room contains 8 tables and 99 chairs. What is the smallest possible number of chairs at a table having the most chairs? 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. A Small Triangle.
Suppose that we have 19 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 three points that create a triangle \(T\) with area at most \(1/18\text{.}\) Solution.
Partition the unit square into nine \(1/3 \times 1/3\) squares. By the pigeonhole principle, one of these 9 squares must get at least 3 points. We claim that triangle \(T\) has area at most \(1/18\text{,}\) which is one half of the area of the \(1/3 \times 1/3\) square. (Note: we consider 3 colinear points as creating a degenerate triangle with area 0.) One way to see this is to draw horizontal lines at the uppermost and lowermost points of \(T\text{.}\) Then draw vertical lines at the leftmost and rightmost points in \(T\text{.}\) These 4 lines create a rectangle \(A\) that has twice the area of \(T\text{.}\) Furthermore, this rectangle \(A\) is inside the \(1/3 \times 1/3\) square. Therefore, the area of \(T\) is at most \(1/18\text{.}\)
5. A Large Domain.
Consider a function \(f: A \rightarrow B\) where \(|A| > |B|\text{.}\) What conclusion can you draw by applying the pigeonhole principle? Be as specific as possible. Solution.
Such a function cannot be injective. Here, the elements of \(A\) are the balls and the elements of \(B\) are the boxes. Some box must receive more than one ball.
6. Integer-Valued Midpoint.
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.
Categorize points by the parity of their coordinates: (even, even), (even, odd), (odd, even) or (odd, odd). Since we have 5 points, there must be two points of the same type. The midpoint
of two points \((x_1, y_1)\) and \((x_2, y_2)\) of the same type also has integer coordinates.
7. More Sums of Subsets.
Let \(A\) be a set of six positive integers, each of which is less than 13. Show that there must be two distinct subsets \(B,C \subset A\) whose elements, when added up, give the same sum. For example, if \(A = \{ 1, 3, 4, 5, 10, 12 \}\) then the subsets \(B= \{ 1, 4, 10 \}\) and \(C=\{ 3, 12 \}\) do the trick: summing each of their elements gives 15. (Hint: what is the maximum possible sum of a subset of \(A\text{?}\) What is the minimum? Use these numbers to get an upper bound on the number of pigeonholes.) Solution.
The minimum sum is 0 (for the empty set) and the maximum sum is \(7+8+9+10+11+12= 57\text{.}\) We place each set into a "pigeonhole" labeled by the sum of its elements. A set of size 6 has \(2^6=64\) different subsets. So two sets must be placed in the same pigeonhole.