[combinatorial mathematics] pigeon's nest principle (simple form of pigeon's nest principle | simple form examples of pigeon's nest principle 1, 2, 3)

One 、 Pigeon nest principle simple form

---

Pigeon nest principle :

take

n

+

1

n + 1

n+1 An object Put it in

n

n

n Boxes in , be

There must be a box in At least contain

2

2

2 individual or

2

2

2 More than objects ;

Pigeon nest principle It's actually Many to few configuration ; There is at least one many to one situation ;

Two 、 Example of simple form of pigeon nest principle 1

---

prove : The side length is

2

2

2 In the regular triangle of , Yes

5

5

5 A little bit , There must be two points whose distance is less than

1

1

1 ;

Will become

2

2

2 An equilateral triangle , It is divided into

4

4

4 A small equilateral triangle , The length of each side is

1

1

1 ; Here's the picture :

stay

4

4

4 In a small square , draw

5

5

5 A little bit ;

According to the pigeon nest principle , The above question can be turned into take

5

5

5 Put an object into

4

4

4 In a box , At least one box contains

2

2

2 individual or

2

2

2 More than objects ;

In an equilateral triangle lattice , If you draw two points , The distance must be less than

1

1

1 ;

3、 ... and 、 Example of simple form of pigeon nest principle 2

---

prove :

9

×

3

9\times3

9×3 Of the lattice , Use black , white Paint in two colors , There must be two identical coloring schemes ;

First enumerate the possible coloring schemes : There can only exist

2

3

=

8

2^3 = 8

23=8 Possible coloring schemes ;

stay

9

9

9 In the column square , Use

8

8

8 Paint in three modes ;

It can be understood equivalently as the pigeon nest principle : take

9

9

9 Put an object in

8

8

8 In a box , be At least one box contains

2

2

2 individual or

2

2

2 More than objects ;

So at least there is

2

2

2 Column or

2

2

2 The grid above the column will be painted in one color ;

Four 、 Example of simple form of pigeon nest principle 3

---

prove : There is... In the space

9

9

9 Grid points , The midpoint of all the lines between two points , There is a grid ;

Lattice points refer to integer points ;

The midpoint of the line is the requirement of the grid : Spatial coordinates

(

x

,

y

,

z

)

(x,y,z)

(x,y,z) And

(

x

′

,

y

′

,

z

′

)

(x' , y' , z')

(x′,y′,z′) Have the same parity , namely

• $x,x^{\prime }$
• $y,y^{\prime }$
• $z,z^{\prime }$

At this time, the midpoint of the line between these two spatial coordinates is Grid point , That is, integer point ;

Next, it is analyzed that the parity of the three coordinates is the same , The reason why the midpoint is the grid point :

The coordinate formula of the midpoint of the line is :

(

x

+

x

′

2

,

y

+

y

′

2

,

z

+

z

′

2

)

( \dfrac{x + x'}{2} , \dfrac{y + y'}{2} , \dfrac{z + z'}{2} )

(2x+x′​,2y+y′​,2z+z′​)

When parity is the same , The three numbers of the spatial coordinates of the midpoint of the line are all integers ;

Spatial coordinates

(

x

,

y

,

z

)

(x,y,z)

(x,y,z) And

(

x

′

,

y

′

,

z

′

)

(x' , y' , z')

(x′,y′,z′) The parity modes of are

2

3

=

8

2^3 = 8

23=8 Kind of ; Namely

• The first $1$
• The first $2$
• The first $3$

There are two cases for each of the above coordinates , The three coordinates are

2

×

2

×

2

=

8

2 \times 2 \times 2 = 8

2×2×2=8 In this case , This is the principle of multiplication ;

In the space

9

9

9 Grid points , The parity pattern of each lattice point has

8

8

8 Kind of ;

It can be understood equivalently as the pigeon nest principle : take

9

9

9 Put an object in

8

8

8 In a box , be At least one box contains

2

2

2 individual or

2

2

2 More than objects ;

So at least there is

2

2

2 Or

2

2

2 The parity pattern of more than lattice points is the same ;

therefore :

2

2

2 The midpoint connected by lattice points with the same parity pattern , It must be grid point ;