Discovery
The pigeonhole principle is a simple but powerful concept that is used in tackling combinatorial mathematics problems in a systematic manner. In simple terms, the principle states that if some objects need to be placed in boxes that are lesser in number than the objects, then at least one box will have two objects. The concept was formulated in 1834 by a German mathematician named Peter Gustav Lejeune Dirichlet. In his original publication, Dirichlet used a German word that meant drawer in English (Brualdi, 2008). The word soon changed to pigeonhole that is an open space on a wall for keeping mail. However, for easy understanding of the principle especially in regions where English was a foreign language, pigeonhole was taken to mean a structure where pigeons are kept.
Theory
The pigeonhole principle states that if n + 1 pigeons are placed into n pigeonholes, then at least one pigeonhole will contain more than one pigeon (Li, 2005). From this statement, the strong form of the pigeonhole principle can be obtained.
Let q1, q2, q3..qn be positive integers
If q1+ q2 + q3++ qn - n+1 pigeons are put into n pigeonholes
Then the first pigeonhole has at least q1 pigeons, the second pigeonhole has at least q2 pigeons, the third pigeonhole has at least q3 pigeons, and the nth pigeonhole has at least qn pigeons.
The induction method can then be used to prove the principle. This involves assuming the opposite and proving it wrong.
We can assume that the ith pigeonhole has at most qi - 1 pigeons where i = 1, 2, 3..n
Then the number of pigeons in the n pigeonholes will be:
(q1 - 1) + (q2 - 2) + (q3 - 3) + (qn - n) = q1 + q2 + q3 +qn - n
This is a contradiction because it is less than the number of pigeons
Then q1+ q2 + q3++ qn - n+1 = 2n - n + 1 = n + 1
The simple form is usually used in cases where q1 = q2 = q3 = ..qn = m
If n(m - 1) + 1 pigeons are placed into n pigeonholes, at least two pigeons will be placed in the same pigeonhole.
Then q1+q2+q3+qnn > m- 1, this means that one of the positive integers must be greater than or equal to m.
Applications
The pigeonhole principle can be used in many fields including computer science, and mathematics. In computer science, the pigeonhole principle is in the hash tables and lossless compression algorithms. A hash table uses a key such as the name of a person to find the value associate with the key such as the address of the person. The hash table transforms the key into a number that is used to index directly into an array the location of the corresponding value. The pigeonhole principle is used to show that collision is inevitable in hashing. In a lossless compression algorithm, the pigeonhole principle is used to show that the algorithm cannot reduce the sizes of all files. For every file the algorithm reduces, there must be another file that the algorithm makes bigger. In mathematics, the principle can be used in probability and statistics, and geometry (Shi, 2009). For example, it can be used to show how many people must be selected from a group of married people to ensure that at least one married couple has been selected. In geometry, it can be used to find any two points in a given shape, such that the distance between the two points does not exceed a certain value.
References
Brualdi, R. A. (2008). Introductory combinatorics (5th ed.). Indianapolis, IN, United States: Pearson Education (US).
Li, K.-Y. (2005). Pigeonhole Principle. Mathematical Excalibor, 5(23),
Shi, P. (2009). The pigeonhole principle simple but immensely powerful. Retrieved from http://www.mit.edu/pengshi/math149/talk_pigeonhole.pdf
