There are many principles in mathematics. Some of them are quite simple and understandable even to a beginner, and some require certain explanations and evidence. 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 pigeon / rabbit principle). This is a fairly simple statement that can help in solving many mathematical problems.

Dirichlet principle: problems with solutions

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. Translated from the original German, it sounds like the "principle of boxes". The scientist conducted his research with rabbits and containers. He demonstrated that if we put, say, 5 rabbits in 7 containers, then at least in one container there would be 5/7 from 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 there are 7 rabbits and 5 boxes, then at least one of them has 2 rabbits (7/5 is 2 intacts). Starting from this statement, mathematics managed to formulate a principle that has been providing successful solutions to problems in mathematics for many years.

Modern wording 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. You just need to take into account that hares and cells can be easily replaced with mathematical objects and objects (numbers, points, segments, figures, etc.).

Another wording

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 we map the set S containing d + 1 elements to the set R with the set of d elements, then two elements from the set S will have the same image.

Although modern GEF in mathematics imposes creative requirements on students and offers non-standard options, the solution through Dirichlet’s statement is not always so simple and straightforward. Sometimes it is very difficult to determine which value to consider as an animal, and which as a cage, and how the fact of having two animals in one cage will help to solve the problem. And if we manage to figure it out, it is still impossible to determine in which particular cell the object will be. That is, you can simply prove the existence of such a cell, but you cannot concretize it.

Example number 1. Geometry

Modern examples of problem solving demonstrate that perfect various 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 cannot cross its three sides.

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, not containing the line k. Well, now is the time to apply the Dirichlet principle. Problems with solutions can demonstrate that, under the present conditions, rabbits and cages mean various objects. So, instead of hares, we substitute the vertices of the triangle, and instead of the cells - the half-plane. Since the drawn line k does not intersect any of the vertices, each of them is in one or another plane. But since there are three vertices in the triangle and we have only two planes (s1 and s2), one of them will contain two vertices. Suppose that these are vertices A and B, and they are in the half-plane s2 (that is, they lie on the same side of k). In this case, the segment AB does not intersect the straight line k. That is, there is a side in the triangle that k does not intersect.

Alternative solution

In this task, we assumed that the points A and B are in the same plane, but the Dirichlet principle does not indicate a specific cell, so we could also point out that the vertices C and B, or A and C were located in the same plane. For this task it does not matter which side of the triangle the straight line k intersects. Therefore, this principle is ideal for its solution.

Example No. 2. Geometry

In the middle of an equilateral triangle ABC (in which AB = BC = AC = 1) 5 points were located. It is necessary to prove that two of them are located at a distance less than 0.5.

If you draw middle lines in the right ABC triangle, they divide it into 4 small right triangles with sides ½ = 0.5. Suppose these triangles are cells, and the points inside them are rabbits. It turns out that 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 small figures. Consequently, the distance between them will be less than 0.5 (since the size of the segment inside the triangle never exceeds the size of its largest side).

Example number 3. Combinatorics

In other fields, the Dirichlet principle can also be successfully applied: combinatorics and mathematical physics have long been based on it in solving problems.

For example, around a rounded table, m flags of different countries stand at equal distances from each other, and m representatives from each country sit 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 expand the table so that the mutual arrangement of representatives and flags changes (if we exclude the initial placement of the table), but there are m representatives left.

Let us apply the Dirichlet assertion to the solution and denote that the representatives are rabbits, and certain table positions during rotation are cells. In this case, it is necessary to draw an analogy between the location 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 cell less than what is needed (m-1), which means that one of them will have at least 2 rabbits. At the same time, situations are not excluded that some cage will be empty (not a single representative matches the flag), and in some cage there will be two, three or even more rabbits (two, three or more representatives will coincide with the flags). Thus, with one certain rotation, at least two representatives will find themselves near their flags (at least two rabbits will fall into one cell).

Starting the solution of such a problem, it is important to understand that the initial position is also a cell, but according to the condition of the problem it is obviously empty, so we reduce the total by 1 (m-1).

Example number 4. Theory of numbers

The Dirichlet principle in number theory is also of paramount importance.

Suppose, on a piece of a notebook in a cage, the student randomly at the nodes of the cells put down 5 points. It is necessary to prove that at least one segment with vertices at these points passes 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 coordinates ((x4   + x5   ) / 2), ((y3   + y6   ) / 2)), which will be integers under conditions of corresponding parity x4   and x5,   y3   and y6. It turns out that the middle of the segment is located in the cell node.

Example number 5

Quite a lot of tasks of different complexity can be solved through the Dirichlet principle. Problems with solutions of various mathematical and logical questions are often based on this principle.

On the straight road dug small transverse grooves. The distance between all the grooves is the same and equal to Ö2 m. It is necessary to prove that, regardless of the width of the grooves, a person walking along a road with an interval of 1 m will once fall 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.

Generalization of the principle

Materials on mathematics, in addition to standard (simple and not very) formulations, also contain one generalized, which is used to identify more than two objects similar to each other. She argues that if dm + 1 rabbits are placed in d cells, then at least m + 1 rabbits will be in the same cell.

Example No. 6. Generalization

A rectangle with an area of ​​5 x 6 cells (30 cells), shaded only 19. Is it possible to find a square with an area of ​​2 x 2 cells, in which at least three will be painted over?

Our figure must be divided into 6 blocks of 5 cells. Based on the statement of Dirichlet, in one of them at least 4 cells will be painted over (19/6 = 4). Then in one of the squares with an area of ​​4 cells, located in one of the blocks, at least 3 cells will be painted over.

Example number 7

Two solutions

Interesting: