# Pigeonhole Principle

Suppose $$P, k$$ and $$n$$ are integers such that $$P > k \times n$$. If $$P$$ pigeons are placed into $$n$$ pigeonholes, then the pigeonhole principle states there must be (at least) one pigeonhole which contains at least $$k+1$$ pigeons.

Proof: The proof is by contradiction. Suppose there are no pigeonholes that contain at least $$k+1$$ pigeons, so each pigeonhole must contain at most $$k$$ pigeons. Since there are $$n$$ pigeonholes, there are at most $$k \times n$$ pigeons in total. This contradicts the fact that there are $$P > k \times n$$ pigeons in total. $$_\square$$

The power of the pigeonhole principle comes from choosing the correct pigeons and pigeonholes for the problem.

## Worked Examples

### 1. In a standard deck of 52 cards, what is the minimum number of cards you need to pick up, in order to guarantee that there is a suit with at least 3 cards?

Solution: A standard deck has four suits, which forms our pigeonhole (so $$n=4$$). The cards are our pigeons. We want at least 3 cards in a suit, so $$k+1 = 3$$, implying $$k=2$$. Hence, if we have $$9 = 2 \times 4 +1$$, then by the pigeonhole principle, since there are $$4$$ suits (pigeonhole), there must be a suit which contains $$3 = 2+1$$ cards.

We are not yet done, as we want to know the minimum number. How do we know that $$8$$ cards are not sufficient to meet the requirements? Let's provide an example. The cards 2, 3 of clubs, 2, 3 of diamonds, 2, 3 of hearts, 2, 3 of spades are a set of $$8$$ cards which do not have a suit with at least 3 cards. Thus, the minimum number is 9.

### 2. There are 10 points placed within an equilateral triangle of side length 1. Show that we can find 2 points with distance at most $$\frac {1}{3}$$ apart.

Solution: If we have 2 points in an equilateral triangle of side length $$A$$, then these 2 points have distance at most $$A$$ apart. (Why? Convince yourself that if we have 2 points in ANY triangle, then the distance between these 2 points is at most the length of the longest side.) We are unable to apply the pigeonhole principle directly.

Cut up the equilateral triangle as follows:

Equilateral Triangle

Let our pigeons be the 10 points, and the pigeonholes be the 9 smaller equilateral triangles. By the pigeonhole principle, there must be 1 smaller equilateral triangle with at least 2 points in it. Then, these 2 points are at distance at most $$\frac {1}{3}$$ apart by our initial observation.

### 3. There are 6 people in a random Facebook group. Show that there are either 3 people who are all friends, or 3 people who are all strangers. Note: Remember that on Facebook, person A is friends with person B, then person B is friends with person A. Also, you are either a friend with, or a stranger to, another person.

Solution: We are unable to apply the Pigeonhole Principle directly. Consider any person A. Consider the other 5 people, who will be our pigeons. He is either friends or strangers (pigeonholes) with them. By the pigeonhole principle, there are (at least) 3 that he is either friends with, or strangers with. Let us assume that there are (at least) 3 whom he is friends with (otherwise interchange friends with strangers in the following discussion). Consider the group that are friends with A. If two of them are friends with each other, then the two of them along with A form a set of 3 people who are all friends. Otherwise, if none of them are friends with each other, then any three of them form a set of 3 people who are all strangers.

Note by Calvin Lin
4 years, 7 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

I'm sorry. But, there is no image in the solution to question $$2$$.

- 4 years, 5 months ago

Thanks, I've edited it in.

Staff - 4 years, 5 months ago

My friend can you please simplify this principle more. I want to understand it but i didnt get it fully.

- 4 years, 4 months ago

Think that you have some pigeons. And you made their houses with some cardboard boxes. But, the number of houses or pigeon holes is less than that of the pigeons (Maybe you were short of cardboard). Now, you decided to stuff all the pigeons into their houses. And no matter how you do this there always will be a pigeon hole that contains more than one pigeon. So, the pigeon hole principle just states that if you have more pigeons than pigeon holes it is impossible for you to provide each pigeon with a distinct home. This is the pigeon hole principle in its simplest form. It is a simple piece of logic but a can be used a great tool in problem solving if you can find the right pigeons with the right holes.

But this is not the same principle that is stated in the note but simply a easier variation. The version on the note (which is also known as the intermediate pigeon hole) states that if the number of pigeons is $$p$$ and number of holes is $$n$$ and for some $$k \in \mathbb{N}$$ and $$p<nk$$, then there must be more than $$k$$ pigeons in at least one hole. I advice you to read the note again. Because, I first learnt the pigeon hole theorem from the brilliant blog and to this day it is one of my most favorite techniques.

I hope that I was helpful.

If not read the chapter on Pigeon hole Principle from the book the "The Art and Craft of Problem Solving".

[ You might want to check that book out!]

- 4 years, 4 months ago

You have the book .

- 3 years, 7 months ago