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 or more pigeons into 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 pigeons. This proves the Pigeon Hole Principle, using the method of proof by contradiction.
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\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:
Log in to reply
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?
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)
Hey Tang. Could you please go through one of my latest discussion?
The Pigeon Hole Principle or the Dirichlet Box Principle is one the fundamental theorems of Combinatorics and is absolutely great.
I think there are many versions/theorems under PHP . Can you explain them ?
Log in to reply
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.
Log in to reply
Alright . Never mind.
I dont get it?? what is there to be amazed?