Pigeon Hole Principle

The Pigeon Hole Principle was given by Peter Gustav Lejeune Dirichlet. People who have never heard of the Pigeon Hole Principle may think that it is a joke!

Statement: Here's what the statement says: If we must put $N+1$ or more pigeons into $N$ pigeon holes, then some pigeon hole must contain two or more pigeons.

Notice the vagueness of the proposition "some pigeon hole must contain . . . ", "two or more . . . ". This is, in fact, a distinguishing feature of the Pigeon Hole Principle, which sometimes allow us to draw quite unexpected conclusions, even when we don't seem to have enough information.

Proof: The proof of this principle is quite simple, and uses only a trivial count of the pigeons in their pigeon holes. Suppose no more than one pigeon were in each hole. then there would be no more than N pigeons altogether, which contradicts the assumption that we have $N + 1$ pigeons. This proves the Pigeon Hole Principle, using the method of proof by contradiction.

#Combinatorics #PigeonholePrinciple #TorqueGroup #Counting

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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}$

Comments

The PHP is great when you want to prove that "something exists," or "there is something." For example, here's a good beginner-level PHP problem:

There are $1000000$ people at a huge party. Prove that there exist $2$ people who know the same number of people at the party. (Assume that "knowing" is a symmetric relationship; that is, A knows B if and only if B knows A. Also assume that knowing yourself doesn't count.)

Michael Tang - 7 years, 6 months ago

Could we think about problems (like the one above) as graphs with each pigeon as a vertex and the number of connections as the edges?

Lemma Theorem - 7 years, 6 months ago

very childish question........since a human can know 1.2,3,............................999999...so there are 999999 pigeon holes...(assuming each person in the party to be pigeon)..now let us assume the no two pigeons holes contain more than one pigeon..,but this a contradiction as if it so then the number of people in the party will be equal or less than 999999..but we have 1000000 people..hence there exist 2 people who know the same number of people at the party..(proved)

Suvadip Sana - 7 years, 6 months ago

Hey Tang. Could you please go through one of my latest discussion?

Priyansh Sangule - 7 years, 6 months ago

The Pigeon Hole Principle or the Dirichlet Box Principle is one the fundamental theorems of Combinatorics and is absolutely great.

Soham Dibyachintan - 7 years, 6 months ago

I think there are many versions/theorems under PHP . Can you explain them ?

Priyansh Sangule - 7 years, 6 months ago

Can you be more specific as to which versions are you talking about? By the way, I was trying to be totally basic, not trying to go much in deep.

Akshat Jain - 7 years, 6 months ago

Alright . Never mind.

Priyansh Sangule - 7 years, 6 months ago

I dont get it?? what is there to be amazed?

Saravanan Rajenderan - 7 years, 5 months ago

Math	Appears 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}$