Pigeon hole principle does not introduce knowledge to students in primary school mathematics textbooks, but it is an important thinking method for us to solve mathematical problems.

Pigeon hole principle was first discovered by German mathematician Dirichlet, so it is also called Dirichlet overlapping principle.

Let's learn the principle of pigeon cage together.

Typical example

1.？ The first pigeon coop principle: put an object into N drawers, and there must be at least one object in each drawer.

For example, if you put three apples in two drawers, there must be two apples in one drawer.

2.？ If you put five apples in six drawers, there must be an empty drawer. This is the so-called second pigeon coop principle: if you put an object in n drawers, there must be at most one object in one drawer.

3.？ Construction method of drawer:

When we use the pigeon hole principle to solve mathematical problems, the key is how to think of the numbers in the topic as apples and drawers, so constructing drawers is the key to solve the problem. Below we will introduce the common thinking methods of constructing "drawers" through examples.

Example 1. Constructing drawers with "digital grouping method"

Choose 5 1, ..., 100 from1,2, 3, and prove that there must be: (1)2 among these 5 1 numbers; (2) The difference between two numbers is 50; (3)8 numbers, the greatest common divisor of which is greater than 1.

Analysis and answer:

(1) Divide 100 into 50 groups.

{ 1,2},{3,4},……,{99, 100}。

In the selection of 5 1, there must be two numbers belonging to the same group. The two numbers in this group are adjacent integers, and they must be coprime.

(2) We can divide the number 100 into the following 50 groups:

{ 1,5 1},{2,52},……,{50, 100}。

In the selection of 5 1, there must be two numbers belonging to the same group, and the difference between the two numbers in this group is 50.

(3) Divide the number of 100 into five groups (one number can be in different groups):

The first group: multiples of 2, namely {2, 4, ..., 100};

The second group: multiples of 3, namely {3, 6, ..., 99};

Group III: multiples of 5, namely {5, 10, ..., 100};

The fourth group: multiples of 7, namely {7, 14, ..., 98};

The fifth group: 1 and prime numbers greater than 7, namely {1, 1 1, 13, ..., 97}.

There are 22 * * * in the fifth group, so at least 29 of the selected 5 1 numbers are in the first to fourth groups. According to the drawer, from the first group to the fourth group, there are always 8 numbers in a certain group, and the greatest common divisor of these 8 numbers is greater than 1.