Principle 1: If more than n objects are put into n drawers, at least one drawer contains at least two items. drawer principle
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), so it is impossible. Principle 2: If there are more than mn(m times n) objects in N drawers, at least one drawer contains at least m+ 1 objects. Proof (reduction to absurdity): If each drawer can hold at most M objects, then N drawers can hold at most mn objects, which is inconsistent with the topic, so it is impossible. Principle 3: If you put an unlimited number of items in N drawers, there will be an unlimited number of items in at least one drawer. Principle 1, 2, 3 are all expressions of the first pigeon nest principle.
The second pigeon coop 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.
Edit this application.
abstract
It is simple and easy to solve the problem of pigeon hole principle by applying pigeon hole principle, which plays an important role in mathematical problems. Many proofs of existence can be solved with it. Example 1: Of the 400 people born in the same year, at least two have the same birthday. Solution: 365 days a year as 365 drawers, 400 people as 400 objects. According to the pigeon hole principle 1, at least two people have the same birthday. 400/365 =1… 35,1+0 = 2. Another example is that we randomly find them from the street. "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 why. Solution: Choose two of the three toys, and the matching methods can only be the following six: (rabbit, rabbit), (rabbit, panda) and (panda). Considering that each matching 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 to say, at least two people should choose toys with the same matching method. The above examples all seem to demonstrate the problems of "existence", "total existence" and "at least existence". Yes, this is the main function of pigeonhole principle. Using pigeonhole principle only affirms "existence", "eternal existence" and "at least existence", but it can't exactly point out which drawer contains how much. Although the principle of pigeon hole is simple, it is widely used and can answer many interesting questions, some of which are quite difficult. Let's study some related problems. Making drawers is an important example of applying this principle. 1 Choose 9 numbers 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 use the even number 15 in the title to make 8 drawers: Features of this drawer: Any drawer with two numbers has the same feature: the sum of these two numbers is 34. Now, from the even number of 15 in the topic, 9 numbers are randomly selected. From the pigeon hole principle (because there are only eight drawers), there must be two numbers in the same drawer (in line with the above characteristics). According to the characteristics of the drawer, 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. These 20 numbers are divided into the following ten groups according to odd numbers and multiples, which are regarded as 10 drawers respectively (obviously, they have the above properties): {1, 2,4,8, 16}, {3} 20}, {7, 14}. 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.
Divisibility problem
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 (it is proved that at least two of the remainder of n+ 1 natural numbers divisible by n are equal (pigeon hole principle), which can be written as m = a1* n+b = a2 * n+b. 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 three can only be 0, 1, 2, which may be constructed into three drawers respectively: [0], [1], [2] ① If five natural numbers are divided by three, the remainder obtained will be distributed in these three drawers. We take 1 from each of these three drawers (for example, take 3, 4 and 5 from 1~5), and its sum (3+4+5= 12) will be divisible by 3. ② If these five remainders are distributed in two drawers, one drawer should hold at least three remainders (pigeon hole principle). Select three remainders from the drawer with more remainders, and their algebraic sum is either 0, 3 or 6, all multiples of 3, so the sum of the corresponding three natural numbers is multiples of 3. (3) If these five remainders are distributed in one drawer, it is obvious that three remainders can be randomly extracted from this drawer. In the same example (2), the sum of the remainder can be divisible by 3. So the sum of three corresponding natural numbers can 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. Proof: Let the integer of 1 1 be: a 1, a2, A3...A66. 1 1 any integer must have: 3|a 1+a2+a3, assuming that 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. Let a7+a8+a9=b3 ② and then consider 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 or even. The sum of these two odd (or even) integers must be even. Let's set 2|b 1+b2, and then: 6|b 1+b2, that is, 6|a 1+a2+a3+a4+a5+a6 ∴ any 1668. The sum or difference is a multiple of 10. Analysis: Note that the remainder of these numbers divided by 10 is a single digit, and the 10 drawer is made with 0, 1, …, 9 as the standard and marked with [0], [1], …, [9]. Further adjustment: [6], [7], [8] and [9] are merged with [4], [3], [2] and [1] respectively, so that at least one drawer can be guaranteed to have two numbers, and their sum or difference is a multiple of 10.