$$\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}}$$

10.1: The Pigeonhole Principle

• • Joy Morris
• Professor (Mathematics) at University of Lethbridge
$$\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}}$$

The Pigeonhole Principle is a technique that you can apply when you are faced with items chosen from a number of different categories of items, and you want to know whether or not some of them must come from the same category, without looking at all of the items.

Example $$\PageIndex{1}$$

Suppose I will be teaching an independent study course in graph theory to two students next semester, and I want to use Bondy & Murty’s “Graph Theory” textbook. It has been issued in two editions, and I don’t care which edition we use, but I want both students to have the same edition.

I find a website on which someone has posted that they have three copies of the text for sale, but they don’t say which editions they are. Without any more information, I know that if I buy these texts, I will have suitable texts for my students.

The reasoning is straightforward. The first book could be edition $$1$$ or edition $$2$$. If the second text is the same as the first, then I have what I need, so the only possible problem is if the first two books consist of one copy of edition $$1$$, and one copy of edition $$2$$. But then the third book must match one or the other of the first two, since there are only two editions, so I will have two copies of one or the other of the editions.

This idea can be generalised in several ways. We’ll look at the most straightforward generalisation first.

Proposition $$\PageIndex{1}$$: Pigeonhole Principle

If there are $$n$$ items that fall into $$m$$ different categories and $$n > m$$, then at least two of the items must fall into the same category.

Proof

Amongst the first $$m$$ items, either two of the items are from the same category (so we are done), or there is exactly one item from each of the $$m$$ categories. Since $$n > m$$, there is at least one more item. This item must fall into the same category as one of the previous items since every category already has an item.

The name of this principle comes from the idea that it can be stated with the categories being a row of holes, and the items being pigeons who are assigned to these holes.

In Example 10.1.1, the categories were the editions, and the items were the textbooks.

Example 10.1.1 was a very direct and straightforward application of the Pigeonhole Principle. The Principle can also apply in much more subtle and surprising ways.

Example $$\PageIndex{2}$$

Maria makes a bet with Juan. He must buy her at least one chocolate bar every day for the next $$60$$ days. If, at the end of that time, she cannot point out a span of consecutive days in which the number of chocolate bars he gave her was precisely $$19$$, then she will pay for all of the chocolate bars and give them back to him. If she can find such a span, then she gets to keep the chocolate bars. To limit the size of the bet, they agree in advance that Juan will not buy more than $$100$$ chocolate bars in total.

Is there a way for Juan to win this bet?

Solution

The answer is no. For $$1 ≤ i ≤ 60$$, let $$a_i$$ represent the number of chocolate bars that Juan has bought for Maria by the end of day $$i$$. Then $$1 ≤ a_1 < a_2 < . . . < a_{60} ≤ 100$$. Maria is hoping that for some $$i < j$$, she will be able to find that $$a_i + 19 = a_j$$. We therefore also need to consider the values $$a_1 + 19 < a_2 + 19 < . . . < a_{60} + 19$$. By the bounds on $$a_1$$ and $$a_{60}$$, we have $$a_1 + 19 ≥ 20$$, and $$a_{60} + 19 ≤ 119$$. Thus, the values $$a_1, . . . , a_{60}, a_1 + 19, . . . , a_{60} + 19$$ are $$120$$ numbers all of which lie between $$1$$ and $$119$$.

By the Pigeonhole Principle, at least two of these numbers must be equal, but we know that the $$a_i$$s are strictly increasing (as are the $$a_i + 19$$s), so there must exist some $$i < j$$ such that $$a_i + 19 = a_j$$. Maria must point to the span of days from the start of day $$i + 1$$ to the end of day $$j$$ since in this span Juan gave her $$19$$ chocolate bars.

In fact, Juan could not win a bet of this nature that lasted more than $$56$$ days, but proving this requires more detailed analysis specific to the numbers involved, and is not really relevant to this course.

Here is another example that would be hard to prove if you didn’t know the Pigeonhole Principle.

Example $$\PageIndex{3}$$

Fix $$n$$, and colour each point of the plane with one of $$n$$ colours. Prove that there exists a rectangle whose four corners are the same colour.

Solution

Take a grid of points with $$n + 1$$ rows and $$n \binom{n+1}{2} + 1$$ columns. We claim that this grid will contain such a rectangle

Since n colours have been used, and there are $$n+1$$ points in each column, by the Pigeonhole Principle each column must contain at least two grid points that are the same colour.

In any column, there are $$\binom{n+1}{2}$$ possible locations in which a pair of points of the same colour could appear. Thus there are at most $$\binom{n+1}{2}$$ ways to position two points of colour $$1$$ in a column so that the points do not occupy the same two locations in more than one of these columns. The same is true for each of the $$n$$ colours. Therefore, we can create a maximum of $$n \binom{n+1}{2}$$ columns, each having two points of some colour, in such a way as to avoid having the same colour occupy the same two locations in more than one of the columns. Since we have $$n \binom{n+1}{2} + 1$$ columns, there must exist some pair of columns such that the same colour does occupy the same two locations in both of the columns. These four points form a rectangle whose corners all have the same colour.

So far we have only thought about guaranteeing that there are at least two items in some category. Sometimes we might want to know that there are at least $$k$$ items in some category, where $$k > 2$$. There is a generalisation of the Pigeonhole Principle that applies to such situations.

Proposition $$\PageIndex{2}$$: Generalised Pigeonhole Principle

Given $$n$$ items that fall into $$m$$ different categories, if $$n > km$$ for some positive integer $$k$$, then at least $$k + 1$$ of the items must fall into the same category.

Proof

Amongst the first $$km$$ items, either $$k + 1$$ of the items are from the same category (so we are done), or there are exactly $$k$$ items from each of the $$m$$ categories. Since $$n > km$$, there is at least one more item. This item must fall into the same category as one of the previous items. Since every category already has $$k$$ items, this means that there will be $$k + 1$$ items in this category.

Notice that the Pigeonhole Principle is a special case of the Generalised Pigeonhole Principle, obtained by taking $$k = 1$$.

Example $$\PageIndex{4}$$

The population of West Lethbridge in the $$2014$$ census was $$35$$, $$377$$. Show that at least $$97$$ residents of West Lethbridge share a birthday. If you live in West Lethbridge, how many people can you be sure have the same birthday as you?

Solution

For the first part of this question, we apply the generalised pigeonhole principle, with $$m = 366$$ (for the $$366$$ days of the year, counting February $$29$$ since it is just as legitimate a birthday as any other despite being more uncommon), $$k = 96$$, and $$n = 35, 377$$. We have

$$n = 35, 377 > km = 96 · 366 = 35, 136,$$

so the Generalised Pigeonhole Principle tells us that at least $$k + 1 = 97$$ people must share a birthday.

For the second part of the question, the answer is $$0$$. There is no reason why every single other person in West Lethbridge might not have their birthday on the day after yours (although that particular possibility is quite unlikely). There is certainly no guarantee that any of them has the same birthday as yours.

Notice that although we have found in the above example that some group of at least $$97$$ people in West Lethbridge must have the same birthday, we have no idea of which $$97$$ people are involved, or of what the joint birthday is. This is rather remarkable, but is an example of a type of proof that is quite common in advanced mathematics. Such proofs are referred to as “non-constructive,” since they prove that something exists, without giving you any idea of how to find (or construct) such a thing.

The proof of the following theorem involves a more subtle application of the Generalised Pigeonhole Principle.

Theorem $$\PageIndex{1}$$: Erdös-Szekeres Theorem

For every pair of integers $$a$$, $$b ≥ 1$$, if $$S$$ is a sequence of $$ab + 1$$ distinct real numbers, then there is either an increasing subsequence of length $$a + 1$$ or a decreasing subsequence of length $$b + 1$$ in $$S$$.

Proof

Define a function f that maps each element of $$S$$ to the length of the longest increasing subsequence that begins with that element.

If there exists some $$s ∈ S$$ such that $$f(s) ≥ a + 1$$, then we are done. So we may assume that $$f(s) ≤ a$$ for every $$s ∈ S$$. Since there is always an increasing sequence of length at least $$1$$ starting at any element of $$S$$, we in fact have $$1 ≤ f(s) ≤ a$$ for every $$s ∈ S$$, so there are a possible values for the outputs of $$f$$. Since $$|S| = ab + 1$$, and $$ab + 1 > ab$$, the Generalised Pigeonhole Principle tells us that at least $$b+ 1$$ elements of $$S$$ must have the same output under the function $$f$$.

We claim that if $$x$$ is before $$y$$ in $$S$$ and $$f(x) = f(y)$$, then $$x > y$$. By assumption, $$x \neq y$$ (all values of $$S$$ are distinct), so the only other possibility is $$x < y$$. If $$x < y$$, then taking $$x$$ followed by an increasing subsequence of length $$f(y)$$ that starts at $$y$$, would give an increasing subsequence of length $$f(y) + 1$$ that starts at $$x$$, contradicting $$f(x) = f(y)$$. This contradiction shows that $$x < y$$ is not possible, so $$x > y$$, as claimed.

Let $$s_1, s_2, . . . , s_{b+1}$$ be elements of $$S$$ that have the same output under $$f$$, and appear in this order. Then by the claim we proved in the previous paragraph, $$s_1 > s_2 > . . . > s_{n+1}$$, which is a decreasing subsequence of length $$b + 1$$.

In fact, $$ab + 1$$ is the smallest possible length for $$S$$ that guarantees this property. For any $$a$$, $$b$$, there is a sequence of length $$ab$$ in which the longest increasing sequence has length $$a$$ and the longest decreasing subsequence has length $$b$$. One such sequence is

$b, b − 1, . . . , 1; 2b, 2b − 1, . . . , b + 1; . . . ; ab, ab − 1, . . . ,(a − 1)b + 1$

Any increasing subsequence can only have one entry from each of the $$a$$ subsequences of length $$b$$ that are separated by semicolons, so can only have length $$a$$. Any decreasing subsequence must be entirely contained within one of the subsequences of length $$b$$ that are separated by semicolons, so can only have length $$b$$.

Proposition $$\PageIndex{3}$$: Even More Generalised Pigeonhole Theorem

Let $$n_1, n_2, . . . , n_m$$ be positive integers. Given at least

$n_1 + n_2 + . . . + n_m − m + 1$

items that fall into $$m$$ categories, there must be some $$1 ≤ i ≤ m$$ such that at least $$n_i$$ items fall into the $$i^{\text{th}}$$ category.

Proof

Amongst the first

$$n_1 + n_2 + . . . + n_m − m$$

items, either there is some $$1 ≤ i ≤ m$$ such that at least ni of the items fall into the $$i^{\text{th}}$$ category, or there are precisely $$n_i − 1$$ objects in the ith category, for every $$1 ≤ i ≤ m$$. Since there is at least one more item, this item must fall into the $$i^{\text{th}}$$ category for some $$1 ≤ i ≤ m$$, which means that there will be $$n_i$$ items in this category.

Notice that the Generalised Pigeonhole Principle is a special case of the “Even more generalised pigeonhole principle,” obtained by taking

$n_1 = n_2 = . . . = n_m = k.$

Example $$\PageIndex{5}$$

Suppose Ali owes Tomas $$10$$, and wants to give him a number of identical pieces of currency to pay her debt. Her bank only gives out currency in loonies, twonies, five-dollar bills, or ten-dollar bills, and does not take requests for specific kinds of currency. How much money must Ali request from the teller, if she wants to be sure to have $$10$$ in identical pieces of currency with which to pay Tomas?

Solution

If Ali gets any $$10$$ bills she can give one of those to Tomas and is done. If she gets at least two $$5$$ bills, she is done. If she gets at least five twonies, she is done, and if she gets at least $$10$$ loonies she is done. So the most money she can get without being able to give Tomas his $$10$$ in a single type of currency, is $$9$$ loonies, $$4$$ twonies, and a $$5$$ bill, for a total of $$22$$. Therefore, if Ali asks for $$23$$, she is guaranteed to be able to pay Tomas in a single type of currency.

Although the above example does not directly use the “Even more generalised pigeonhole principle” because it asks for the value of the currency Ali needs to request rather than the number of items she must request, it uses the same ideas and should be helpful in understanding the concept.

Exercise $$\PageIndex{1}$$

1) Show that in any positioning of $$17$$ rooks on an $$8$$-by-$$8$$ chessboard, there must be at least three rooks none of which threaten each other (i.e. no two of which lie in the same row or column).

2) Sixteen people must sit in a row of eighteen chairs. Prove that somewhere in the row there must be six adjacent chairs all occupied.

3) An artist has produced a large work of art to be carried in a parade. Part of the concept is that it must be carried by people of roughly the same size (i.e., either all adults, or all children). The artist has left it to the last minute to find people to carry this, and is in a bit of a panic. He doesn’t know if he will be able to assemble enough of either adults or children to carry the piece, so he decides to ask everyone he sees, until he has enough volunteers. It takes $$15$$ adults to carry the piece, or $$23$$ children. If everyone approached agrees to help, how many people does the artist need to approach before he is sure to have enough people to carry his art in the parade?

4) Let $$n$$ be odd, let $$a$$ be even, and let $$\pi$$ : $$\{1, . . . , n\} → \{1, . . . , n\}$$ be a permutation. Prove that the product

$$(a + 1 − \pi (1))(a + 2 − \pi (2))· · ·(a + n − \pi (n))$$

is even. Is the same conclusion necessarily true if $$n$$ is even or if $$a$$ is odd? Give a proof or a counterexample in each case.

5) Let $$n ≥ 1$$, let $$x$$ be a positive integer, and let $$S$$ be a subset of cardinality $$n + 1$$ from $$\{x, x^2 , . . . , x^{2n}\}$$. Prove that there exist two numbers in $$S$$ whose product is $$x^{2n+1}$$.

6) Show that in every set of $$n + 1$$ distinct integers, there exist two elements $$a$$ and $$b$$ such that $$a − b$$ is divisible by $$n$$.

7) A drawer contains socks of $$8$$ different colours. How many socks must you pull out of the drawer to be certain that you have two of the same colour?

8) There are $$15$$ students in a Combinatorics class. Explain how you know that two of them have their birthday in the same month.

9) A pizza restaurant has $$8$$ different toppings. Every day in October, they will put a $$2$$-topping pizza on sale. Prove that the same pizza will be on sale on two different days.

10) 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 each of them is at most $$100$$, how many different possible sums are there?]

11) Consider any set of $$5$$ points in the plane that have integer coordinates. Prove that there is some pair from these $$5$$ points such that the midpoint of the line segment joining this pair of points also has integer coordinates. Give an example of $$4$$ points in the plane that do not have this property, and list all of the midpoints as evidence