鸽巢原理 | Baeldung中文网

1. Overview

The pigeonhole principle (also sometimes called the Dirichlet drawer principle) is a simple yet powerful idea in mathematics that can be used to show some surprising things, as we’ll see later. In this article, we’ll first define what the pigeonhole principle is, followed by some examples to illustrate how it can be applied.

Then we’ll discuss the generalized version of the principle and give several examples that use the generalized version. Finally, we’ll show some particularly clever applications that make use of the pigeonhole principle.

2. The Basic Pigeonhole Principle

In this section, we’ll first define the basic pigeonhole principle and prove it. Then we’ll show three examples that use this basic principle.

2.1. Definition and Proof

The most basic form of the principle refers to pigeons and pigeonholes. Suppose that a set of pigeons fly into a set of pigeonholes. Then if there are more pigeons than pigeonholes, there must be at least one pigeonhole that has more than one pigeon in it.

Shown below are three groups of twelve pigeonholes. Each group has thirteen pigeons (represented by the circles), so there is at least one pigeonhole in each group that has at least two pigeons.

pigeonholes

We can of course apply this principle to other things besides pigeons and pigeonholes. Formally, we can state the pigeonhole principle like this: If there are boxes and or more objects are placed into these boxes, then there is at least one box that contains two or more of the objects.

Even though the idea seems pretty obvious and almost trivial, we still need to prove that it must be true. The proof is relatively straightforward and goes like this:

Suppose by contradiction that there are boxes and n+1 or more objects are placed into these boxes, but there are no boxes with two or more of the objects. This means that every box has at most one object in it.

But if every box has at most one object in it, then there can’t be more than objects in the boxes overall. But this is a contradiction since we assumed that there are at least n+1 objects placed into the boxes!

Next, we give some examples of how the pigeonhole principle can be applied. In each example, we’ll clearly explain what objects correspond to pigeons and what objects correspond to pigeonholes.

2.2. First Example

Suppose we have a group of 27 English words. Then there must be at least two words in the group that begin with the same letter. In this case, the 27 English words are the pigeons and we can think of the pigeonholes as buckets that store words that start with a specific letter of the English alphabet.

In this case, there are 26 pigeonholes (one for each letter in the English alphabet) but 27 pigeons, so we can immediately see that there must be at least one bucket with more than one word in it. But a bucket with more than one word implies that there are at least two words that start with the same letter.

2.3. Second Example

In any group of 367 people, there must be at least two people with the same birthday. Here we can think of a person as a pigeon and a room that has all the people who have a specific birthday as a pigeonhole. Since there are only 366 possible birthdays, we have 366 rooms.

But if we put 367 people in 366 rooms, then we know that there must be at least one room with at least two people in it. This means that there must be at least two people with the same birthday.

2.4. Third Example

Let’s say we know the maximum number of hairs that a person can have on his head. Let be this number. Then in any group of more than people, there must be at least two people with the same number of hairs on their heads.

A person represents a pigeon and a room with people that have a specific number of hairs on their heads represents a pigeonhole. Since we have more people than rooms, there must be at least one room with at least two people in it.

Now the average number of hairs on a person’s head is about 100,000, so this means that the maximum is probably at most a few hundred thousand. This means that in any group of say 300,000 people, it’s guaranteed that there are at least two people with the same number of hairs on their heads!

3. The Generalized Pigeonhole Principle

Here we’ll define and prove the generalized version of the pigeonhole principle. Then we’ll see three examples that use this generalized version.

3.1. Definition and Proof

We can say even more when the number of objects is more than a multiple of the number of boxes. For example, in any set of 21 decimal digits, there must be 3 that are the same. This is because if 21 objects are put into 10 boxes, there must be at least one box with at least 3 objects in it.

We can formally express this notion as the generalized pigeonhole principle. The generalized pigeonhole principle states that if objects are placed in boxes, then there must be at least one box with at least $\lceil n/k \rceil$ objects in it. Now we’ll prove this statement.

Suppose that objects are placed into boxes, but every box contains at most $\lceil n/k \rceil - 1$ objects. Then the total number of objects is at most $k(\lceil n/k \rceil - 1)$ , but this value is less than k((n/k + 1) - 1) = n . This is because we know that $\lceil n/k \rceil < (n/k) + 1$ , so if substitute the expression in the place of $\lceil n/k \rceil$ in the expression $k(\lceil n/k \rceil - 1)$ then we’ll get which must be bigger in value.

Thus, we get a contradiction since there are objects in total.

Next, we’ll give some examples of how we can apply the generalized pigeonhole principle. In each example, we’ll clearly explain what corresponds to objects and what corresponds to boxes.

3.2. First Example

In any group of 100 people there is at least $\lceil 100/12 \rceil = 9$ who were born in the same month. Here the objects we are placing are the people and the boxes can be imagined as rooms that have people who were born in a specific month. Since we have 100 people and 12 rooms (one for each month of the year), there must be a room with at least 9 people in it.

3.3. Second Example

To guarantee that at least three cards of the same suit are chosen, we must select at least nine cards from a standard deck of 52 cards. In this case, we can think of the boxes as marked with a particular suit, and as we select cards from the deck we place them in the box with the same suit as the selected card. The generalized pigeonhole principle tells us that if cards are selected, there is at least one box containing at least $\lceil n/4 \rceil$ cards.

So if $\lceil n/4 \rceil >= 3$ then we know that at least three cards of the same suit must’ve been selected. The smallest possible value that can take for this condition to be true is 9, so that at least nine cards must be selected.

3.4. Third Example

The minimum number of students needed in a class to ensure that at least six students receive the same grade is 26 if there are five possible grades (e.g. A, B, C, D, and F). We can think of each object as a person and each box as a room with people that have a specific grade. The minimum number of students needed to satisfy the condition is equal to the smallest integer such that $\lceil n/5 \rceil = 6$ , and the smallest such integer is 26.

Shown below are two instances of this third example. In both cases, we have 5 boxes that represent the five possible grades and 26 red circles representing 26 students that are assigned some grade. In both cases, there is at least one box containing at least six red circles which means that there are at least six students who got the same grade.

grades

4. Clever Applications of the Pigeonhole Principle

In this section, we’ll discuss a couple of interesting applications of the pigeonhole principle that require a little bit more sophistication.

4.1. First Example

Among any n+1 integers such that each integer is at most , there must be an integer that divides one of the other integers. We can write each of the n+1 integers $x_{1}, x_{2}, ... , x_{n+1}$ as a power of 2 times an odd integer. So let $x_{j} = 2^{k_{j}}q_{j}$ for j = 1, 2, ..., n+1 , where $k_{j}$ is a nonnegative integer and $q_{j}$ is odd. The integers $q_{1}, q_{2}, ... , q_{n+1}$ are all odd positive integers less than .

It follows from the pigeonhole principle that two of the integers $q_{1}, q_{2}, ... , q_{n+1}$ must be equal, since there are only odd positive integers less than . So there must exist integers and such that $q_{i} = q_{j}$ . Let be the common value of $q_{i}$ and $q_{j}$ .

Then we have that $x_{i} = 2^{k_{i}}q$ and $x_{j} = 2^{k_{j}}q$ . Therefore, if $k_{i} < k_{j}$ then $x_{i}$ divides $x_{j}$ , whereas if $k_{i} > k_{j}$ , then $x_{j}$ divides $x_{i}$ .

4.2. Second Example

Suppose that there is a sports team that plays at least one game a day for 30 days, but no more than 45 games in total. Then there must be a period of some consecutive days during which the team must play exactly 14 games. We’ll now prove this statement.

Let $x_{j}$ be the number of games played on or before the th day of the 30 day period. Then $x_{1}, x_{2}, ..., x_{30}$ is an increasing sequence of distinct positive integers, with $1 <= x_{j} <= 45$ . Furthermore, $x_{1} + 14, x_{2} + 14, ..., x_{30} + 14$ is also an increasing sequence of distinct positive integers, with $15 <= x_{j} + 14 <= 59$ .

The 60 positive integers $x_{1}, x_{2}, ..., x_{30}, x_{1} + 14, x_{2} + 14, ..., x_{30}$ are all less than or equal to 59. The pigeonhole principle then tells us that two of these integers are equal. Since the integers $x_{1}, x_{2}, ..., x_{30}$ are all distinct and the integers $x_{1} + 14, x_{2} + 14, ..., x_{30} + 14$ are also all distinct, there must be indices and with $x_{i} = x_{j} + 14$ .

But this means that exactly 14 games were played from day j+1 to day .

5. Conclusion

In this article, we explored the pigeonhole principle through some definitions and examples.

First, we discussed the most basic form of the pigeonhole principle along with its proof. Then we gave some examples that make use of this basic principle.

Then we introduced the generalized version of the pigeonhole principle and proved it as well. We also saw some examples that make use of this generalized version.

Finally, we saw some more interesting applications of the pigeonhole principle. These final examples show that with a little bit more sophistication combined with the pigeonhole principle, we can prove some pretty impressive results.

Persistence

REST

Security