The pigeon hole principle roughly means: "If each drawer represents a collection, then each apple can represent an element. If there are n+ 1 or more elements in n sets, at least one set must have at least two elements.
The pigeon coop principle is sometimes called the pigeon coop principle ("If there are five pigeon coops and the pigeon keeper keeps six pigeons, then when the pigeons fly back to the cages, there are at least two pigeons in one cage"). It was first put forward by Dirichlet, a German mathematician, to prove some problems in number theory, so it is also called Dirichlet principle. This is an important principle in combinatorial mathematics.
First, the most common form of pigeon coop principle
Principle 1 If more than n objects are put into n drawers, at least one drawer has more than two objects.
[Proof] (reduction to absurdity): If each drawer can only hold one object at most, then the total number of objects is n at most, not n+k(k≥ 1), which is impossible.
Principle 2 If more than mn objects are put into n drawers, at least one drawer has m+ 1 or more objects.
[Proof] (reduction to absurdity): If there are at most M objects in each drawer, then there are at most mn objects in N drawers, which is inconsistent with the topic, so it is impossible.
Principle12 is the expression of the first pigeon nest principle.
Second, the filing principle:
Put (Mn- 1) objects into n drawers, and there must be at most (M- 1) objects in a drawer.
[Proof] (reduction to absurdity): If there are not less than m objects in each drawer, there are always at least mn objects, which contradicts the topic, so it is impossible.
2. Apply the pigeon hole principle to solve the problem
The pigeon hole principle is simple and easy to accept, and plays an important role in mathematical problems. Many proofs of existence can be solved with it.
1:At least two out of 400 people have the same birthday.
Solution: Take 366 days in a year as 366 drawers and 400 people as 400 objects. From the pigeon hole principle 1, we can know that at least two people have the same birthday.
For another example, we randomly find 13 people on the street, and we can conclude that at least two of them belong to the same genus.
"Choose 6 pairs of gloves from any 5 pairs of gloves, of which at least 2 pairs are just a pair of gloves."
"From 1, 2, ..., 10, and there are at least two parity differences. "
Example 2: Kindergarten bought many plastic toys of white rabbits, pandas and giraffes, and each child chose two at random, so no matter how you choose, two out of any seven children always choose the same toy. Try to explain the truth.
Solution: Choose two toys from three kinds, and the matching methods can only be the following six kinds: (rabbit, rabbit), (rabbit, panda), (rabbit, giraffe), (panda, panda), (panda, giraffe), (giraffe). Considering that each collocation method is a drawer and seven children are the objects, according to the principle of 1, at least two objects should be placed in the same drawer, that is, at least two people should choose toys in the same collocation method and choose the same toys.
It seems that the above examples are all about "existence", "total existence" and "at least existence", which is the main function of pigeonhole principle. (It should be noted that pigeonhole principle only affirmed "existence", "total existence" and "at least existence", and could not exactly point out how many drawers there were. )
Although the principle of pigeon hole is simple, it is widely used. It can answer many interesting questions, some of which are quite difficult. Let's study some related problems.
(a) separability
Divide all integers into m classes according to the remainder divided by the natural number m, which is called the residual class or congruence class of m, and it is represented by [0], [1], [2], …, [m- 1]. Each class contains an infinite number, for example, [1] contains 1. ..... When studying divisibility-related issues, residue classes are often used as drawers. According to the pigeon hole principle, it can be proved that the difference between two natural numbers in any n+ 1 is always a multiple of n. ..
Example 1 proves that if we take 8 natural numbers, the difference between the two numbers must be a multiple of 7.
In the problems related to divisibility, analysis and solution have such properties. If two integers A and B have the same remainder when divided by the natural number M, then their difference a-b is a multiple of M. According to this property, this question only needs to prove that there are two natural numbers in these eight natural numbers. The remainder of their division by 7 is the same. We can divide all natural numbers into seven categories, that is, seven drawers, according to seven different remainders 0, 1, 2, 3, 4, 5 and 6 obtained by dividing by seven. According to the pigeon hole principle, there must be two numbers in the same drawer, that is, the remainder of their division by 7 is the same, so the difference between these two numbers must be a multiple of 7.
Example 2: For any five natural numbers, it is proved that the sum of three numbers must be divisible by three.
It is proved that the remainder obtained by dividing any number by 3 can only be 0, 1, 2, which can be constructed into three drawers respectively:
[0],[ 1],[2]
(1) If the remainder obtained by dividing these five natural numbers by 3 is distributed in these three drawers respectively, we take 1 from these three drawers, and the sum can be divisible by 3.
(2) If these five remainders are distributed in two drawers, there must be three remainders in one drawer (pigeon hole principle), and the sum of these three remainders is either 0, 3 or 6, then the sum of the corresponding three natural numbers is a multiple of 3.
If these five remainders are distributed in one of the drawers, obviously, the sum of the three natural numbers must be divisible by 3.
Example 2': For any integer 1 1, it is proved that there must be 6 numbers, and their sum can be divisible by 6.
Prove: Let the integers 1 1 be: a 1, a2, A3...A 1 1 and 6=2×3.
(1) Let's consider the case that it is divisible by 3.
According to Example 2, among the 1 1 arbitrary integers, there must be:
3|a 1+a2+a3, let's say a1+a2+a3 = b1;
Similarly, among the remaining eight arbitrary integers, from Example 2, there must be: 3 | a4+a5+a6. Let A4+A5+A6 = B2;
Similarly, among the other five arbitrary integers, there are 3|a7+a8+a9, and let: a7+a8+a9=b3.
② Consider again that b 1, b2 and b3 are divisible by 2.
According to the pigeon hole principle, at least two of the three integers b 1, b2 and b3 are the same odd or even, and the sum of these two same odd (or even) integers must be even. Let's set 2|b 1+b2.
Then: 6|b 1+b2, that is: 6|a 1+a2+a3+a4+a5+a6.
Any integer of ∴ 1 1, where the sum of 6 numbers must be a multiple of 6.
Example 3: Given seven different natural numbers arbitrarily, it is proved that there must be two integers, and their sum or difference is a multiple of 10.
Analysis: Note that these teams made 10 drawers, and the remainder of 10 is single digits, with 0, 1, …, 9 as the standard, marked with [0], [1], …, [9]. If two figures fall in the same drawer, the difference is 65438. [9] If four drawers are merged with [4], [3], [2] and [1] respectively, at least one drawer can be guaranteed to have two numbers, and their sum or difference is a multiple of 10.
(2) area problem
Example: Each of the nine straight lines divides a square into a trapezoid with an area ratio of 2:3, which proves that at least three of the nine straight lines pass through the same point.
Proof: As shown in the figure, let a straight line EF divide the square into two trapeziums, making it the center line MN. Since the heights of these two trapeziums are equal, their area ratio is equal to the length ratio of the neutral line, that is |MH|:|NH|. Therefore, point H has a definite position (it is on a straight line connecting the midpoints of a pair of opposite sides of a square and | MH |: | NH | = 2: 3). According to geometric symmetry, there are four such points * * (that is, H, J, I, K in the figure). Nine known dividing lines suitable for conditions, each of which must pass through H, J, I and K.
(3) Dyeing problem
Example 1 the cube is painted with red or blue paint (only one color is painted on each side), which proves that the colors on three sides of the cube must be the same.
It is proved that if two colors are regarded as two drawers and six faces of a cube are regarded as objects, then 6=2×2+2. According to principle 2, at least three faces should be painted the same color.
There are five children, and each child randomly draws three pieces from a bag with many black and white Go pieces. Please prove that at least two of the five children have pulled out the same color combination.
To analyze the answer, we must first determine how many different situations the colors of the three pieces can have, including: 3 black, 2 black, 1 white, 1 black, 2 white, 3 white * *, which is considered as four drawers. According to the pigeon hole principle, at least two children find out the color of the chess pieces in the same drawer, that is, the colors of the chess pieces they hold are the same.
Example 3: Suppose there are any six points on the plane, and there is no three-point connection. Every two points are connected by a red or blue line segment. After they are all connected, can you find a triangle composed of these lines so that the three sides of the triangle are the same color?
Solution: First, you can choose any one of these six points, and then connect five line segments from this point to the other five points. As shown in the figure, at least three of these five line segments are of the same color, assuming they are red. Now we will study these three red lines separately. The other ends of the three line segments can be different colors. Suppose one of the three line segments (dotted line) is red, then this red line segment and the other two red line segments form the same color triangle we need. If these three lines are all blue, then these three lines also constitute the same color triangle we need. Therefore, no matter how colored, at least one triangle with the same color can be found among all the line segments between these six points.
Example 3' (Six-person Party) proves that at any six-person party, either three people have known each other before or three people have not known each other before. "
Example 3 ":Each of the 65,438+07 scientists communicates with the other 65,438+06 people, and their communication only discusses three issues, while any two scientists discuss the same issue. Prove that at least three scientists are discussing the same problem when communicating.
Solution: Suppose A is a scientist, and he only discusses three problems with other 16 people. According to the pigeon cage principle, he discussed the same problem with at least six of them. Let these six scientists be B, C, D, E, F and G to discuss the A problem.
If two of these six people also discuss the problem of A, the conclusion is established. Otherwise, the six of them will only discuss the problems of B and C. In this way, we know from the pigeon cage principle that B has discussed at least the same problem with the other three. Let's assume that these three are C, D and E, and they are discussing the problem of B. ..
If two people in C, D and E also discuss the problem of B, the conclusion is established. Otherwise, they only discuss the problem of C, and this conclusion is also valid.
3. Making drawers is the key to applying this principle.
Example 1 Take any number 9 from 15 even numbers of 2, 4, 6, …, 30, and prove that the sum of the two numbers must be 34.
Analysis and solution We have made 8 drawers, of which 15 is even, and the theme is:
There are two numbers in a drawer, both of which have the same feature: the sum of these two numbers is 34. Now, from the even number of 15 in the topic, we can choose 9 numbers at will. From the pigeon hole principle (because there are only eight drawers), there must be two numbers in the same drawer. According to the characteristics of the drawer we made, the sum of these two numbers is 34.
Example 2: Choose at least a few of the 20 natural numbers 1, 2, 3, 4, …, 19, 20 to ensure that there must be two numbers, and their difference is 12.
By analyzing and solving these 20 natural numbers, the differences among the following 8 pairs are12: {20,8}, {19,7}, {18,6}, {17,5} and {/kloc-.
There are also four unpaired numbers {9}, {10}, {1}, {12} and * * * to form 12 drawers (each bracket is regarded as a drawer). As long as there are two numbers from the same drawer, the difference between them will be. It can be done (take the number of 12: take one number from the drawer of 12 (for example, take 1, 2,3, …, 12), then the difference between any two of these numbers of 12 must not be equal to/kloc.
Example 3: Of the 20 numbers from 1 to 20, no matter which number is 1 1, there must be two numbers, one of which is a multiple of the other.
To analyze and answer the questions required by the topic, we should consider making drawers according to the principle that any two numbers in the same drawer have multiples. Divide these 20 numbers into the following ten groups according to odd numbers and multiples, and regard them as 10 drawers (obviously, they have the above properties):
{ 1,2,4,8, 16},{3,6, 12},{5, 10,20},{7, 14},{9, 18},{ 1 1},{ 13},{ 15},{ 17},{ 19}。
Choose any one 1 1 from these 201arrays. According to the pigeon hole principle, at least two numbers are taken out of the same drawer. Because two numbers in the same drawer have multiple relationships, one of these two numbers must be a multiple of the other.
Exodus 4: On the anniversary of a school, N alumni came and shook hands with each other. Please prove that at least two of these N alumni shake hands as often as possible.
Analysis answers * * * There are n alumni, and each person shakes hands at least 0 times, that is, this person has never shaken hands with other alumni; At most, there are n- 1 times, that is, this person shakes hands with every alumni attending the meeting. But if an alumnus shakes hands 0 times, then the number of handshakes can't exceed n-2 times at most; If an alumnus shakes hands n- 1 time, the one with the least number of handshakes, whether the previous state is 0, 1, 2, …, n-2 or the latter state is 1, 2, 3, …, n-65438+, cannot be less than/. The number of handshakes is only n- 1. Think of this n- 1 as n- 1 drawers, and each of the n alumni attending the meeting is classified into the corresponding "drawers" according to the number of handshakes. According to the pigeon hole principle, if at least two people belong to the same drawer, then the two people shake hands as many times.
In some problems, "drawers" and "objects" are not obvious and need to be carefully made. How to make "drawers" and "objects" can be difficult. On the one hand, we should carefully analyze the conditions and problems in the topic, on the other hand, we should do more questions to accumulate experience.
drawer principle
Put eight apples into seven drawers at will. No matter how you put it, there are two or more apples in at least one drawer. Pigeonhole principle is sometimes called the pigeon coop principle. It was first put forward by Dirichlet, a German mathematician, and was used to prove some problems in number theory. Therefore, it is also called Dirichlet principle. This is an important principle in combinatorial mathematics. There are several forms that can be extended to the general situation.
Form 1: Proof: Suppose that N+ 1 elements are divided into n sets A 1, a2, …, An, and a 1, A2, …, an is used to represent the corresponding number of elements in these n sets. It is necessary to prove that at least one ai is greater than or equal to 2 (by reduction to absurdity), that is to say, it is assumed that the conclusion is not valid, that is, every ai has one.
A1+a2+…+an ≤1+…+1= n < n+1,which contradicts the topic. Therefore, at least one ai≥2 means that there must be two or more elements in a set.
Form 2: Let n? M+ 1 element is divided into n sets a 1, a2, …, An, and A 1, A2, …, an is used to represent the corresponding number of elements in these n sets. It is necessary to prove that at least one ai is greater than or equal to M+ 1. Assuming that the conclusion is not true, that is, every ai has ai < m+ 1, then because ai is an integer, there should be ai≤m, so there are:
a 1+a2+…+an≤m+m+…+m=n？ m