29-04 — Proof by Cases and Pigeonhole Arguments

Phase: 29 — Proof Techniques Subject: 29-04 Prerequisites: 29-01 (Direct Proof), 29-02 (Proof by Contradiction), 26-05 (Pigeonhole Principle) Next subject: 29-05 — Reading and Writing Proofs

Learning Objectives

By the end of this subject, you will be able to:

1. Structure a proof by cases (exhaustive case analysis)
2. Apply the pigeonhole principle in counting and existence proofs
3. Combine case analysis with contradiction and contrapositive
4. Use the extremal principle (choose the largest/smallest element)
5. Recognise when case analysis is the most natural proof strategy

Core Content

1. Proof by Cases (Exhaustive Case Analysis)

Proof by cases splits a statement into multiple mutually exclusive scenarios and proves each separately.

Template:

We prove P(x) for all x by considering all possible cases.

Case 1: [Condition A]
[Prove P(x) for x satisfying A]

Case 2: [Condition B]
[Prove P(x) for x satisfying B]

...

Since every x satisfies exactly one of these cases, P(x) holds for all x. ∎

Key requirements: - Cases must be exhaustive (cover all possibilities) - Cases must be mutually exclusive (no overlap) - Each case must be proved independently

2. The Pigeonhole Principle

Basic form: If $n$ items are placed into $m$ containers and $n > m$, then at least one container holds more than one item.

Generalised form: If $n$ items are placed into $m$ containers, at least one container holds at least $\lceil n/m \rceil$ items.

Why it's powerful: It converts counting into existence statements — "there must exist..." without constructing the object.

3. The Extremal Principle

The extremal principle says: "Consider the largest/smallest/best/worst element." This extremal element often has special properties that make the proof easier.

Template:

Among all objects satisfying [condition], choose one with the [maximum/minimum] [property].
[Show this extremal object has a contradiction or special structure]

Example: In any finite set of points in the plane, not all on a line, there is a line through exactly two points. Choose the pair of points with the smallest distance. The line through them cannot contain a third point (otherwise that point would be closer to one of them).

4. Combining Techniques

Case analysis works well with: - Contradiction: Assume $P$ is false, derive contradictions in each case - Contrapositive: Prove $\neg Q \implies \neg P$ by cases on $\neg Q$ - Pigeonhole: Use cases to define the "pigeonholes"

Worked Examples

Example 1: Pigeonhole — Birthday Problem

Problem: Show that among 13 people, at least two were born in the same month.

Solution:

13 people (pigeons) into 12 months (pigeonholes). Since $13 > 12$, by the pigeonhole principle, at least one month contains at least $\lceil 13/12 \rceil = 2$ people.

Answer: At least two people share a birth month.

Example 2: Case Analysis — Absolute Value

Problem: Prove that for all real $x$, $|x| \geq 0$ and $|x| = 0 \iff x = 0$.

Solution:

By definition: $|x| = x$ if $x \geq 0$, and $|x| = -x$ if $x < 0$.

Case 1: $x > 0$. Then $|x| = x > 0$. ✓ Case 2: $x = 0$. Then $|x| = 0$ by either definition. ✓ Case 3: $x < 0$. Then $|x| = -x > 0$ (since $x < 0$ implies $-x > 0$). ✓

All cases give $|x| \geq 0$. For $|x| = 0$: - If $x \geq 0$: $|x| = x = 0 \implies x = 0$. - If $x < 0$: $|x| = -x > 0$, so $|x| \neq 0$.

Thus $|x| = 0 \iff x = 0$. ∎

Example 3: Extremal Principle — Convex Hull

Problem: Prove that any set of $n \geq 3$ points in the plane, not all collinear, has at least three points that form a triangle containing no other points of the set in its interior.

Solution:

Consider all triangles formed by triples of points from the set. Choose one with the smallest area (exists since finite set).

Claim: This triangle contains no other points of the set in its interior.

Proof: Suppose some point $P$ of the set lies inside this minimum-area triangle $ABC$. Then $P$ divides $ABC$ into three smaller triangles $PAB, PBC, PCA$, each with area less than $\text{Area}(ABC)$. But each of these triangles has vertices from our set, contradicting the minimality of $\text{Area}(ABC)$.

Answer: By the extremal principle (minimum area), such a triangle exists.

Practice Problems

Problem 1: Use the pigeonhole principle to show that among any 10 positive integers, there exist two whose difference is divisible by 9.

Problem 2: Prove by cases: For any integer $n$, $n^2 \equiv 0$ or $1 \pmod{4}$.

Problem 3: Use the extremal principle: In any group of $n$ people, there are two people with the same number of friends in the group.

Problem 4: Prove by cases: For all real $x, y$, $|x - y| \leq |x| + |y|$ (triangle inequality for real numbers).

Problem 5: Show that among any 52 integers, there exist two with the same last digit.

Summary

1. Proof by cases exhausts all mutually exclusive possibilities and proves the statement in each
2. Pigeonhole principle converts "more items than containers" into "some container has multiple items"
3. Extremal principle picks the largest/smallest element to exploit its special properties
4. Case analysis combines naturally with contradiction and contrapositive
5. These techniques are essential for combinatorics, graph theory, and existence proofs

Key Terms

• Case analysis
• Exhaustive cases
• Extremal principle
• Mutually exclusive
• Pigeonhole principle

Pitfalls

Quiz

1. Overlapping cases. Cases should be mutually exclusive and collectively exhaustive (MECE). If cases overlap, you're double-counting or missing edge cases.
2. Missing the 'extreme' case. Pigeonhole proofs often fail because the edge case (e.g., n-1 pigeons in n holes) is overlooked. Test boundaries.
3. Counting holes incorrectly. The pigeonhole principle says: if n items into m containers and n > m, then at least one container has ≥ 2 items. Don't confuse n and m.
4. Using pigeonhole when a direct construction works. Sometimes the extremal principle (construct the worst case) is cleaner than pigeonhole.
5. Forgetting to prove the bound is tight. Saying 'at least 2' is true, but can you achieve exactly 2? If not, the bound might be loose. Prove tightness when relevant.
6. Confusing ordered and unordered cases. When splitting into cases, be clear whether order matters. 'Case 1: x is even' is different from 'Case 1: x is the smallest element'.

Q1: A proof by cases requires:

A) Only one case B) Cases that are exhaustive and mutually exclusive C) Exactly three cases D) Cases that all lead to the same contradiction

Correct: B)

• If you chose B: Correct. Exhaustive (cover all possibilities) and mutually exclusive (no overlap) are the two requirements.
• If you chose A: One case is just a regular proof. Cases are for when the statement splits into scenarios.
• If you chose C: The number of cases depends on the problem, not a fixed requirement.
• If you chose D: Cases don't need to lead to contradiction — they each prove the statement directly.

Q2: The pigeonhole principle states that if $n$ items are in $m$ containers with $n > m$:

A) Every container has at least one item B) At least one container has more than one item C) Exactly one container is empty D) All containers have the same number of items

Correct: B)

• If you chose B: Correct. This is the basic pigeonhole principle: more pigeons than holes means at least one hole has $\geq 2$ pigeons.
• If you chose A: Not necessarily. With $n = 5, m = 3$, we could have distribution $(3, 1, 1)$ — one container empty.
• If you chose C: Not necessarily. With $n = 5, m = 3$, we could have $(2, 2, 1)$ — no empty containers.
• If you chose D: Equal distribution is the exception, not guaranteed.

Q3: The generalised pigeonhole principle says that with $n$ items in $m$ containers, some container has at least:

A) $n/m$ items B) $\lceil n/m \rceil$ items C) $n - m$ items D) $m/n$ items

Correct: B)

• If you chose B: Correct. $\lceil n/m \rceil$ is the ceiling function (round up). This guarantees at least this many items in some container.
• If you chose A: $n/m$ might not be an integer. With 10 items in 3 containers, $10/3 \approx 3.33$, but we need at least $\lceil 3.33 \rceil = 4$.
• If you chose C: $n - m$ is too large. With 10 items in 3 containers, $n-m = 7$, but we only guarantee $\geq 4$.
• If you chose D: $m/n$ is usually less than 1, which doesn't make sense for "at least" items.

Q4: The extremal principle is useful because:

A) It always gives the answer directly B) The extremal element (largest/smallest) often has special properties that simplify the proof C) It avoids the need for any proof D) It only works for finite sets

Correct: B)

• If you chose B: Correct. Choosing the minimum/maximum/smallest element often reveals a contradiction or special structure.
• If you chose A: It doesn't always give the answer directly — it's a proof strategy, not an algorithm.
• If you chose C: The extremal principle IS a proof technique. It doesn't avoid proof; it provides a starting point.
• If you chose D: It works for infinite sets too, though you need additional argument that the extremum exists.

Q5: In the extremal principle proof that "among $n$ people there are two with the same number of friends," the "extremal" element is:

A) The person with the most friends B) The person with the fewest friends C) The total number of friendships D) Any person chosen arbitrarily

Correct: B)

• If you chose B: Correct. Choosing the person with the fewest friends (say $k$ friends) — if $k = 0$, done. If $k > 0$, that person's friends each have at least 1 friend (the chosen person), and by counting, someone must have the same count.
• If you chose A: The person with the most friends doesn't directly lead to the pigeonhole argument.
• If you chose C: The total is not an "extremal element" in the required sense.
• If you chose D: Arbitrary choice doesn't exploit the extremal structure needed.

Q6: For the statement "any $n \geq 3$ non-collinear points contain a triangle with no interior points," the extremal principle uses:

A) The triangle with the largest area B) The triangle with the smallest area C) The triangle with the most vertices D) Any triangle containing points

Correct: B)

• If you chose B: Correct. Choosing the minimum-area triangle and showing it contains no interior points is the key insight.
• If you chose A: The largest-area triangle might contain many interior points. We need the smallest.
• If you chose C: All triangles have 3 vertices. This doesn't distinguish them.
• If you chose D: We need to PROVE that such a triangle exists, not assume it.

Q7: To prove $n^2 \equiv 0$ or $1 \pmod{4}$ for all integers $n$, we use cases based on:

A) Whether $n$ is prime or composite B) Whether $n$ is even or odd C) Whether $n > 0$ or $n < 0$ D) The number of digits in $n$

Correct: B)

• If you chose B: Correct. Every integer is either even ($n = 2k$) or odd ($n = 2k+1$). These are exhaustive and mutually exclusive cases.
• If you chose A: Primality doesn't determine $n^2 \mod 4$. $2$ (prime) gives $4 \equiv 0$, $3$ (prime) gives $9 \equiv 1$.
• If you chose C: Sign doesn't matter: $(-n)^2 = n^2$. Positive and negative give the same result.
• If you chose D: The number of digits is irrelevant to modular arithmetic.

Q8: Which proof technique is most natural for "there exist two people with the same number of friends"?

A) Direct proof B) Proof by contradiction C) Pigeonhole principle D) Mathematical induction

Correct: C)

• If you chose C: Correct. This is a direct application of the pigeonhole principle: $n$ people into $n$ possible friend counts (0 to $n-1$), but the extremes make the count effectively $n-1$ holes.
• If you chose A: Direct proof is possible but requires careful counting. Pigeonhole is the elegant approach.
• If you chose B: Contradiction can work (assume all have different friend counts, derive that someone has $n-1$ friends and someone has 0, contradiction). But pigeonhole is cleaner.
• If you chose D: Induction isn't the natural tool for existence statements about finite sets.

Next Steps

Continue to 29-05 — Reading and Writing Proofs to consolidate all proof techniques and learn how to read, structure, and write complete mathematical proofs.