×

# 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.

Note by Akshat Jain
3 years, 1 month ago

Sort by:

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.)

· 3 years, 1 month 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) · 3 years, 1 month 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? · 3 years, 1 month ago

Hey Tang. Could you please go through one of my latest discussion? · 3 years, 1 month ago

The Pigeon Hole Principle or the Dirichlet Box Principle is one the fundamental theorems of Combinatorics and is absolutely great. · 3 years, 1 month ago

I dont get it?? what is there to be amazed? · 3 years ago

I think there are many versions/theorems under PHP . Can you explain them ? · 3 years, 1 month 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. · 3 years, 1 month ago