Drawer principle

In the mathematics that is pigeonhole principle (Engl. Pigeonhole principle , therefore, also Pigeonhole ) to make a simple, intuitive and often useful method to certain statements of a finite set. The principle is often used in discrete mathematics .

The principle

The principle can be formulated informally as follows:

If objects are divided into sets and are larger than , then there is at least one set in which more than one object ends up. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle (n,m>0)}$ ${\displaystyle n}$ ${\displaystyle m}$

or equivalent

If objects are divided into sets and are smaller than , then there is at least one set in which no object ends up. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle (n,m>0)}$ ${\displaystyle n}$ ${\displaystyle m}$

The name comes from a pictorial representation of this process: if you have a certain number of drawers and you put more objects in the drawers than there are pockets, then at least two of these objects end up in any drawer.

It probably goes back to Dirichlet , who used it in 1834. In many languages ​​(Bulgarian, Czech, Danish, Icelandic, Kazakh, Latvian, Polish, Romanian, Russian etc.) it is therefore also called the “Dirichlet principle”.

proof

The proof of this principle is trivial and can be done indirectly , for example : If the principle is not correct, then at most one object ends up in each drawer. This means there are at most as many objects as there are drawers. But that contradicts the requirement that there are more objects than drawers.

Examples

Despite its simplicity, you can make certain statements with the drawer principle, for example that there are at least two people in Munich who have exactly the same number of hairs on their heads. Proof: All residents of Munich are divided into “drawers” ​​according to the number of their hairs. Typically, humans have around 100,000 to 200,000, but certainly less than 1 million hairs, so there are a maximum of one million drawers (from 0 to 999,999). But since there are around 1.4 million inhabitants in Munich, you have more inhabitants than drawers, so two or more people end up in at least one drawer. According to the definition of the drawers, these have the same number of hairs on their heads.

Another example is the statement that in a group of 13 people at least two have birthdays in the same month (because there are only 12 months).

Another, somewhat more complex example, in which the drawer principle is used, is the following: If you choose twelve different two-digit numbers in pairs , there are at least two of them whose difference is a two-digit number whose two digits are the same. Proof: The representation of a two-digit number that is a multiple of eleven consists of two identical digits. Now you think about which remainders can result from dividing a number by 11 (see remainder class ). It turns out that the numbers 0 to 10 are the possible residues. If two numbers leave the same remainder, their difference is a multiple of 11. So there are 11 “drawers” ​​but 12 two-digit numbers that are distributed over them. According to the drawer principle, there are two numbers in a compartment; As explained above, their difference is a multiple of 11, so it has the desired shape.

Tightening of the principle

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

Distributed to objects on amounts , so there is at least an amount of at least, properties are here means the symbol is the smallest integer which is greater than or equal is . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle (n,k>0)}$ ${\displaystyle \lceil {\tfrac {n}{k}}\rceil }$ ${\displaystyle (}$ ${\displaystyle \lceil {\tfrac {n}{k}}\rceil }$ ${\displaystyle {\tfrac {n}{k}}}$ ${\displaystyle )}$

Example of tightening

So you can now prove that there are at least 82 people in Germany with the same number of hairs, if you assume that there are at least 82,000,000 people in Germany and all have less than 1,000,000 hairs: We distribute 82,000,000 objects (residents) to 1,000,000 sets (which reflect the hair number of their elements [objects]), so there is at least one set with at least objects. ${\displaystyle {\tfrac {82.000.000}{1.000.000}}=82}$

Related topics

The Ramsey theory deals with combinatorial generalizations of the principle , see e.g. B. Van der Waerden's Theorem .

Literature and web links

• Martin Aigner , Günter M. Ziegler : The Book of Evidence , Berlin (Springer) 2002
• Pigeon Principle at cut-the-knot (with math. Examples)
• Daniel Schwenter : To prove that it may be possible / yes it must be / that one of two people has as much hair on his body / as the other in Deliciæ physico-mathematicæ , Nuremberg 1636, p. 86