Welcome to the World of the Pigeonhole Principle!
In your H3 Mathematics journey, you will encounter many complex proofs. Some require pages of algebra, but others rely on a surprisingly simple idea called the Pigeonhole Principle (PHP). This principle is a powerful tool in the "Mathematical Proofs and Reasoning Principles" section of your syllabus. It allows us to prove that something must exist, even if we don't know exactly where it is!
Don’t worry if the name sounds a bit funny. By the end of these notes, you’ll see why this "obvious" concept is a secret weapon for solving some of the trickiest problems in discrete mathematics.
1. The Basic Idea: Pigeons and Holes
Imagine you have 10 pigeons, but only 9 pigeonholes for them to sleep in. If every pigeon flies into a hole, what can we say for sure?
Even if we try to spread them out as much as possible, at least one hole must contain more than one pigeon. It’s impossible to give every pigeon its own private room!
The Mathematical Statement:
If \( n + 1 \) pigeons are put into \( n \) pigeonholes, then at least one pigeonhole contains 2 or more pigeons.
A Simple Analogy:
Think about your sock drawer. If you have 3 loose socks and they are either black or blue (2 colors), at least 2 of those socks must be the same color. You’ve just used the Pigeonhole Principle!
Quick Review:
- Pigeons = The items you are counting.
- Holes = The categories or containers you are putting them into.
- The Rule = If Pigeons > Holes, then at least one hole has > 1 pigeon.
2. The Generalized Pigeonhole Principle
Sometimes, we have a lot more pigeons than holes. For example, what if we have 21 pigeons and only 10 holes?
If we distribute them as evenly as possible, each hole would get 2 pigeons, with 1 pigeon left over. That 1 extra pigeon must go into a hole that already has 2, meaning at least one hole will have 3 pigeons.
The Formula:
If \( N \) objects are placed into \( k \) boxes, then at least one box contains at least \( \lceil N/k \rceil \) objects.
Note: The symbol \( \lceil x \rceil \) is the ceiling function. It means "round up to the nearest whole number." For example, \( \lceil 2.1 \rceil = 3 \).
Step-by-Step Example:
Suppose there are 50 people in a room. How many people must share the same day of the week for their birthday?
1. Identify the Pigeons: \( N = 50 \) (the people).
2. Identify the Holes: \( k = 7 \) (the days of the week).
3. Calculate: \( 50 / 7 \approx 7.14 \).
4. Round up: \( \lceil 7.14 \rceil = 8 \).
Conclusion: At least 8 people were born on the same day of the week.
3. How to Approach a PHP Problem
Struggling to start? Don't worry! Most PHP problems follow a similar pattern. When you see a question asking you to "Prove that there exists..." or "Show that at least...", follow these steps:
Step 1: Identify the "Pigeons"
What are the things you are distributing? These are usually the larger group of items (numbers, people, points).
Step 2: Identify the "Holes"
What are the categories? This is often the trickiest part. You might need to create "boxes" based on remainders, ranges of numbers, or geometric areas.
Step 3: Apply the Principle
Show that because the number of pigeons is greater than the number of holes (or a multiple of the holes), the conclusion must follow.
Key Takeaway: The Pigeonhole Principle is a non-constructive proof. It tells us that a certain situation must exist, but it doesn't tell us which hole has the extra pigeons!
4. Common Applications and Examples
Example 1: Birthdays
In a group of 13 people, at least two must have been born in the same month.
(Pigeons = 13 people, Holes = 12 months. Since 13 > 12, the result follows.)
Example 2: Number Theory (Remainders)
Prove that if you pick 6 integers, at least two of them will have the same remainder when divided by 5.
(Pigeons = 6 integers, Holes = possible remainders when dividing by 5, which are {0, 1, 2, 3, 4}. Since there are 6 numbers and only 5 possible remainders, two numbers must share a remainder.)
Did you know?
This principle is also known as Dirichlet's Box Principle, named after the German mathematician Peter Gustav Lejeune Dirichlet who formalized it in 1834.
5. Common Mistakes to Avoid
1. Mixing up Pigeons and Holes: Always make sure your "Pigeons" are the items being distributed and your "Holes" are the containers. If you get them backwards, the math won't work!
2. Forgetting to round up: In the generalized version, always use the ceiling function. Even if the division results in \( 2.01 \), the answer is 3.
3. Thinking you found the specific hole: PHP only proves existence. If you say "The third hole must have two pigeons," you are likely over-stepping. You can only say "At least one hole has two pigeons."
Summary Checklist
- Basic PHP: \( n+1 \) items in \( n \) boxes \( \rightarrow \) at least one box has \( \ge 2 \) items.
- Generalized PHP: \( N \) items in \( k \) boxes \( \rightarrow \) at least one box has \( \ge \lceil N/k \rceil \) items.
- Prerequisite: Always identify your pigeons and holes clearly before writing your proof.
- Goal: Use this to prove existence in combinatorial and number theory problems.
Keep practicing! At first, identifying the "holes" can feel like a riddle, but with a bit of experience, you'll start seeing pigeonholes everywhere!