Pigeonhole Principle

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

Proof: The proof is by contradiction. Suppose there are no pigeonholes that contain at least k+1 k+1 pigeons, so each pigeonhole must contain at most k k pigeons. Since there are n n pigeonholes, there are at most k×n k \times n pigeons in total. This contradicts the fact that there are P>k×n 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 n=4). The cards are our pigeons. We want at least 3 cards in a suit, so k+1=3 k+1 = 3 , implying k=2k=2. Hence, if we have 9=2×4+1 9 = 2 \times 4 +1, then by the pigeonhole principle, since there are 4 4 suits (pigeonhole), there must be a suit which contains 3=2+1 3 = 2+1 cards.

We are not yet done, as we want to know the minimum number. How do we know that 8 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 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 13 \frac {1}{3} apart.

Solution: If we have 2 points in an equilateral triangle of side length A A, then these 2 points have distance at most A 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 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 13 \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
7 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

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

Siam Habib - 7 years, 1 month ago

Log in to reply

Thanks, I've edited it in.

Calvin Lin Staff - 7 years, 1 month ago

Log in to reply

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

Varun Singla - 7 years ago

Log in to reply

@Varun Singla 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 pp and number of holes is nn and for some kNk \in \mathbb{N} and p<nkp<nk, then there must be more than kk 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 - 7 years ago

Log in to reply

@Siam Habib You have the book .

Rajdeep Dhingra - 6 years, 3 months ago

Log in to reply

Prove that in a triangle of side 1 if 5 points are chosen then there atleast two points whose distance is at most 1/2

Aastha Kudiya - 1 year, 8 months ago

Log in to reply

What have you tried? That's very similar to worked example 2 above.

Calvin Lin Staff - 1 year, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...