Lecture
In combinatorics, the Dirichlet principle — a statement formulated by the German mathematician Dirichlet in 1834; it establishes a relationship between objects («rabbits») and containers («boxes») when certain conditions are met.
In English and some other languages the statement is known as the «pigeonhole principle» (Eng. Pigeonhole principle), where the objects are pigeons and the containers are boxes (holes). In German it is called the «box principle» (Ger. Schubfachprinzip).
The Dirichlet principle is often applied in proving theorems, especially in discrete mathematics; in particular, in the theory of Diophantine approximations and in the analysis of the solvability of systems of linear inequalities.
The Dirichlet principle. If n+1 or more rabbits sit in n boxes, then there is a box containing at least two rabbits. Let us discuss
examples
1. Six schoolchildren ate seven candies. Prove that one of them ate at least two candies.
2. There are 15 pupils in a class. Is there a month in which at least two pupils of this class celebrate their birthdays?
3. A store received 25 crates of apples of three varieties, with each crate holding apples of some single variety. Can one find 9 crates of apples of the same variety?
9 holes contain 7 pigeons; by the Dirichlet principle at least one hole (in fact even more than one) contains no pigeons
9 holes contain 10 pigeons; by the Dirichlet principle at least one hole contains more than one pigeon
The most widespread formulation of this principle is the following:
If rabbits are placed in boxes, and the number of rabbits is greater than the number of boxes, then at least one of the boxes contains more than one rabbit.
Variants of more general formulations :
or more items among 
boxes, in some box there will be at least 
item.
rabbits, and also at least one box contains no more than 
rabbits. Here the Iverson brackets 
and 
round the expression enclosed in them to an integer, up and down respectively.
on finite sets A and B be given, with 
, where 
. Then the function will take some one of its values at least 
times 
.Formulations for particular cases are also encountered:
If the number of boxes is greater than the number of rabbits, then at least one box is empty.
Theorem 1. For any choice of five points inside a unit square there is a pair of points at a distance from each other of no more than 
Proof. At first glance the theorem seems complicated and non-obvious, but with the help of the Dirichlet principle it is proved without difficulty . Divide the square into 4 quarters, as shown in the figure. At least two of the five chosen points will fall into one quarter, and then the distance between them will be no more than the diagonal of the quarter, equal to ■
Theorem 2. Part of a company of 
people 
exchange handshakes. Prove that in the company there are at least two people who made the same number of handshakes .
Proof. Let us define «boxes» 
and place into box 
those participants of the company who made 
handshakes. If box 
is not empty, then one or more participants of the company made no handshakes at all, and hence box 
is then empty, because the number of those who made handshakes turns out to be less than 
It follows from this that the number of nonempty boxes is always less than 
and, consequently, at least one box corresponds to two or more people. ■
Theorem 3. For any positive irrational number 
there exist infinitely many fractions 
differing from by less than 
(this is one of the versions of Dirichlet's theorem on Diophantine approximations) .
Proof. For an arbitrary natural number form a set of 
values:
, where 
denotes the integer part of the number.
All these numbers belong to the interval from 0 to 1. Let us distribute them into boxes: in the first box we place the numbers from 0 to 
, in the second — from 
to 
, and so on. But since there are more of these numbers than the number of boxes, by the Dirichlet principle in one of the boxes there will be at least two differences: 
and 
The values of the differences by construction differ by less than 
Setting 
we obtain:
or: 
(since 
)
By virtue of the arbitrariness of the number the closeness of the fraction to the number can be made arbitrarily small, therefore the number of fractions is infinite. ■
There exists a generalization of this principle to the case of infinite sets: there is no injection of a more powerful set into a less powerful one. Example: if an uncountable set of pigeons is contained in a countable set of boxes, then at least one of the boxes contains an uncountable set of pigeons.
A number of modern generalizations of the Dirichlet principle are given in Ramsey theory.
Suppose that a drawer contains a mixture of black and blue socks, each of which can be worn on either foot, and that you pull several socks out of the drawer without looking. What is the minimum number of socks pulled out needed to guarantee a pair of the same color? Using the pigeonhole principle, to have at least one pair of the same color ( m = 2 holes, one per color), using one box for each color, you need to pull only three socks out of the drawer ( n = 3 items). Either you have three items of the same color, or you have two items of the same color and one of the other color .
If there are n people who can shake each other's hands (where n > 1 ), the pigeonhole principle shows that there is always a pair of people who shake hands with the same number of people. In this application of the principle, the «hole» to which a person is assigned is the number of hands they shake. Since each person shakes hands with some number of people from 0 to n - 1 , there are n possible holes. On the other hand, either the hole '0' or the hole ' n - 1', or both must be empty, since it is impossible (if n > 1) for someone to shake hands with everyone while someone shakes hands with no one. This leaves n people who must be placed into at most n - 1 nonempty holes, so the principle applies.
This handshaking example is equivalent to the statement that in any graph with more than one vertex there is at least one pair of vertices with the same degree . This can be seen by associating each person with a vertex and each edge with a handshake.
One can demonstrate that in London there must be at least two people with the same number of hairs on their heads, as follows. Since a typical human head has on average about 150,000 hairs, it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head ( m = 1 million holes). More than 1,000,000 people live in London ( n greater than 1 million units). By assigning a hole for each number of hairs on a person's head and distributing people into holes according to the number of hairs on their heads, there must be at least two people assigned to the same hole by the 1,000,001st assignment (because they have the same number of hairs on their heads) (or, n > m ). Assuming that 8.9 million people live in London [10], one can even assert that at least nine Londoners have the same number of hairs, since eight Londoners in each of the 1 million holes make up only 8 million people.
For the average case ( m = 150,000 ) with the constraint of the smallest number of overlaps, there would be at most one person assigned to each hole and 150,001 people assigned to the same hole as someone else. In the absence of this constraint, there may be empty holes, because a «collision» occurs before the 150,001st person. The principle merely proves the presence of an overlap; it says nothing about the number of coincidences (which falls under a probability distribution ).
In the «History of the Athenian Society» there is a passing satirical allusion to this version of the principle, prefaced «A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries». (Printed for Andrew Bell, London, 1710.). [11] It seems the question whether there were in the World any two persons with the same number of hairs on their heads? was raised in the Athenian Mercury before 1704. [12] [13]
Perhaps the first written mention of the pigeonhole principle appears in 1622 in a short sentence of the Latin work Selectae Propositiones , by the French Jesuit Jean Leurechon , where he wrote: «It is necessary that two people have the same number of hairs, écus or other things as each other". [14] The full principle was set out two years later with additional examples in another book, which is often attributed to Leurechon but was perhaps written by one of his students.
In the birthday problem a set of n randomly chosen people is given; what is the probability that some pair of them will share a birthday? By the pigeonhole principle, if there are 367 people in a room, there is at least one pair sharing a birthday, since there are only 366 possible birthdays to choose from (including February 29, if present). The birthday «paradox» refers to the result that even if a group consists of only 23 people, the probability that there is a pair of people with the same birthday is still greater than 50%. Although at first glance this may seem surprising, it makes intuitive sense if one takes into account that the comparison is actually made between all possible pairs of people, rather than fixing one person and comparing them solely with the rest of the group.
Imagine seven people who want to play a team tournament ( n = 7 items) with the constraint of choosing only four teams ( m = 4 holes). The pigeonhole principle tells us that they cannot all play on different teams; there must be at least one team that includes at least two of the seven players:
Any subset of size six from the set S = {1,2,3, ..., 9} must contain two elements whose sum equals 10. The holes will be labeled by two-element subsets {1,9}, {2 , 8}, {3,7}, {4,6} and the singleton {5}, five holes in all. When six «pigeons» (the elements of the subset of size six) are placed in these holes, and each pigeon goes into the hole on whose label it is contained, at least one of the holes labeled by a two-element subset will have two pigeons in it. [15]
This principle can be used to prove that any lossless data compression algorithm , provided that it makes some inputs smaller (as the name compression suggests), will also increase some other inputs. Otherwise the set of all input sequences up to a given length L could be mapped to the (much) smaller set of all sequences of length less than L without collisions (since the compression is lossless), a possibility that the pigeonhole principle excludes.
A notable problem in mathematical analysis is, for a fixed irrational number a , to show that the set {[ na ]: n is an integer} of fractional parts is dense in [0, 1]. It turns out to be not easy to explicitly find such integers n , m that | na - m | < e , where e > 0 is a small positive number, and a is an arbitrary irrational number. But if one takes M such that 1 / M < e, by the pigeonhole principle there must be n 1 , n 2 ∈ {1, 2, ..., M + 1 } such that n 1 a and n 2 a are in the same integer subdivision of size 1 / M (there are only M such divisions between consecutive integers). In particular, one can find n 1 , n 2 such that n 1 a is in ( p + k / M , p + ( k + 1) /M ) , and n 2 a is in ( q + k / M , q + ( k + 1) / M ) for some p , q integers and k in {0, 1, ..., M - 1 }. Then it is easy to verify that ( n 2 - n 1 ) a is in ( q - p - 1 / M , q - p + 1 / M ). It follows that [ na ] <1 / M < e , where n = n 2 - n 1 or n = n 1 - n 2 . This shows that 0 is a limit point of {[ na ]}. One can then use this fact to prove the case for p in (0, 1] : find n such that [ na ] <1 / M < e ; then, if p ∈ (0, 1 / M ], the proof is complete. Otherwise p ∈ (j / M , ( j + 1) / M ], and, setting k = sup { r ∈ N : r [ na ] < j / M }, we obtain | [( k + 1) na ] - p | <1 / M < e .
Variants occur in a number of proofs. The proof of the pumping lemma for regular languages uses a version that mixes finite and infinite sets: if infinitely many objects are placed into a finite number of boxes, then there exist two objects that share a box. [16] Fisk's solution of the Art Gallery problem uses a kind of converse: if n objects are placed into k boxes, then there is a box containing at most n / k objects. [17]
Below are alternative formulations of the pigeonhole principle.
Let q 1 , q 2 , ..., q n be natural numbers. If
objects are distributed among n boxes, then either the first box contains at least q 1 objects, or the second box contains at least q 2 objects, ..., or the n- th box contains at least q n objects. [19]
The simple form is obtained from this when q 1 = q 2 = ... = q n = 2 , which gives n + 1 objects. Taking q 1 = q 2 = ... = q n = r gives a more quantitative version of the principle, namely:
Let n and r be natural numbers. If n ( r - 1) + 1 objects are distributed into n boxes, then at least one of the boxes contains r or more objects. [20]
This can also be formulated as follows: if k discrete objects are to be distributed among n containers, then at least one container must contain at least 
objects, where 
is the ceiling function, denoting the smallest integer greater than or equal to x . Likewise, at least one container must hold at most 
objects, where 
is the floor function, denoting the largest integer less than or equal to x .
The probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly placed into m mailboxes with equal probability 1 / m , then at least one pigeonhole will contain more than one pigeon with probability
where ( m ) n is the falling factorial m ( m - 1) ( m - 2) ... ( m - n + 1) . For n = 0 and for n = 1 (and m > 0 ) this probability is zero; in other words, if there is only one pigeon, there can be no conflict. For n > m (more pigeons than holes) it equals one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of mailboxes ( n ≤ m), because of the random nature of the distribution of pigeons among boxes there is often a significant probability of a collision. For example, if 2 pigeons are randomly distributed among 4 holes, there is a 25% probability that at least one hole will contain more than one pigeon; for 5 pigeons and 10 holes this probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes remains fixed, there is always a greater probability of a pair as you add more pigeons. This problem is examined in more detail in the birthday paradox .
A further probabilistic generalization is that when a real random variable X has a finite mean value E ( X ) , then the probability is nonzero that X is greater than or equal to E ( X ) , and similarly the probability is nonzero that X is less than or equal to E ( X ) . To see that this implies the standard pigeonhole principle, take any fixed arrangement of n pigeons in m holes and let X be the number of pigeons in a hole chosen uniformly at random. The mean value of X equals n / m , so if there are more pigeons than holes, the mean value is greater than one. Consequently, X is sometimes at least 2.
The pigeonhole principle can be extended to infinite sets by formulating it in terms of cardinal numbers: if the cardinality of a set A is greater than the cardinality of a set B , then there is no injection from A into B . However, in this form the principle is tautological, since the meaning of the statement that the cardinality of a set A is greater than the cardinality of a set B is precisely that there is no injection from A to B . However, adding at least one element to a finite set is enough to increase its cardinality.
Another way to formulate the pigeonhole principle for finite sets is similar to the principle that finite sets are Dedekind-finite: let A and B be finite sets. If there is a surjection from A to B that is not injective, then no surjection from A to B is injective. In fact, no function of any kind from A to B is injective. This is not true for infinite sets: consider the function on the natural numbers that sends 1 and 2 to 1, 3 and 4 to 2, 5 and 6 to 3, and so on.
A similar principle holds for infinite sets: if an uncountable number of pigeons is placed into a countable number of holes, there will exist at least one box into which an uncountable number of pigeons is placed.
However, this principle is not a generalization of the pigeonhole principle for finite sets: in the general case it is false for finite sets. In technical terms it says that if A and B are finite sets such that any surjection from A to B is not injective, then there exists an element b of B such that there exists a bijection between the preimage of b and A . This is a completely different statement, absurd for large finite cardinalities.
Yakir Aharonov et al. presented arguments that the pigeonhole principle may be violated in quantum mechanics , and proposed interferometric experiments to test the pigeonhole principle in quantum mechanics. However, later studies called this conclusion into question. In January 2015, in an arXiv preprint, researchers Alastair Rae and Ted Forgan of the University of Birmingham performed a theoretical analysis of the wave function of the flight of electrons of various energies through an interferometer using the standard pigeonhole principle. If the electrons had no interaction force at all, each of them would give a single perfectly round peak. At high interaction force, each electron gives four distinct peaks, 12 peaks in all on the detector; these peaks are the result of the four possible interactions that each electron can experience (individually, only together with the first other particle, only together with the second other particle, or all three together). If the interaction force were quite low, as it would be in many real experiments, the deviation from the zero-interaction pattern would be almost imperceptible, much smaller than the lattice period of the atoms in solids such as the detectors used to observe these patterns. This would make it very difficult or even impossible to distinguish a weak but nonzero interaction force from no interaction at all, and would thus give the illusion of three electrons that did not interact despite all three passing along two paths.
rabbits. Assume that each box contains at most one rabbit:
(number of rabbits in the 1st box)
(number of rabbits in the 2nd box)
(number of rabbits in the 
. We have obtained a contradiction, since by assumption the number of rabbits is 
Comments