Dirichlet principle: problems with solutions
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.
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
Today there are several different formulations of this principle. The most understandable and simple means that you can not put 8 rabbits in 3 cells so that each has no more than 2. A more scientific and complex formulation explaining the Dirichlet principle says: if there are k + 1 hares in k cells, then at least At least 1 cell will contain more than one hare. And if k-1 hares are in k cells, then at least 1 cell will contain less than one hare. The proof of this statement is quite simple, so to speak, by contradiction. If we assume that there are less hares in each cell than k-1 / k, then there are less than k * k-1 / k = k-1 in k cells of hares, which contradicts the initial conditions.
In fact, such a simple and understandable principle greatly facilitates the solution of problems in mathematics and the proof of many laborious theorems.It is just necessary to take into account that hares and cells can be easily replaced with mathematical objects and objects (numbers, points, segments, figures, etc.).
Sometimes tasks on the Dirichlet principle are not as simple and obvious as with animals in boxes. It is necessary to transfer this principle to mathematical sets in order to find any solutions. In this case, you can rely on another, more complex wording.
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.
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 depict on a sheet of notebook the coordinate system, the basis of which is located in one of the nodes. The axes of the coordinate system will coincide with the grid lines, and the side of the cell is taken as a single segment. It turns out that all 5 marked points will be in the system, and their coordinates will be only a whole number (even or odd). Thus, we get 4 options of coordinates: (even, even), (odd; even), (even, odd) and (odd; odd). So, 2 out of 5 points will correspond to one variant. If you look at the situation from the Dirichlet position, then it is necessary to designate the points as hares, and the variants of the coordinates - as cells. We get 5 birds with one stone and 4 cages, respectively, in one of them there will be at least 2 animals. Suppose these are points P and A, with coordinates (x4y3) and (x5y6). 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 x4and x5,y3and 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.
In order to facilitate the decision, it is necessary to imagine that the road can be “wound” on a circle with a length of Ö2 meters. It turns out that all the grooves will merge into 2 opposite, and the steps of the person 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 is in the arc denoting the groove, no matter what length k arc (groove width). Of course, it is obvious that if a man walked a distance equal to less than k, then sooner or later he would have entered a ditch. After all, a person will not be able to overstep the distance k if his step length is less than k. So, we need to find two tracks, the distance between which will not exceed the value of k. To this end, it would be appropriate to use the principle of Dirichlet. We mentally divide the entire circle into arcs with a size less than k and we will consider them as cells. Suppose there are n of them.Suppose that the number of steps is greater than the number of arcs (n + m), although no two steps will coincide due to the irrationality of the number Ö2, then according to the Dirichlet principle, at least one of the cells will contain more than one step. And since the arc length is less than k, then the distance between the steps will be less. Thus, we found the steps necessary for the proof.
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
Class in which 25 people. Of any 3 randomly selected students, two will be friends. It is necessary to prove that there is a schoolboy in the class who has more than 11 friends.
To begin with, we take two schoolchildren who are not friendly with each other (since if they were all friends with each other, there would be three friends in each troika and each student would be friends with 24 others). The remaining 23 classmates will be friends with one of our two, because otherwise there would be a troika with no friends (and this contradicts the original condition of the problem). It turns out that one of the two students will be friends with at least 12 students. In this case, the students are rabbits, and the terms "friends or not" are cells. We have 23 animals and only 2 cages. Accordingly, in one of them at least 23/2 = 11.5, that is, 12 rabbits. That is, one of the 2 students chosen by us will be friends with at least 12 of their classmates (or even more). Of course, there are other methods for solving the problem, but this is one of the most understandable and convenient.