There are many principles in mathematics. Some of them are fairly simple and understandable even for the beginner, and some require certain explanations and proofs. However, they are all very effective, and they can be easily applied in practice. One of them is the Dirichlet principle (also known as the principle of pigeons / rabbits). This is a fairly simple statement that can help in solving many mathematical problems.
This principle was formulated by the honorary German mathematician Johann Dirichlet back in 1834. Today it is used in combinatorics, as well as in mathematical physics. In translation from the original German, it sounds like the "box principle". The scientist conducted his studies with rabbits and containers. He demonstrated that if you place, say, 5 rabbits in 7 containers, then at least one container will contain 5/7 of one animal. However, the rabbit can not be divided into parts, therefore, at least one cell will be empty (5/7 is 0 integers). Similarly, in the opposite direction, if the rabbit 7, and the boxes 5, then at least one of them - 2 rabbits (7/5 is 2 whole). Starting from this statement, the mathematician managed to formulate a principle that ensures the successful solution of problems in mathematics for many years.
Modern formulation and proof
In fact, such a simple and understandable principle greatly facilitates the solution of problems in mathematics and the proof of many laborious theorems. Just need to consider that hares and cells can easily be replaced by mathematical objects and objects (numbers, points, segments, shapes, etc.).
Sometimes tasks on the Dirichlet principle is not as simple and obvious as with animals in crates. You must carry this principle into mathematical sets to find any solutions. In this case, it is possible to rely on another, more complex formulation.
If you map a set S containing d + 1 elements to a set R with a set of d elements, then two elements from the set S will have the same image.
Although modern GEF mathematics present creative requirements to students and offer non-standard options, the solution through Dirichlet's statement is not always so simple and straightforward. Sometimes it is very difficult to determine what value is considered an animal, and which is a cell, and how the fact of having two animals in one cell will help solve the problem. And if you manage to figure it out, you still can not determine which cell the object will be in. That is, you can simply prove the existence of such a cell, but you can not specify it.
Example No. 1. Geometry
Modern examples of problem solving demonstrate that perfectly different mathematical objects can act as animals and cells.
The line k passes through the plane of the triangle ABC, but does not intersect any of its vertices. It is necessary to prove that it can not cross its three sides.
Let us imagine how the line k divides the triangle into two planes, let's call them s1 and s2. We assume that s1 and s2 are open, that is, they do not contain the line k. Well, now is the time to apply the Dirichlet principle. Problems with solutions can demonstrate that under the rabbits and cells in modern conditions means a variety of objects. So, instead of hares, we substitute the vertices of a triangle, and instead of cells - half-planes. Since the straight line k does not intersect any of the vertices, each of them is in one plane or another. But since the vertices in the triangle are three, and we have only two planes (s1 and s2), one of them will contain two vertices. Suppose that they are vertices of A and B, and they are in the half-plane s2 (that is, they lie on one side of k). In this case, the segment AB does not intersect the line k. That is, there is a side in the triangle that the line k does not intersect.
In this problem, we assumed that there are points A and B in one plane, but the Dirichlet principle does not indicate a specific cell, so we could specify exactly that in the same plane the vertices C and B or A and C were placed. For this task It does not matter which side of the triangle the straight line k does not intersect. Therefore, this principle is ideal for solving it.
Example No. 2. Geometry
In the middle of an equilateral triangle ABC (for which AB = BC = AC = 1) there are 5 points. It is necessary to prove that two of them are located at a distance less than 0.5.
If you draw the middle lines in the right triangle ABC, they divide it into 4 small regular triangles with sides ½ = 0.5. Suppose that these triangles are cells, and the points inside them are rabbits. It turns out, we have 5 rabbits and 4 cells, therefore, in one of them there will be at least two rabbits. Given that the points are not vertices (since they are located inside the triangle ABC, and not on one of its sides), they will be placed inside the small figures. Consequently, the distance between them will be less than 0.5 (since the value of the segment inside the triangle never exceeds the value of its largest side).
Example No. 3. Combinatorics
In other areas, it is also possible to successfully apply the Dirichlet principle: combinatorics and mathematical physics have long been based on it in solving problems.
Let's say that around the rounded table there are m flags of different countries at an equal distance from each other, and m representatives from each country are sitting at the table, each of which is located next to someone else's flag. It is necessary to prove that with a certain rotation of the table at least two of the representatives will be near their flags.
It turns out that there are m-1 ways to deploy the table so that the arrangement of representatives and flags changes (if you exclude the initial placement of the table), but there remain m representatives.
We apply Dirichlet's statement to the solution and denote that representatives act as rabbits, and certain positions of the table during rotation are cells. In this case, we need to draw an analogy between the position of the representative next to the corresponding flag and the filled cells. That is, a positive result (1 representative is placed near his flag) is equivalent to the result "the rabbit is in the cage". We understand that we have one less cell than we need (m-1), which means that in one of them there will be at least 2 rabbits. In this case, it is possible that some cell will be empty (no representative has coincided with the flag), and in some cell there will be two, three or even more rabbits (two, three or more representatives will coincide with the flags). Thus, with one specific rotation, at least two representatives will find themselves near their flags (at least two rabbits will fall into one cell).
When starting this task, it is important to understand that the initial position is also a cell, but by the condition of the problem it is known to be empty, so we reduce the total by 1 (m-1).
Example number 4. Number theory
The Dirichlet principle in number theory is also of great importance.
Suppose, on the leaf of the notebook in the cell, the student arbitrarily placed 5 points at the nodes of the cells. It is necessary to prove that at least one segment with vertices at these points will pass through the node of the cell.
First you need to draw on a sheet of notebook coordinate system, the basis of which will be located in one of the nodes. The axis of the coordinate system coincide with the grid lines, and a single cut accepted side cells. It turns out that all 5 of the marked points will be in the system, and their coordinates will be just an integer (odd or even). Thus, we get 4 possible coordinates: (odd4. y3 ) and (x5. y6 ). The middle of the segment connecting these two vertices will have the coordinates ((x4 + x5 ) / 2), ((y3 + y6 ) / 2)), which are integers under the conditions of the corresponding parity x4 and x5, y3 and y6. It turns out that the middle of the segment is located in the node of the cell.
Example No. 5
Sufficiently many problems of varying complexity can be solved through the Dirichlet principle. Problems with solutions of various mathematical and logical questions often rely on this principle.
On a straight road, small transverse grooves are dug. The distance between all the grooves is the same and is equal to Ö2 m. It is necessary to prove that, regardless of the width of the grooves, a person walking along the road with an interval of 1 m will one day get his foot into one of them.
To facilitate the solution, it is necessary to imagine that the way you can "reel" in circumference at Ö2 meters. It turns out that all of the grooves merge into 2 opposite, but the steps will be displayed in the form of an arc, equal to 1 m. We need to consistently mark all the steps, until one of them will be in the arc, indicating the groove, no matter what is the length k of the arc (the width of the groove). Of course, it is obvious that if the man walks a distance equal to less than k, then sooner or later he would come into the ditch. After all, the man did not succeed to cross the distance k, if the length of the step is less than k. So, we need to find two tracks, the distance between which shall not exceed the value k. To do this, it is appropriate to use the Dirichlet principle. We mentally divide the entire circumference into arcs of size less than k, and we assume their cells. For example, they will be n pieces. Suppose that the number of steps is greater than the number of arcs (n m), although no two steps will not match because of the irrationality of Ö2 number, then, by Dirichlet principle, at least in one of the cells will house more than one step. And since the arc length is less than k, then the distance between the steps will be smaller. Therefore, we found necessary to prove the steps.
A generalization of the principle
Materials on mathematics, besides standard (simple and not so) formulations, also contain one generalized one, which is used to identify more than two objects that are similar to each other. She claims that if dm + 1 rabbits are placed in d cells, then at least m + 1 rabbits will be in one cell.
Example No. 6. Generalization
Rectangle with an area of 5 x 6 cells (30 cells), painted only 19. Is it possible to detect a square of 2 x 2 cells in which a minimum of three will be painted?
Our figure needs to be divided into 6 blocks of 5 cells. Proceeding from Dirichlet's statement, in one of them at least 4 cells will be painted (19/6 = 4). Then in one of the squares of 4 cells, located in one of the blocks, a minimum of 3 cells will be painted.
Example No. 7
Two solutions to the question