Post on the news page, know MP3 pictures, videos, encyclopedias, and ask for help.
The pigeon nest principle, also known as the pigeon hole principle, is a special case of Ramsey theorem.
Its simple form is: put n+ 1 objects into n boxes, and at least one box contains two or more objects.
Here is a simple Ramsey theorem:
Let p and q be positive integers, p, q >；; = 2, there is a minimum positive integer R(p, q), so that when n >；; When =R(p, q), if the edges of Kn are painted red and blue, there is either a blue complete P-shape or a red complete Q-shape.
Ramsey theorem has a wider scope of application, so I won't go into details here. If you are interested, you can read books on combinatorial mathematics.
It is known that N+ 1 positive integers are all less than or equal to 2n. It is proved that there must be two numbers that are coprime.
This problem was solved by the great Hungarian mathematician Paul Elder? S, 19 13- 1996) to Bossa (Louis p? Sa), and Bo Xiaosha can give the correct answer in less than half a minute, and his answer is so clever and wonderful that Erdos is amazed.
Before listing the Posada solution, students can think about the solution by themselves, and then they can deeply understand the mystery of the Posada solution.
Bosha's solution is this:
Suppose there are n boxes, put 1 and 2 in the box of 1, 3 and 4 in the second box, 5 and 6 in the third box, ..., 2n- 1 and 2n in the nth box.
If n+ 1 numbers are randomly selected from these n boxes, two numbers of at least one box will be selected. Therefore, there must be a pair of continuous numbers in this number n+ 1. Obviously, these two continuous numbers are coprime.
This problem is so easy to solve!
To clarify the above problems in a relatively shallow way, we can say:
For a six-story loft with four spaces on each floor, it has 6 4 = 24 lofts. Now put 25 pigeons in the pigeon house, and you will definitely see two pigeons crowded together in one of the pigeon houses!
* coprime: let a and b be positive integers. If the greatest common factor of A and B is 1, A and B are coprime.
First of all, the story of a Hungarian mathematician.
Louis Pósa is a young mathematician in Hungary. 1988 He was about 40 years old. /kloc-at the age of 0/4, he was able to publish a mathematical paper with considerable depth. Before graduating from college, he was awarded the title of doctor of science.
His mother is a mathematician. He was influenced by his mother when he was a child and loved to think. Mother saw that he was interested in mathematics and encouraged him to develop in this field. She gave him some math games or toys to inspire him to think independently. Under the guidance of his mother, he taught himself high school math books when he was in primary school. It was the famous Hungarian mathematician who really trained him as a mathematician.
Ordos has deep research in the fields of number theory, graph theory and other branches of mathematics. He devoted himself to mathematics all his life, never wanted to get married, and only stayed with his mother. He often leaves his motherland to do research and give lectures abroad. Not many mathematicians in eastern European countries can leave their own countries and enter and leave the western world at will like Ordos. He made friends in mathematics everywhere, and his prolificacy in mathematics and ingenious methods of solving problems made him enjoy a high reputation in mathematics. For his motherland, his important contribution is not only in the study of mathematics. As soon as he returned to his own country, he devoted himself to training the younger generation of mathematicians, telling them the problems that foreign mathematicians are concerned about at present and expanding their horizons.
I want to tell the story of how he discovered Louis Posa's talent.
Once when he came back from abroad, he heard a friend talk about a clever little thing that could solve many math problems in primary schools, so he went to the child's house.
Posa's family is happy to invite Professor Erdos to dinner. When drinking soup, Ordos wanted to test the ability of the 12-year-old child sitting next to him, so he asked him such a question:
"If you have n+ 1 integers on hand, and these integers are less than or equal to 2n, then you must have a pair of numbers that are coprime. Do you know why? "
The child thought for less than half a minute and soon gave the answer to this question. His answer was so clever that Professor Erdos was amazed. I think this is a rare "gift" and should be cultivated well.
Less than two years after Erdos systematically taught the child mathematics, Posa became a "little mathematician" and discovered some profound theorems in graph theory.
Second, how does Posa solve the problem of Erdusti?
For many readers who have left school for a long time, I want to explain the questions raised by Erdos.
First of all, let's explain: what does a pair of numbers mean by coprime?
We know that if natural numbers 1, 2, 3, 4, 5, … are arranged in order of size, starting from 2, like 2, 3, 5, 7,1,13, 17,/.
Numbers with this special property are called prime numbers.
Didn't our primary school learn to decompose integer factors? That is, the product of prime numbers is used to represent an integer. For example, 50 = 2× 5× 5, 108 = 2× 2× 3× 3× 3.
Two natural numbers are called coprime. If they are expressed as the product of prime numbers, they cannot be found to have a common prime factor. For example, {8, 1 1} is a logarithm coprime. 10 and 108 are not coprime because they have a common prime factor of 2.
Now let's understand the problems in Ordos. First consider some special cases:
When n=2, we have three integers less than or equal to 4, and we can only choose {2,3,4}, excluding 1. Obviously, {2,3} or {3,4} are coprime.
When n=3, find four integer groups (excluding 1) among integers less than or equal to 6, which may be {2, 3, 4, 5}, {2, 3, 4, 6}, {3, 4, 5, 6}, {2, 4, 5, 6} and so on. Check them one by one, and you will find that each group has at least one pair of prime numbers.
It can be seen that with the increase of n, the number of arrays with n+ 1 different numbers will increase greatly. If we check these arrays one by one, it will really become: "My life is limited, but the number is infinite". Not only will it be inexhaustible, but it will also be "alas" in the end!
If someone in the reader says, "I have the spirit of hard work!" " "I still want to persuade him not to work so hard and learn to do it skillfully. This is the most important thing. Otherwise, other children can solve the problem in less than half a minute, and we can't solve it all our lives by hard work and diligence. Isn't this a waste of life?
Let me introduce Posa's solution to this problem now. But I hope readers can think for themselves first and see how to solve this problem. If you can find a solution different from the following, please write to me. If you still can't figure it out after a while, please read on, you will appreciate the originality of Posa's solution, and most importantly, you will learn the "pigeon coop principle", which may be used when you become an amateur mathematician or a professional mathematician in the future!
Posa considers the problem like this: take n boxes, the first box we put 1 and 2, the second box we put 3 and 4, the third box we put 5 and 6, and so on until the nth box we put 2n- 1 and 2n.
Now we randomly select n+ 1 numbers from n boxes. We saw at once that a box must have been evacuated. Therefore, two numbers in n+ 1 are continuous numbers, and obviously these two continuous numbers are coprime. So this problem is solved!
Do you think this solution is easy to understand and clever? !
Third, the principle of pigeon cage
Posa used something mathematically called the pigeon hole principle in his proof. The principle is this: If you put n+ 1 items into n boxes, some boxes must contain at least 2 items.
There are six pigeon coops with four spaces on each floor, so there are 6× 4 = 24 pigeon coops in total. Now I have put 25 pigeons in it. You must see a pigeon cage. Two pigeons will be crowded together.
The principle of pigeon coop is so simple that children over 3 years old will understand it.
However, this principle has a very important application in mathematics.
19th century, a mathematician named Dirichlet (1805- 1859) skillfully used the pigeon-cage principle to solve problems in the study of number theory. Later, the German mathematician Min Guski (Minkowski1864-1909) also obtained some results by using this principle.
At the beginning of the 20th century, Toure (A. Thue 1863- 1922) skillfully solved the problem of rational number solution of indefinite equation by using pigeon cage principle without knowing the work of Dirichlet and Min Guski, and 12 papers used this principle.
Later, Siegel (C.L.Siegel, 1896-? ) We use Toure's results to find the Siegen Lemma, which is the most basic and necessary tool to study transcendental numbers.
Therefore, readers should not underestimate this seemingly simple principle. If you are good at using it, it can help you solve some math problems.
Fourth, the daily application of pigeon coop principle
I'll give you some questions related to your daily life. You can see the application of mathematics here.
(1) Wear socks in the dark.
One night, the light in your room suddenly broke down. You couldn't see your fingers. You wanted to go out, so you touched the socks under the bed. You have three pairs of red, white and blue socks, but you usually do things casually and throw them away as soon as you take them off. You can't know which pair is the same color in the dark.
You want to take out the least socks and borrow the street lamp outside to make a pair of the same color. What should be the minimum quantity?
If you know the pigeon coop principle, you will know that you only need to take out four socks.
Why? Because if we have three boxes painted with red, white and blue, with socks of opposite colors in them, as long as we take out four socks, one of the boxes must be empty, then the socks taken out of this empty box can be worn.
(2) Fingerprints and hair
It is said that no two people in the world have the same fingerprints, so the police attach great importance to fingerprints when dealing with crimes, hoping to solve the case or verify the prisoner through fingerprints.
But did you know that in China's population of 65.438+0.2 billion, at least two people have the same amount of hair?
The reason is very simple, the number of human hair will not exceed 65.438+0.2 billion! Suppose a person has at most n hairs. Now let's imagine a house numbered 1, 2, 3, 4, … all the way to n.
Whoever has the same amount of hair will enter the house. Therefore, Mr. Zhang Leping's San Mao should be included in No.3 Hospital.
Now suppose that there is one person in each room, and there are still "900 million MINUS N" people left, which will not be equal to zero. Now, we will randomly choose one and put it in a house with the same hair as him, and he will meet his comrades with the same hair.
(3) the birthday of the theater audience
In a theater that can accommodate 1500 seats, it is proved that if the theater is full, at least five spectators must be born on the same day in the same month.
Now suppose there are 365 days in a year. Imagine a big pigeon coop with sections labeled "1 month 1 day", "1 month 2" and "1February 3 1 day".
Suppose four people are crammed into each section now, then 4×365= 1460 people enter the pigeon coop, leaving 1500- 1460=40 people. As long as someone enters dovecote, there are five people in the same Amanome.
Fifth, the application of pigeon coop principle in mathematics.
Now I want to give some mathematical problems to illustrate the application of pigeon coop principle.
A Property of Fibonacci Number (1)
Fibonacci series is such a series: 1, 1, 2, 3, 5, 8, 13, 2 1, 34, ... 1 and 1 are the first two items.
In the18th century, the French mathematician and physicist J. L. La-Grange discovered that this Fibonacci number has such interesting properties:
If you divide each term by 2 and write down its remainder, you will see 1, 1, 0, 1, 1, 1, …
If you divide each term by 3 and write down its remainder, you will get
1, 1,2,0,2,2, 1,0, 1, 1,2,0,2,2, 1,0,…
If you divide each term by 4 and write down its remainder, you will get
1, 1,2,3, 1,0, 1, 1,2,3, 1,0,…
Now observe the sequence obtained by dividing by 2. Every three paragraphs from the beginning, the following sequence repeats the previous sequence. Divide the sequence by 3, and every eight paragraphs from the beginning, the subsequent sequence will repeat the previous sequence. The same is true of the remainder series obtained by dividing by 4: every six paragraphs, the subsequent series repeats the previous series.
Lagrange found that no matter what number you divide, the remainder series will repeat regularly.
Why is this happening?
If we divide Fibonacci number by an integer k, its possible remainder is 0, 1, 2, …, k- 1.
Since each term in Fibonacci number is the sum of the first two terms, the remainder after it is divided by k is equal to the sum of the remainder of the first two terms divided by k (note: if this sum is greater than k, we will take the remainder after it is divided by k). As long as a pair of adjacent remainders appear repeatedly, the following series will appear repeatedly from that logarithm. There may be K2 pairs of different adjacent remainders, so we know that as long as the number of items is appropriately large, a pair of adjacent remainders will be repeated. Therefore, the remainder sequence of Fibonacci sequence will be repeated periodically.
(2) The positions of the five tacks in the equilateral triangle.
A regular triangle (that is, a triangle with three equilateral sides), each side is 2 units long.
If you put five tacks at random, a pair of tacks will be less than one unit apart.
If you don't believe me, you can do a few experiments to see if it has always been like this. I'll solve this problem with pigeon coop principle now.
Take the midpoint of each side of the triangle, and then connect these midpoints with line segments to divide the regular triangle into four congruent small regular triangle figures. Now the distance between any two points in each small triangle will not exceed 1 unit.
Because we have five pushpins, no matter how we put them, two of them must fall into the same small regular triangle, so the distance between the two pushpins will not exceed one unit.
Six, think about it.
(1) gives an arbitrary number 12, and proves that there must be a logarithm with the same remainder when divided by 1 1.
(2) If you randomly nail 17 to a regular triangle board with 2 units on each side.
(3) If five nails are randomly nailed to a square plate with two units on each side,
(4) We must be able to properly nail 9 nails on a square board with a length of 2 units on each side, so that there are no nails in it, and the distance between the two nails is less than 1 unit.
(5) (British Mathematical Olympiad 1975) If seven nails are nailed on a circular plate with a radius of 1, so that the distance between the two nails is greater than or equal to 1, then there must be a position of the seven nails right on the center of the circle.
(6) When any six people are together, one of two situations will definitely happen: the first situation-three people know each other. The second case-there are three people who don't know each other at all.
(7)(a) Can 1 00 natural numbers be selected from integers from1to 200, so that none of them can divide the remaining 99 numbers?
(b) Prove that if 1 01natural numbers are randomly selected from1to 200, there are at least two natural numbers, one of which can be divisible by the other.
(8) Give 10 any number of digits. Of course, we can divide it into two parts, so that the sum of integers in each part is equal to the sum of integers in other parts.
[Edit this paragraph] Simple form
If n+ 1 objects are put into n boxes, at least one box contains two or more objects.
1: 13 There are two people whose birthdays are in the same month.
Example 2: There are n married couples. In order to ensure that a couple is selected, at least how many people should be selected from these 2n people? (n+ 1)
[Edit this paragraph] Strengthen the form
Let q 1, q2, ... qn be positive integers. If you want to put it that way.
Q 1+q2+...+qn-n+ 1 objects are put into n boxes, so either the first box contains at least q1objects or the second box.
At least q2 object, ..., or the nth box contains qn object.
Example 1: There are apples, bananas and oranges in a basket of fruits. To ensure that there are at least 8 apples or at least 6 bananas or at least 9.
How many fruits should an orange put in the basket? (2 1 piece)