Courses
Courses for Kids
Free study material
Offline Centres
More
Store Icon
Store

What is pigeonhole principle?

seo-qna
Last updated date: 13th Jul 2024
Total views: 346.8k
Views today: 3.46k
Answer
VerifiedVerified
346.8k+ views
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.

Complete step-by-step answer:
 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.

Note: There is also an alternative formulation of the pigeonhole principle, that formulation goes as follows,
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.