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.

## Comments

Sort by:

TopNewestThe 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

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)

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?

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

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.

Log in to reply