First, the main points of knowledge
Pigeon hole principle, also known as pigeon nest principle, is a basic principle of combinatorial mathematics, which was first explicitly put forward by German mathematician Narrow Clay, so it is also called Narrow Clay Principle.
If you put three apples in two drawers, there must be two or more apples in one drawer. This well-known common sense is the embodiment of pigeon hole principle in daily life. It can be used to solve some rather complicated and even incomprehensible problems.
Principle 1: divide n+ 1 elements into n classes. In any case, there must be two or more elements in a class.
Principle 2: put m elements into n sets (n < m = set, then there must be at least k elements in a set.
Where k = (when n is divisible by m)
[]+ 1 (when n is not divisible by m)
([] indicates the largest integer not greater than, that is, the integer part of)
Principle 3: put an infinite number of elements into a finite set, and there must be an infinite number of elements in a set.
Second, the steps to solve the problem by applying the pigeon coop principle
Step 1: Analyze the meaning of the question. Distinguish what is "thing" and what is "drawer", that is, what is "thing" and what is "drawer".
Step 2: Make drawers. This is a crucial step. This step is how to design drawers. According to the subject conditions and conclusions, combined with relevant mathematical knowledge, master the most basic quantitative relationship, design and determine the number of drawers needed for solving problems, and pave the way for the use of drawers.
Step 3: Using the observation and setting conditions of the pigeon hole principle, combined with the second step, in order to solve the problem, various principles are appropriately applied or several principles are comprehensively applied.
There are five students doing their homework in the classroom. There are only four subjects today: Mathematics, English, Chinese and Geography.
Proof: At least two of the five students are doing the same homework.
Proof: treat five students as five apples.
Math, English, Chinese and geography homework is a drawer with ***4 drawers.
According to the pigeon hole principle 1, there must be a drawer with at least two apples in it.
In other words, at least two students are doing homework in the same subject.
Example 2: There are three red balls, five yellow balls and seven blue balls in the wooden box. If you touch them blindfolded, how many balls do you have to take out to ensure that two of them are the same color?
Think of three colors as three drawers.
In order to satisfy the meaning of the question, the number of balls must be greater than 3.
The minimum number greater than 3 is 4.
So at least four balls must be taken out to meet the requirements.
Answer: Take out at least 4 balls.
There are 50 students in the class. How many books should you bring to ensure that at least one student can get two or more?
Imagine 50 students as 50 drawers and books as apples.
According to the principle of 1, there are more books than students.
That is, at least 50+ 1=5 1 book is needed.
Answer: At least 5 1 serving is required.
Example 4: Plant10/tree along a path with a length of 100 meters. No matter how you plant it, the distance between two trees will not exceed 1 meter.
Divide this path into 1m long sections, *** 100 sections.
Each segment is regarded as a drawer, *** 100 drawers, and the tree of 10 1 is regarded as10/apple.
So 10 1 apples are put into 100 drawers, and there are two apples in at least one drawer.
That is, at least one part has two or more trees.
Example 5: 1 1 Students borrow books from their teachers' homes. There are four books in the teacher's study: A, B, C and D. Each student can borrow at most two different books, at least one.
Try to prove that there must be two students borrowing the same kind of books.
Proof: if students only borrow one book, there are four different types: A, B, C and D.
If students borrow two different types of books, there are six different types: AB, AC, AD, BC, BD and CD.
* * * There are 10 species.
Think of these 10 types as 10 "drawers"
Take 1 1 student as 1 1 "Apple".
Whoever borrows any books goes into which drawer.
According to the classification principle, at least two students borrow books of the same type.
Example 6: There are 50 athletes in a single round robin event. If there is no draw, there is no complete victory.
Try to prove that there must be two athletes with the same integral.
Proof: one point per game.
Because there is no draw and no victory, the score is only 1, 2, 3...49, and there are only 49 possibilities.
Take these 49 possible scoring situations as 49 drawers.
Fifty athletes scored.
Two athletes must score the same score.
Example 7: There are many football, volleyball and basketball in the sporting goods warehouse. Fifty students from a class came to the warehouse to get the ball. It is stipulated that everyone should get at least 1 ball and at most two balls. How many students have the same kind of balls?
The key to solving the problem: using pigeon hole principle II.
According to the regulations, many students have the following nine ways to match the ball:
{ Foot } { Row } { Blue } { Full } { Row } { Blue } { Foot Row } { Foot Blue } { Row Blue }
Nine drawers are manufactured in these nine matching ways.
Think of these 50 students as apples.
=5.5……5
According to the pigeon hole principle 2k = []+ 1, there are at least six people, and they are holding the same ball.