Courses
Courses for Kids
Free study material
Offline Centres
More
Store

# What is pigeonhole principle?

Last updated date: 13th Jul 2024
Total views: 346.8k
Views today: 3.46k
Hint: Pigeonhole principle is a statement that says if $n$ items are put into the $m$ numbers of containers and the value of $n$ is greater than $m$ , then one of the containers must contain more than one item. The pigeonhole principle was given in the year $1834$ by one Peter Gustav Dirichlet . The principle has very obvious but very important implications.
The pigeonhole principle is based on the statement that if $10$ pigeons are present in a pigeon box with nine holes, now since the number $10$ is more than $9$ this means that at least one of the pigeonholes must have more than one pigeon. In mathematical terms this can be written as,
For two given natural numbers $k$ and $m$ , if
$n = km + 1$ Objects are distributed among $m$ sets, then the pigeonhole principle says in simple terms that at least one of the objects contains at least $k + 1$ objects. Thus this is the mathematical expression of the pigeonhole principle. The numbers $k$ in the question of $10$ pigeons is $1$ , while the number $m$ present here is $9$ , which means if we have distribute the,
$km + 1$ which is 10 objects in $9$ sets one of the sets will contain at least $k + 1$ objects i.e. $2$ objects, which was in fact our initial statements.
In $n$ objects are distributed over $m$ places, and if $n < m$ then some place in this situation will receive no object, i.e. a placeholder in that condition is sure to remain empty.