Jan 29, 2021
1 mins read
The pigeonhole principle is a simple, yet beautiful and useful idea. Given a set A of pigeons and a set B of pigeonholes, if all the pigeons fly into a pigeonhole and there are more pigeons than holes, then one of the pigeonholes has to contain more than one pigeon.
The pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.
The first formalization of the pigeonhole concept is believed to have been made by Dirichlet (1805–1859) as what he called Schubfachprinzip or the “drawer/shelf principle”. As Dirichlet published works in both German and French, he would alternate between calling the principle Schubfach and tiroir, which both translate to drawer. However, as Dirichlet’s father was a postmaster it is believed that the type of drawer he was referring to might have best been translated to English as pigeon-hole, such as those commonly used for storing and sorting mail. The first appearance of the term “pigeonhole principle” was used by mathematician Raphael M. …
Originally published August 23rd, 2019.