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:

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.

## Comments

Sort by:

TopNewestI'm sorry. But, there

is no imagein the solution to question \(2\). – Siam Habib · 3 years agoLog in to reply

– Calvin Lin Staff · 3 years ago

Thanks, I've edited it in.Log in to reply

– Varun Singla · 2 years, 11 months ago

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

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!] – Siam Habib · 2 years, 11 months ago

Log in to reply

– Rajdeep Dhingra · 2 years, 2 months ago

You have the book .Log in to reply