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.