pigeonhole principle


For any natural numberMathworldPlanetmath n, there does not exist a bijection between n and a proper subsetMathworldPlanetmathPlanetmath of n.

The name of the theorem is based upon the observation that pigeons will not occupy a pigeonhole that already contains a pigeon, so there is no way to fit n pigeons in fewer than n pigeonholes.

Title pigeonhole principleMathworldPlanetmath
Canonical name PigeonholePrinciple
Date of creation 2013-03-22 11:53:32
Last modified on 2013-03-22 11:53:32
Owner djao (24)
Last modified by djao (24)
Numerical id 11
Author djao (24)
Entry type Theorem
Classification msc 03E05
Classification msc 03B22
Classification msc 03-01
Classification msc 03-00
Synonym box principle
Synonym Dirichlet principle