Generalized Pigeonhole Principle Applications

From "At Least Two" to "At Least How Many?"

The basic Pigeonhole Principle is a special case of a more general rule. What if we have many more pigeons than pigeonholes? It seems intuitive that some holes must be very crowded. The Generalized Pigeonhole Principle (GPHP) makes this idea precise.

The Generalized Pigeonhole Principle: If you place $N$ objects (pigeons) into $k$ boxes (pigeonholes), then there is at least one box containing at least $\lceil N/k\rceil$ objects.

The symbol $\lceil x\rceil$ is the ceiling function, which means "round $x$ up to the nearest integer." For example, $\lceil 3.14\rceil =4$ and $\lceil 5\rceil =5$.

Let's watch a short video that introduces this formula and demonstrates it with a clear example.

As the video showed, if you have 50 people ($N=50$) and 12 months ($k=12$), at least one month must have $\lceil 50/12\rceil =\lceil \mathrm{4.166...}\rceil =5$ people's birthdays. The basic principle only guaranteed 2!

A Deeper View: The Principle of Averages

The GPHP is deeply connected to the concept of averages. Thinking about it this way often provides a more profound insight, especially in complex problems.

If you have $N$ pigeons in $k$ holes, the average number of pigeons per hole is simply $N/k$. It's a fundamental statistical truth that in any set of numbers, at least one number must be greater than or equal to the average, and at least one must be less than or equal to the average.

Since the number of pigeons in a hole must be an integer, if the average is $N/k$, there must be at least one hole with at least $\lceil N/k\rceil$ pigeons.

The following reading formalizes this powerful connection.

Common Application: Working Backwards

A frequent task in combinatorics is to determine the minimum number of items needed to guarantee a certain outcome. For instance, "What is the minimum number of students required to ensure at least 3 get the same grade?" This involves using the GPHP in reverse.

The logic is to consider the "worst-case scenario" — the situation just before the guarantee is met. If we want to guarantee $m$ items in one of $k$ boxes, the worst case is that every box contains $m-1$ items. This accounts for $k\times (m-1)$ items. The very next item we add, the $(k\times (m-1)+1)$-th item, has nowhere to go but into a box that already has $m-1$ items, thus satisfying our condition.

So, the minimum number of pigeons needed to guarantee at least $m$ pigeons in one of $k$ holes is $N=k(m-1)+1$.

Let's see this logic applied to a concrete problem.

Practice Problems

Now it's your turn to apply the Generalized Pigeonhole Principle. Remember to first identify the pigeons and the pigeonholes.

1. Remainders: Among any 100 integers, prove that there are at least 3 that have the same remainder when divided by 37. What is the exact minimum number guaranteed by the GPHP?

2. Geometric Dots (Revisited): In the previous lesson, you proved that if 5 points are placed in an equilateral triangle of side length 1, two points are within $\frac{1}{2}$ unit of each other. Now, let's try a problem that requires the generalized principle.

   • Problem: 17 points are placed arbitrarily inside a 4x4 square. Prove that there must be two points whose distance is at most $\sqrt{2}$.
   • Hint: How can you divide the 4x4 square into identical smaller regions (pigeonholes) such that the maximum distance between any two points within a single region is $\sqrt{2}$?

   If you get stuck on the geometric problem, the following video segment solves a very similar problem. The logic of dividing the area into pigeonholes is key.

3. Olympiad Challenge: Ten students solved a total of 35 problems in a math competition. Each problem was solved by exactly one student. We know that at least one student solved exactly 1 problem, at least one student solved exactly 2 problems, and at least one student solved exactly 3 problems. Prove that there is also at least one student who has solved at least 5 problems.

   • Hint: This is a classic "average principle" problem. Consider the students whose problem counts are not specified. How many problems are left for them to solve?

   If you need a further hint, the resource below contains the problem statement and a starting point.

Conclusion

In this lesson, we have extended the basic Pigeonhole Principle into a more powerful quantitative tool. By understanding the formula and its connection to averages, you can now prove much stronger claims about distributions—a critical skill for advanced combinatorics.

Key Takeaways:

• The Generalized Pigeonhole Principle (GPHP) states that if $N$ items are placed into $k$ boxes, at least one box must contain at least $\lceil N/k\rceil$ items.
• The GPHP can be understood as a consequence of the principle of averages: at least one category must contain a number of items greater than or equal to the average.
• A common problem type involves "working backwards" to find the minimum number of items, $N$, needed to guarantee $m$ items in one of $k$ categories. The formula is $N=k(m-1)+1$.

In our next lesson, we will continue our exploration of the Pigeonhole Principle, focusing specifically on its many beautiful and surprising applications within number theory, building on the comfort you already have with concepts like divisibility and remainders.