The Pigeonhole Principle

The “pigeon” version of the pigeonhole principle states that if there are h holes and p pigeons in the holes and h < p, then there must be at least two pigeons in one hole. That is, if there is a mapping between two finite sets of unequal size, then at least one element in the smaller set must be paired with more than one element in the larger set.

The extended pigeonhole principle says that if p > nh for some integer n, then at least one hole will contain n + 1 pigeons. Informally, the most even distribution of pigeons assures this result and larger populations within a hole are possible (note that some specific holes may be empty—we are only making a claim about the existence of a more crowded hole).

For practice applying this principle in different situations, see Pigeonhole Principle, The Pigeon Hole Principle, and The Pigeon Hole Principle 2.

Making Mathematics Home |
Mathematics Projects | Students | Teachers |
Mentors | Parents | Hard Math Café |