 The inspiration for the name of the principle: pigeons in holes. Here n = 7 and m = 9. The pigeonhole principle, also known as Dirichlet's box principle, states that if n pigeons are put into m pigeonholes, and if n > m, then at least one pigeonhole must contain more than one pigeon. Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force you to reuse one of the holes. Image File history File links Download high resolution version (1246x1010, 190 KB)Pigeons in holes attempting to demonstrate the Pigeonhole principle. ...
Image File history File links Download high resolution version (1246x1010, 190 KB)Pigeons in holes attempting to demonstrate the Pigeonhole principle. ...
Peter Gustav Lejeune Dirichlet. ...
Literally, a pigeonhole is a small hole in a loft, the nesting-place of a pigeon. ...
Pigeon redirects here. ...
The pigeonhole principle is an example of a counting argument which can be applied to many formal problems, including ones involving infinite sets that cannot be put into one-to-one correspondence. In Diophantine approximation the quantitative application of the principle to the existence of integer solutions of a system of linear equations goes under the name of Siegel's lemma. Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ...
In set theory, an infinite set is a set that is not a finite set. ...
In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ...
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers. ...
In mathematics and linear algebra, a system of linear equations is a set of linear equations such as 3x1 + 2x2 − x3 = 1 2x1 − 2x2 + 4x3 = −2 −x1 + ½x2 − x3 = 0. ...
Carl Ludwig Siegel (December 31, 1896 – April 4, 1981) was a German mathematician specialising in number theory. ...
The first statement of the principle is believed to have been made by Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle"). In some languages (for example, Russian) this principle is therefore called the Dirichlet principle (not to be confused with the minimum principle for harmonic functions of the same name). Peter Gustav Lejeune Dirichlet. ...
1834 was a common year starting on Wednesday (see link for calendar). ...
In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function f : U → R (where U is an open subset of Rn) which satisfies Laplaces equation, i. ...
Examples An easy example of the pigeonhole principle involves the situation when there are five people who want to play softball, but only four teams. This would not be a problem except that each of the five refuses to play on a team with any of the other 4. To prove that there is no way for all five people to play softball, the pigeonhole principle says that it is impossible to divide five people among four teams without putting two of the people on the same team. Since they refuse to play on the same team, at most four of the people will be able to play.
Although the pigeonhole principle may seem to be a trivial observation, it can be used to demonstrate possibly unexpected results. For example, there must be at least two people in London with the same number of hairs on their heads. Demonstration: a typical head of hair has around 150,000 hairs. It is reasonable to assume that no one has more than 1,000,000 hairs on their head. There are more than 1,000,000 people in London. If we assign a pigeonhole for each number of hairs on a head, and assign people to the pigeonhole with their number of hairs on it, there must be at least two people with the same number of hairs on their heads.
The pigeonhole principle often arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. No hashing algorithm, no matter how clever, can avoid these collisions. This principle also proves that there cannot be a lossless compression algorithm that will compress any file by a certain amount. If it could then two files would be compressed to the same smaller file and restoring them would be ambiguous. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...
Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. ...
Several additional examples are given by Grimaldi (see References).
Generalizations of the pigeonhole principle A generalized version of this principle states that, if n discrete objects are to be allocated to m containers, then at least one container must hold no fewer than  objects, where  is the ceiling function, denoting the smallest integer larger than or equal to x. In mathematics, the floor function is the function defined as follows: for a real number x, floor(x) is the largest integer less than or equal to x. ...
A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more than one pigeon with probability
 where m(n) is a falling factorial. For n = 0 and for n = 1 (and m > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For n > m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (n ≤ m), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. This problem is treated at much greater length at birthday paradox. In mathematics, the Pochhammer symbol is used in the theory of special functions to represent the rising factorial or upper factorial and, confusingly, is used in combinatorics to represent the falling factorial or lower factorial The empty product (x)0 is defined to be 1 in both cases. ...
The birthday paradox states that if there are 23 or more people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. ...
Application examples - If there are n persons who can arbitrarily shake hands with one another, there is always a pair of persons who shake the same number of hands: one can shake 0 to n − 1 number of hands, if he doesn't shake any hand, he'll be excluded from the group. Suppose all of the n persons shake hands at least once, so as every person in will shake from 1 to n − 1 hands. There are n persons and just n − 1 hands shaken. Thus, because of pigeonhole, there must be two people shaking the same number of hands.
References - Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
See also In proving results in combinatorics several useful combinatorial rules or combinatorial principles are used. ...
In linguistics, cardinal numbers is the name given to number words that are used for quantity (one, two, three), as opposed to ordinal numbers, words that are used for order (first, second, third). ...
In mathematics, the multinomial formula is an expression of a power of a sum in terms of powers of the addends. ...
In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ...
The birthday paradox states that if there are 23 or more people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. ...
External links |
Feeds |
Contact