Pigeonhole principle

In mathematics, the pigeonhole principle is (English pigeonhole principle, therefore Pigeonhole ) a simple, intuitive and often useful way to make certain statements on a finite set. The principle is often used in discrete mathematics.

• 2.1 Example of tightening

The principle

The principle can be formulated informally as follows:

The name comes from a pictorial presentation of this process: If you have a certain number of drawers, and you put as subjects are present, then land in any drawer at least two of these objects more objects in the trays.

It probably goes back to Dirichlet who has applied it in 1834. In many languages ​​(Bulgarian, Czech, Danish, Icelandic, Kazakh, Latvian, Polish, Romanian, Russian, etc ), it is therefore also called " Dirichlet's Principle ".

Evidence

The proof of this principle is almost trivial and can be done indirectly, for example: If the principle is wrong, then lands in each drawer at most one object. Thus there are at most as many objects as drawers. This stands in contradiction to the assumption that there are more objects than drawers.

Examples

Despite its simplicity, you can meet interesting statements to the pigeonhole principle, for example, that there are at least two people are in Munich, have exactly the same number of hairs on your head. Proof: You share all the inhabitants of Munich by number of hairs in " drawers " one. Typically, the person has about 100,000 to 200,000, but certainly less than 1 million hairs, so that there is a maximum of one million drawers ( 0-999999 ). Since there are about 1.3 million inhabitants in Munich, has more inhabitants than drawers so end up in at least one drawer, two or more people. These have by definition of the drawers the same number of hairs on your head.

Another, more complex example, in which the pigeonhole principle used is the following: If one chooses twelve pairwise distinct two-digit numbers, so there are two of them whose difference is a two-digit number whose digits are both the same. Proof: The representation of a number that is a multiple of eleven, consists of two identical digits. Now you wonder which residues may result in the division of a number by 11 (see residue class ). It is found that the numbers 0 to 10, the possible residues. If two numbers have the same remainder, their difference is a multiple of 11 So there are 11 " drawers ", but 12 two-digit numbers that are distributed to it. After the pigeonhole principle are located in a compartment that is two numbers; As explained above, their difference is a multiple of 11, that has the desired shape.

Intensification of the principle

A " sharper " version of the pigeon principle is as follows:

Example of the tightening

Thus one can now prove that there are at least 82 German with the same amount of hair, if it is assumed that in Germany there are at least 82 million inhabitants and all have less than 1,000,000 hairs: We distribute 82 million objects ( German ) on 1,000,000 volumes ( the hair number of its elements [ objects ] to play ), so there's at least an amount of at least objects.

Related Topics

With combinatorial generalizations of the principle of the Ramsey theory is concerned, see eg Van der Waerden theorem.

Literature and links

• Martin Aigner and Günter M. Ziegler: Proofs from THE BOOK, Berlin ( Springer ) 2002
• Pigeon Principle at cut- the- knot (English, math with examples. )

• Discrete Mathematics
• Proof ( mathematics)