The Dovecote Principle , also called Dirichlet’s Principle , states that if p pigeons are divided into q lofts, and if p > q, then there will be at least one loft with more than one pigeon. Another way of saying it is that q holes can hold, at most, q objects if each of the objects is in a different hole, so the fact of adding another object forces you to reuse some of the holes. Otherwise: if you take 8 human people, at least two will have been born on the same day of the week.
It is admitted that the original statement of the beginning bears the creative stamp of Dirichlet , in 1834 , with the name of Schubfachprinzip (“principle of drawers”). It is important and necessary to distinguish it from another principle on harmonic functions, also known by the name of this Teutonic creator.
Summary
[ hide ]
- 1 Sketch
- 2 Statement and proof
- 3 Uses and applications
- 4 Bibliography
- 5 Sources
Sketch
- Principle of distribution, the loft or the Dirichlet box. Let m, n, and p be three natural numbers. If you want to put np + m objects in n boxes, some box must contain at least p + 1 objects.
- If each box contains at most p objects, the total number of objects that we can place is np <np + 1 ≤ np + m.
In its simplest version, this principle says that an injective application cannot exist between a set of m elements and another of n elements, if m> n. Equivalently, if you want to place m objects in n boxes, with m> n, at least one box must contain at least 2 objects.
Although the loft principle may seem like a trivial statement, it can be used to demonstrate surprising results. For example, there are at least 2 people in Havana with the same number of hairs on their heads. Demonstration: a person’s head has around 750,000 hairs and having a million hairs would require a giant head (nobody has a million hairs on the head). We assign a loft for each number from 0 to 1,000,000 and we assign a pigeon to each person who will go to the loft corresponding to the number of hairs on their heads. Since there are more than a million people in Havana, there will be at least two people with the same number of hairs on their heads.
A generalized version of this principle says that if n discrete objects must be kept in m boxes, at least one box must contain no less than T (n / m) objects, where T denotes the ceiling function .
Statement and proof
There is no injective function of A in B as long as the cardinal of A is greater than that of B being these finite sets.
- Induction demonstration
- Basestep: Suppose | B | = 0 . So there is no function f: A in B , in particular there is no injective function.
- Inductive hypothesis: f: A in B is not injective for every finite set A and for every finite set B , that meet | A | > | B | , and | B | <= n , with n> = 0 .
- Inductive thesis: For | A | > | B | = n + 1 , there is no function f: A in injective
- Demonstration of the inductive step: As A is not empty, we choose one of which belongs to A . Two things can happen. Or there is another element other than a in A , let’s call ‘ that f (a) = f (a’) . Or there is no such element. If the case exists, the function f is not injective and the demonstration ends. Let’s take the case that it doesn’t exist, so f (a) has only one preimage that is a. We consider the function g: A – {a} in B – {f (a)} that coincides with f in all the elements of A – {a} . Now we apply the inductive hypothesis since B – {f (a)}it has n elements, therefore g is not injective. Since g is not injective, f is not injective, which is what we wanted to demonstrate.
Uses and applications
The loft principle is often found in computing. For example, collisions are unavoidable in a hash table because the number of possible values that the elements of a vector can take often exceed the number of their indices. No hashing algorithm, no matter how good it is, can prevent these collisions. This principle also proves that any lossless compression algorithm that makes at least one input file smaller will make another input file larger. (Otherwise, two different files could be compressed to the same smaller file and when restored there would be conflict).
