Combinatorics — MGU Mathematics Series
Part III: Advanced Counting and Combinatorial Proof
Pigeonhole · Existence · Ramsey · Remainders · Geometry · Graphs
Chapter 8 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 8:
Pigeonhole Principle
and Existence Arguments

Proving that something must exist without finding it — the pigeonhole principle, guaranteed minima, remainder arguments, geometry, graphs, and Ramsey-type thinking

■ Part III: Advanced Counting and Combinatorial Proof ■

■ 14 Sections  •  Chapter 8 of 14 ■

Follows Chapter 7: Inclusion-Exclusion  ·  Prepares students for Chapter 9: Combinatorial Identities and Proof

Chapter 8 — Front Matter

Purpose and Overview

This chapter introduces a powerful and elegant idea in combinatorics: sometimes you can prove that something must exist, without ever finding it or constructing it directly. The tool that makes this possible is the Pigeonhole Principle, and the broader framework it belongs to is called an existence argument.

Most of the counting work in earlier chapters asked: how many arrangements, selections, or distributions are there? This chapter asks a different kind of question: must a certain pattern or structure occur, given that enough objects are present? These are not counting problems in the ordinary sense. They are reasoning problems about what is unavoidable when objects are distributed across a limited number of categories.

The Pigeonhole Principle is deceptively simple to state but surprisingly deep in application. It can resolve problems in number theory, geometry, graph theory, scheduling, data science, cryptography, and algorithm design. Learning to recognize when a pigeonhole argument applies, and how to structure one correctly, is an important step toward mathematical maturity and proof readiness.

Opening Question

Suppose thirteen people are gathered in a room. Is it guaranteed that at least two of them share a birth month? There are twelve months in a year. If we think of each month as a "box" and each person as an "object" being placed into one of those boxes, then distributing thirteen objects across twelve boxes forces at least one box to hold at least two objects. So yes: it is guaranteed. We do not need to know who the people are or which month each person was born in. The guarantee comes entirely from the numbers. This is the Pigeonhole Principle at work.

14Sections
9Objectives
12Key Terms
15+Worked Examples

Learning Objectives

  1. 1Distinguish between existence arguments and exact-count arguments.
  2. 2State the basic Pigeonhole Principle precisely.
  3. 3State the Generalized Pigeonhole Principle and compute minimum guaranteed outcomes.
  4. 4Identify the pigeons, boxes, and conclusion in a pigeonhole argument.
  5. 5Apply the Pigeonhole Principle to problems in integers, remainders, geometry, and graphs.
  6. 6Construct complete, clearly written pigeonhole proofs.
  7. 7Recognize the limits of pigeonhole arguments and identify common structural mistakes.
  8. 8Understand the basic ideas behind Ramsey-type thinking.
  9. 9Identify settings in computing and data where existence arguments matter.
Chapter 8 — Contents

Sections at a Glance

Sections 8.1 – 8.2
Existence Arguments and the Basic Pigeonhole Principle
What Existence Means · The Principle Stated · Proof · Pigeons and Boxes
Section 8.1

What an Existence Argument Is

Most problems in mathematics ask you to find something, compute something, or count something. Existence arguments are different. An existence argument answers the question: must a certain object, relationship, or pattern exist, under given conditions?

Notice the word must. An existence argument is not a probability claim. It does not say that something is likely or possible. It says that something is inevitable — that no matter how the objects are arranged, the condition is forced to occur. This is a strong claim. To support it, an existence argument must work for every possible arrangement, not just a convenient one. The argument must show that the conclusion holds universally, regardless of the specific details.

Existence Is Not the Same as Construction

When you prove that something exists, you do not have to produce it. A proof by existence says: the structure must be there, because the conditions force it. But the proof does not name the structure, locate it, or build it. This might feel incomplete at first. In many mathematical settings, we want to find the answer, not just prove it exists. But existence arguments are genuinely useful, and often unavoidable. In algorithm analysis, for instance, proving that a collision must exist in a hash table does not require finding the two inputs that collide — it only requires knowing that the number of possible inputs exceeds the number of possible hash values.

Key Distinction

Existence arguments establish facts about what must be true. Construction gives you the specific witness. Both are valuable, but they are not the same. A well-written existence argument is a complete proof, even if it never names the object it claims exists.

Section 8.2

The Basic Pigeonhole Principle

The Pigeonhole Principle is named after a very simple physical picture: imagine a wall of pigeonholes — the small compartments used in old post offices or dovecotes to sort letters or house birds. If there are more pigeons than there are holes, at least one hole must contain more than one pigeon. That is the entire idea. The mathematics makes it precise.

Pigeonhole Principle

If n + 1 or more objects are distributed into n boxes, then at least one box contains at least two objects.

Equivalently: if there are more objects than boxes, and every object goes into exactly one box, then some box must receive at least two objects.

Proof by Contradiction

Proof
Suppose the objects are distributed across n boxes, and suppose for the sake of contradiction that every box contains at most one object. Then the total number of objects is at most n · 1 = n. But we assumed there are at least n + 1 objects. This is a contradiction. Therefore, at least one box must contain at least two objects.
□

Identifying Pigeons and Boxes

To use the Pigeonhole Principle, you must clearly identify the pigeons (the objects being distributed), the boxes (the categories they are placed into), the distribution rule (the rule assigning each pigeon to exactly one box), and the conclusion (what is guaranteed to exist in at least one box). The distribution rule is often implicit in the problem. Making it explicit is part of setting up the argument correctly.

Important Limit

The Pigeonhole Principle guarantees that at least one box contains at least two objects, but it does not say which box that is. The guarantee is about existence, not location. In many applications, that is exactly enough.

Example 8.2.1
Birth months in a classroom
  • ProblemA classroom has 13 students. Prove that at least two students share a birth month.
  • Represent Pigeons: 13 students
    Boxes: 12 birth months (January through December)
    Distribution rule: each student is placed in the box corresponding to their birth month
  • ProveThere are 13 students and 12 birth months. Since 13 > 12, by the Pigeonhole Principle, at least one birth month must contain at least 2 students.
  • CheckThe argument holds regardless of which months the students were born in. No assumption about the specific students is needed.
  • InterpretIn any group of 13 people, at least two must share a birth month. This is not a probability — it is a certainty.
Example 8.2.2
Socks in the dark
  • ProblemA drawer contains 10 red socks and 10 blue socks. How many socks must you draw in the dark to guarantee a matching pair?
  • RepresentPigeons: socks drawn   Boxes: 2 colors (red, blue)   Guarantee needed: at least 2 socks in one box
  • ProveWith 2 boxes (colors), the Pigeonhole Principle says that as soon as you have 2 + 1 = 3 socks, at least two must share a color. With 2 socks, it is possible to have one red and one blue. With 3 socks, a match is guaranteed.
  • InterpretDrawing 3 socks guarantees a matching pair. This answer does not depend on luck or order of drawing.
Answer: 3 socks
Example 8.2.3
Handshakes at a party
  • ProblemSeven people are at a party. Each person can shake hands with any number of the other 6. Prove that at least two people shook hands with the same number of people.
  • ThinkEach person's handshake count is a number from 0 to 6. But 0 and 6 cannot both occur: if someone shook hands with everyone (6 handshakes), then no one shook hands with no one (0 handshakes), and vice versa. So there are at most 6 possible active handshake values.
  • RepresentPigeons: 7 people   Boxes: at most 6 possible degree values (either 0–5 or 1–6, not both 0 and 6)
  • ProveSince 7 people must be distributed into at most 6 boxes, by the Pigeonhole Principle, at least two people must share the same handshake count.
  • CheckThe observation about 0 and 6 being mutually exclusive is essential — without it, there are 7 possible values and the basic principle would not apply.
  • InterpretIn any group of 7 people at a party, at least two must have shaken the same number of hands.
Practice 8.2Concept and Skill
  1. A group of 8 people each name their favorite day of the week. Prove that at least two people named the same day.
  2. A club has 15 members, each born in one of 12 months. Prove that at least two members share a birth month.
  3. For the socks problem: if the drawer contains socks in 4 colors, how many socks must be drawn to guarantee a matching pair? Explain using the Pigeonhole Principle.
  4. Write a complete pigeonhole argument for this claim: among any 14 people, at least two were born on the same day of the week.
  5. Explain why 12 people in a room do not guarantee a shared birth month, but 13 do.
Sections 8.3 – 8.4
Generalized Pigeonhole and Minimum Guarantees
Ceiling Function · Generalized Statement · Minimum Guarantee Formula · Worked Examples
Section 8.3

Generalized Pigeonhole Principle

The basic Pigeonhole Principle guarantees that some box receives at least 2 objects, provided there are more objects than boxes. But what if there are many more objects than boxes? The Generalized Pigeonhole Principle answers this question precisely.

Generalized Pigeonhole Principle

If N objects are distributed into n boxes, at least one box contains at least

⌈ N / n ⌉ objects

where ⌈ x ⌉ denotes the ceiling function — the smallest integer greater than or equal to x.

Equivalently: if more than k · n objects are distributed into n boxes, at least one box contains at least k + 1 objects.

The Ceiling Function

ExpressionValueWhy
⌈ 3 ⌉33 is already an integer
⌈ 3.1 ⌉4Next integer above 3.1
⌈ 3.9 ⌉4Next integer above 3.9
⌈ 7/3 ⌉ = ⌈ 2.33… ⌉3Next integer above 2.33
⌈ 11/5 ⌉ = ⌈ 2.2 ⌉3Next integer above 2.2
⌈ 35/5 ⌉ = ⌈ 7 ⌉77 is already an integer
Example 8.3.1
Guaranteed grade group
  • ProblemA class has 35 students, and each receives a letter grade of A, B, C, D, or F. Prove that at least 7 students received the same grade.
  • RepresentPigeons: 35 students   Boxes: 5 grade categories   Guaranteed minimum: ⌈ 35/5 ⌉ = 7
  • ProveBy the Generalized Pigeonhole Principle, at least one grade category contains at least ⌈ 35/5 ⌉ = 7 students.
  • CheckIf each grade were given to at most 6 students, the total number of students would be at most 6 × 5 = 30, which is less than 35. Contradiction.
  • InterpretIn a class of 35 students with 5 possible letter grades, at least 7 students must have received the same grade.
Example 8.3.2
Cards from a deck
  • ProblemHow many cards must be drawn from a standard 52-card deck to guarantee that at least 4 cards share the same suit?
  • ThinkThere are 4 suits. We want a guarantee of at least 4 per suit: set k + 1 = 4, so k = 3. Minimum cards = k · n + 1 = 3 · 4 + 1 = 13.
  • ProveWith 12 cards, it is possible to have at most 3 of each suit (3 × 4 = 12). With 13 cards and 4 suits, ⌈ 13/4 ⌉ = ⌈ 3.25 ⌉ = 4. At least one suit must appear at least 4 times.
  • InterpretDrawing 13 cards from a standard deck guarantees that at least 4 cards share the same suit.
Answer: 13 cards
Section 8.4

Minimum Guaranteed Outcomes

A common type of pigeonhole problem asks: what is the minimum number of objects needed to guarantee a certain outcome? This is the Generalized Pigeonhole Principle applied in reverse.

Minimum Guarantee Formula

To guarantee at least m objects in some box, using n boxes, you need at least:

N = (m − 1) · n + 1 objects

Reasoning: with (m − 1) · n objects, it is still possible to place exactly m − 1 objects in each box. Adding one more forces the guarantee to trigger.

Example 8.4.1
Selecting from a bag of colored marbles
  • ProblemA bag contains marbles of 6 different colors. How many marbles must be drawn to guarantee that at least 5 marbles share the same color?
  • RepresentBoxes: 6 colors   Desired minimum: 5   Formula: (5 − 1) · 6 + 1 = 25
  • ProveWith 24 marbles, it is possible to have exactly 4 of each color. With 25 marbles and 6 colors, ⌈ 25/6 ⌉ = ⌈ 4.16… ⌉ = 5. At least one color must appear at least 5 times.
  • InterpretDrawing 25 marbles guarantees at least 5 of one color.
Answer: 25 marbles
Example 8.4.2
Ensuring a pair in a card game
  • ProblemA standard deck has 13 different face values, each in 4 suits. How many cards must be dealt to guarantee that at least two share the same face value?
  • RepresentBoxes: 13 face values   Desired minimum: 2 (a pair)   Formula: (2 − 1) · 13 + 1 = 14
  • ProveWith 13 cards, it is possible to hold one of each face value and no pairs. With 14 cards and 13 face values, at least one face value must appear at least twice.
  • InterpretDealing 14 cards guarantees at least one pair by face value.
Answer: 14 cards
Practice 8.3 – 8.4Generalized Principle and Minimum Guarantees
  1. Compute ⌈ 17/4 ⌉
  2. Compute ⌈ 30/7 ⌉
  3. Compute ⌈ 100/9 ⌉
  4. Compute ⌈ 51/10 ⌉
  1. A restaurant offers 8 entrée options. On a given evening, 57 customers each order one entrée. Prove that at least 8 customers ordered the same entrée.
  2. A class of 50 students takes a quiz with 10 questions, each scored correct or incorrect. Prove that at least two students answered the same number of questions correctly. (Hint: scores range from 0 to 10 — how many boxes?)
  3. How many cards must be drawn from a standard 52-card deck to guarantee that some suit contains at least 5 cards?
  4. A bin contains gloves in 5 colors. How many gloves must be drawn to guarantee at least 9 gloves of the same color?
Sections 8.5 – 8.9
Applications: Integers, Remainders, Geometry, Graphs, and Scheduling
Divisibility · Remainder Classes · Points in Regions · Degree Counts · Conflicts
Section 8.5

Pigeonhole Arguments with Integers

Number theory offers especially clean applications of the Pigeonhole Principle. Problems about sums, differences, and subsets of integers often yield elegant existence results. The key technique is to choose boxes that capture a divisibility or parity structure.

Example 8.5.1
Five numbers, sum divisible by 5
  • ProblemFrom any set of 5 integers, prove that some non-empty subset has a sum divisible by 5.
  • ThinkConsider the partial sums of the integers listed in some order. Use remainders as boxes.
  • RepresentLet the 5 integers be a₁, a₂, a₃, a₄, a₅. Form six partial sums:
    S₀ = 0, S₁ = a₁, S₂ = a₁ + a₂, S₃ = a₁ + a₂ + a₃, S₄ = a₁ + ··· + a₄, S₅ = a₁ + ··· + a₅ There are 6 partial sums and only 5 possible remainders mod 5 (namely 0, 1, 2, 3, 4).
  • ProveBy the Pigeonhole Principle, at least two partial sums Sᵢ and Sⱼ (with i < j) have the same remainder mod 5. Then Sⱼ − Sᵢ = aᵢ₊₁ + ··· + aⱼ is divisible by 5. This is a non-empty subset sum divisible by 5.
  • CheckIf any partial sum Sₖ ≡ 0 (mod 5), the subset {a₁, …, aₖ} already has sum divisible by 5. Otherwise, the 5 non-zero partial sums have remainders from {1, 2, 3, 4} — only 4 values for 5 sums, so the principle applies.
  • InterpretNo matter which 5 integers you choose, some non-empty subset sums to a multiple of 5.
Example 8.5.2
Common remainder among 13 integers
  • ProblemProve that among any 13 integers, at least two have the same remainder when divided by 12.
  • RepresentPigeons: 13 integers   Boxes: 12 remainder classes (remainders 0, 1, 2, …, 11)
  • ProveBy the Pigeonhole Principle, since 13 > 12, at least two integers share the same remainder mod 12. Their difference is divisible by 12.
  • InterpretAny 13 integers include two whose difference is a multiple of 12.
Example 8.5.3
Two subsets with equal sum
  • ProblemLet A be any set of 10 distinct integers chosen from {1, 2, …, 50}. Prove that two different subsets of A have the same sum.
  • RepresentPigeons: non-empty subsets of A (there are 2¹⁰ − 1 = 1023 of them)   Boxes: possible subset sums. The maximum possible sum is at most 41 + 42 + ··· + 50 = 455. So subset sums range over at most 455 values.
  • ProveSince 1023 > 455, by the Pigeonhole Principle, at least two different non-empty subsets must have the same sum.
  • InterpretNo matter which 10 integers from 1 to 50 you choose, two different subsets will sum to the same total. You cannot design such a set in which all subset sums are distinct.
Section 8.6

Pigeonhole Arguments with Remainders

When working modulo n, there are exactly n remainder classes: 0, 1, 2, …, n − 1. Every integer belongs to exactly one class. This makes modular arithmetic a natural box structure for pigeonhole arguments. The pattern that emerges is consistent and worth internalizing.

General Divisibility Pattern

To guarantee that some two of N integers share a remainder mod n (and thus have a difference divisible by n), you need N ≥ n + 1.

Example 8.6.1
Six integers, difference divisible by 5
  • ProblemProve that among any 6 integers, two must have a difference divisible by 5.
  • RepresentPigeons: 6 integers   Boxes: 5 remainder classes mod 5 (remainders 0, 1, 2, 3, 4)
  • ProveSince 6 > 5, at least two integers share the same remainder mod 5. If a ≡ r (mod 5) and b ≡ r (mod 5), then a − b ≡ 0 (mod 5), meaning 5 divides (a − b).
  • InterpretAmong any 6 integers, at least two have a difference divisible by 5.
Example 8.6.2
Difference divisible by 9
  • ProblemProve that from any 10 integers, some two have a difference divisible by 9.
  • RepresentPigeons: 10 integers   Boxes: 9 remainder classes mod 9
  • ProveSince 10 > 9, at least two integers share the same remainder mod 9. Their difference is divisible by 9.
  • InterpretAny 10 integers contain two whose difference is a multiple of 9.
Section 8.7

Pigeonhole Arguments in Geometry

Geometric problems are a rich source of pigeonhole applications. The boxes are typically regions of space — intervals, squares, triangles, or disks — and the pigeons are points. The key technique is partitioning the space into a finite number of regions so that the number of points exceeds the number of regions, forcing two points to share a region. Since two points in the same small region must be close to each other, this proves a distance bound.

Example 8.7.1
Five points in a square
  • ProblemFive points are placed inside or on a square with side length 2. Prove that at least two of the points are within distance √2 of each other.
  • ThinkDivide the 2 × 2 square into 4 unit squares, each with side length 1.
  • RepresentPigeons: 5 points   Boxes: 4 unit squares formed by dividing the 2 × 2 square with cuts at the midpoints of each side, creating a 2-by-2 grid of 1 × 1 squares.
Diagram Description

A 2 × 2 square is divided by a vertical cut at x = 1 and a horizontal cut at y = 1, forming four unit squares arranged in a 2-by-2 pattern. Label them I (top-left), II (top-right), III (bottom-left), IV (bottom-right). Each unit square has side length 1 and diagonal length √(1² + 1²) = √2.

  • ProveBy the Pigeonhole Principle, since 5 points are distributed into 4 unit squares, at least one unit square contains at least 2 points. The maximum distance between two points within a unit square is the diagonal: √2.
  • CheckThe argument holds whether points are on the boundary or interior, since the unit squares include their boundaries.
  • InterpretNo matter how 5 points are placed in a 2 × 2 square, two of them are within distance √2 of each other.
Example 8.7.2
Points on a segment
  • ProblemNine points are placed on a line segment of length 1. Prove that at least two points are within distance 1/8 of each other.
  • RepresentDivide the segment into 8 equal subsegments of length 1/8: [0, 1/8], [1/8, 2/8], …, [7/8, 1]. Pigeons: 9 points   Boxes: 8 subsegments
  • ProveBy the Pigeonhole Principle, at least one subsegment contains at least 2 of the 9 points. Any two points within a segment of length 1/8 are within distance 1/8 of each other.
  • InterpretAmong any 9 points on a unit segment, some two are within 1/8 of each other.
Example 8.7.3
Points in an equilateral triangle
  • ProblemFive points are placed inside an equilateral triangle with side length 2. Prove that at least two points are within distance 1 of each other.
  • ThinkDivide the triangle into 4 smaller equilateral triangles of side length 1 by connecting the midpoints of each side.
  • RepresentPigeons: 5 points   Boxes: 4 small equilateral triangles of side length 1
Diagram Description

An equilateral triangle with side 2 is divided into 4 equilateral triangles of side 1 by connecting the midpoints of its three sides. This creates three small triangles in the corners and one central inverted triangle. Each small triangle has side length 1 and maximum interior distance equal to 1.

  • ProveBy the Pigeonhole Principle, at least one small triangle contains at least 2 points. Any two points within an equilateral triangle of side 1 are within distance 1 of each other.
  • InterpretAny 5 points inside an equilateral triangle with side 2 include two that are within distance 1.
Section 8.8

Pigeonhole Arguments in Graphs

Graph theory offers its own natural settings for the Pigeonhole Principle, particularly in arguments about vertex degrees, path lengths, and shared neighborhoods. In a graph with n vertices, the degree of any vertex is a number from 0 to n − 1.

Example 8.8.1
Shared degree in any graph
  • ProblemIn a simple graph with n ≥ 2 vertices, prove that at least two vertices have the same degree.
  • ThinkPossible degrees range from 0 to n − 1. But degrees 0 and n − 1 cannot both occur: if one vertex is connected to all others, no vertex is isolated, and vice versa.
  • RepresentPigeons: n vertices   Boxes: at most n − 1 possible degree values (0 and n − 1 are mutually exclusive)
  • ProveSince n vertices must be distributed into at most n − 1 degree boxes, by the Pigeonhole Principle, at least two vertices have the same degree.
  • InterpretIn any simple graph with at least 2 vertices, some two vertices always share the same degree.
Example 8.8.2
Mutual friends or strangers — Ramsey preview
  • ProblemIn a group of 6 people, any two of whom are either friends or strangers, prove that there must be either 3 mutual friends or 3 mutual strangers.
  • ThinkFix one person P. Person P has 5 relationships with the other 5 people. Each relationship is friend or stranger. By the Pigeonhole Principle: ⌈ 5/2 ⌉ = 3, so at least 3 of P's relationships are of the same type.
  • ProveSuppose at least 3 of P's relationships are "friend" (the stranger case is symmetric). Call those 3 friends A, B, C.
    • If any two of A, B, C are friends with each other, that pair plus P forms 3 mutual friends. Done.
    • If none of A, B, C are friends with each other, then A, B, C are 3 mutual strangers. Done.
  • InterpretIn any group of 6 people, a trio of mutual friends or mutual strangers must exist. This is the statement R(3, 3) = 6 from Ramsey theory.
Section 8.9

Pigeonhole Arguments in Scheduling

Example 8.9.1
Course section conflicts
  • ProblemA university offers 11 courses, each scheduled into one of 5 time slots. Prove that at least three courses must share the same time slot.
  • RepresentPigeons: 11 courses   Boxes: 5 time slots   Ceiling: ⌈ 11/5 ⌉ = ⌈ 2.2 ⌉ = 3
  • ProveSince 11 courses must be distributed across 5 time slots, at least one time slot must contain at least 3 courses.
  • InterpretThe conflict is unavoidable — no matter how cleverly the schedule is arranged, some time slot must hold at least 3 courses.
Practice 8.5 – 8.9Applications Practice
  1. Prove that among any 5 integers, some two have a difference divisible by 4.
  2. Prove that from any 10 integers, some two have a difference divisible by 9.
  3. Six points are placed inside a square with side length 4. Prove that at least two are within distance 2√2 of each other. (Divide into 4 squares of side 2.)
  4. A sequence of 10 distinct integers is chosen from {1, 2, …, 17}. Prove that some two of the integers are consecutive. (Hint: partition into pairs {1,2}, {3,4}, …, {17}… what adjustment is needed?)
  5. In a simple graph with n = 5 vertices, prove that at least two vertices have the same degree.
  6. A hospital has 10 nurses on call, assigned to one of 7 days. Prove that at least two nurses share the same on-call day.
  7. A league has 9 teams. Each game is played on one of 4 courts simultaneously. What is the minimum number of games needed to guarantee that at least 3 games have been scheduled on some court?
Sections 8.10 – 8.12
Ramsey Thinking, Non-Constructive Proof, and Computing Applications
Ramsey Numbers · Complete Disorder Is Impossible · Hash Collisions · Compression Limits
Section 8.10

Ramsey-Type Thinking as an Introduction

The friends-and-strangers example in Section 8.8 is a first glimpse of Ramsey theory, one of the most celebrated areas of combinatorics. The central question of Ramsey theory is: how large must a structure be before a certain pattern must appear within it? This is an existence question in its purest form.

ConceptDescription
Ramsey number R(m, n)The smallest integer N such that any red-blue coloring of the edges of the complete graph K_N must contain either a red K_m or a blue K_n.
R(3, 3) = 6In any group of 6 people, some 3 are mutually friends or mutually strangers. A group of 5 does not guarantee this.
R(4, 4) = 18Known, but requires considerably more work to prove.
R(5, 5)Not precisely known as of this writing — somewhere between 43 and 48.
The Central Principle of Ramsey Theory

Complete disorder is impossible. In any sufficiently large structure, some organized pattern must emerge. This runs counter to the intuition that a large, random-looking structure might have no internal order. Ramsey theory proves that patterns are inevitable once the structure is large enough.

Perspective

The Pigeonhole Principle is the simplest Ramsey-type argument. The friends-and-strangers result (R(3,3) = 6) is the next simplest. Beyond this, Ramsey numbers become extremely difficult to determine. The fact that such small, simply stated questions are deeply open is part of what makes Ramsey theory both fascinating and humbling.

Section 8.11

Existence Without Construction

A recurring theme in this chapter is that existence arguments do not require you to build the object you claim exists. A non-constructive proof establishes that something must exist by showing that its absence leads to a contradiction. This is logically valid. Non-constructive proofs are common in combinatorics, number theory, analysis, and logic. They are often the only proofs available for existence claims where the object is hard or impossible to locate.

Example 8.11.1
Unavoidable repetition in a sequence
  • ProblemA sequence of 101 integers is drawn from the set {1, 2, …, 100}. Prove that some integer appears at least twice.
  • RepresentPigeons: 101 integers   Boxes: 100 possible values (1 through 100)
  • ProveBy the Pigeonhole Principle, since 101 > 100, some value must appear at least twice.
  • InterpretWith 101 integers and only 100 possible values, a repeated value is unavoidable. We do not know which value repeats — only that one must.
Example 8.11.2
Data compression limits
  • ProblemA compression algorithm takes a file of exactly 10 bits (one of 2¹⁰ = 1024 possible files) and produces a compressed version of exactly 9 bits (one of 2⁹ = 512 possible outputs). Prove that the algorithm cannot correctly compress all possible input files.
  • RepresentPigeons: 1024 possible 10-bit files   Boxes: 512 possible 9-bit compressed outputs
  • ProveSince 1024 > 512, by the Pigeonhole Principle, at least two different input files must map to the same compressed output. These two files cannot both be correctly decompressed — the algorithm must fail on at least one of them.
  • InterpretNo lossless compression algorithm can compress every file to a shorter file. This is not a limitation of any particular algorithm; it is a mathematical certainty.
Section 8.12

Applications in Computing and Data

The Pigeonhole Principle appears throughout computer science and data science. Understanding it helps students reason about algorithm limitations, hash functions, data storage, and network behavior.

Hash Functions and Collisions

A hash function maps inputs (files, passwords, text strings) to a smaller set of hash values. If you have more possible inputs than hash values — which is always possible, since inputs can be arbitrarily varied — the Pigeonhole Principle guarantees that two different inputs must produce the same hash value. This is called a hash collision. No hash function can avoid collisions if the input space is larger than the output space. Cryptographic hash functions are designed to make collisions hard to find, not impossible.

The Birthday Paradox — Deterministic vs. Probabilistic

The birthday problem asks: how many people must be in a room before two are likely to share a birthday? The deterministic (pigeonhole) version says: with 366 people and 365 possible birthdays, at least two must share one. This is certain. The probabilistic version asks for the expected number — and the surprising answer is about 23 people for a 50% probability. This is not a contradiction: 23 gives more than 50% probability, while 366 gives absolute certainty. These are different thresholds answering different questions.

ApplicationPigeonhole Role
Hash collisionsInputs outnumber output hash values → collision must exist
Data compressionFiles outnumber shorter files → some file cannot compress
Sorting lower boundsn! orderings require at least ⌈log₂(n!)⌉ comparisons to distinguish
Network packet lossArrival rate exceeds processing rate → some packets must be dropped
Birthday problem (deterministic)366 people, 365 days → shared birthday is certain
MGU Library Connection
  • Probability and Statistics textbook: birthday problem and probabilistic collision thresholds
  • Cryptography module: hash functions, collision resistance, and birthday attacks
  • Algorithms chapter: comparison-based sorting lower bounds and the decision-tree model
  • Data Science Foundations chapter: hash table collision rates and load factor analysis
  • Discrete Mathematics textbook: logic and proof methods underlying existence arguments
Sections 8.13 – 8.14
Common Mistakes and Preparing for Combinatorial Proof
Seven Structural Errors · Complete Argument Requirements · Bridge to Chapter 9
Section 8.13

Common Pigeonhole Mistakes

Mistake 1 — Not Identifying the Boxes Explicitly
"There are 13 people and only 12 months, so two share a birthday."

A proof must specify what the boxes are, what the pigeons are, and why each pigeon goes into exactly one box. The statement above is missing the explicit box structure and distribution rule.

Correct: "Each person is assigned to the box corresponding to their birth month. There are 13 people and 12 boxes. By the Pigeonhole Principle, at least one box contains at least 2 people."
Mistake 2 — Miscounting the Boxes

A common error is counting the wrong number of boxes. You might forget a constraint that reduces the number of available boxes (as in the handshake example, where degrees 0 and n − 1 cannot both occur) or include impossible boxes. Always identify the set of possible boxes carefully.

Mistake 3 — Writing "Might" Instead of "Must"
"At least two people might share a birthday."

The Pigeonhole Principle proves that something must occur — not that it will probably occur, or might occur. With 5 people and 12 months, a shared birthday is possible but not guaranteed. With 13 people, it is certain.

Correct: "At least two people must share a birth month."
Mistake 4 — Using the Basic Principle When the Generalized Form Is Needed

If the problem asks for a guarantee stronger than "at least two objects in one box," the basic Pigeonhole Principle is not enough. Forgetting to upgrade to the Generalized Pigeonhole Principle leads to an underpowered argument.

Mistake 5 — Getting the Minimum Guarantee Formula Wrong
"To guarantee 3 cards of the same suit (4 suits), I need 3 × 4 = 12 cards."

The formula is (m − 1) · n + 1, not m · n. With 12 cards, you can still have at most 3 per suit and avoid the guarantee. You need (3 − 1) · 4 + 1 = 9 cards.

Correct: N = (m − 1) · n + 1 = (3 − 1) · 4 + 1 = 9 cards.
Mistake 6 — Using Pigeonhole When a Count Is Needed

The Pigeonhole Principle proves existence — it does not count how many arrangements satisfy a property or identify which objects satisfy it. If the problem asks how many or which, a different method is needed.

Mistake 7 — Writing an Incomplete Argument

A complete pigeonhole argument must include: (1) clear identification of the pigeons, (2) clear identification of the boxes, (3) the number of pigeons and boxes, (4) the specific statement of the Pigeonhole Principle being applied, and (5) the guaranteed conclusion that follows. Missing any component makes the argument incomplete, even if the final answer is correct.

Section 8.14

Preparing for Combinatorial Proofs

Chapter 8 closes Part III's opening to proof-based combinatorics. The Pigeonhole Principle is an existence tool — it proves that a certain object or pattern must be present. The next chapter, Chapter 9, studies combinatorial identities and proof — arguing that two expressions count the same structure. Together, these chapters develop the proof skills needed for deeper work in combinatorics, graph theory, algorithm analysis, cryptography, and probability.

Readiness Checklist for Chapter 9

  1. ✓I can identify pigeons, boxes, and conclusions in a pigeonhole argument.
  2. ✓I can write a complete pigeonhole proof in full sentences.
  3. ✓I can apply the Generalized Pigeonhole Principle and the minimum guarantee formula.
  4. ✓I can distinguish existence arguments from exact-count arguments.
  5. ✓I understand that a proof must work for all cases, not just convenient examples.
Looking Ahead
Chapter 9: Combinatorial Identities and Proof

Chapter 9 will teach students how to prove combinatorial identities — equations like Pascal's Identity, the Vandermonde identity, and the hockey-stick identity — using double counting, bijective arguments, algebraic manipulation, and recurrence-based reasoning. The skill of writing a complete mathematical argument, practiced here with pigeonhole proofs, carries directly into combinatorial proof. Students will learn to see that a formula is not just a symbolic statement; it describes two different ways to count the same structure.

Chapter 8 — Back Matter

Chapter Summary

Key Terms Review

existence argument
A proof that a certain object, pattern, or relationship must exist under given conditions, without explicitly constructing it.
Pigeonhole Principle
If more than n objects are distributed into n boxes, at least one box contains at least 2 objects.
Generalized Pigeonhole
If N objects are distributed into n boxes, at least one box contains at least ⌈N/n⌉ objects.
pigeons
The objects being distributed in a pigeonhole argument.
boxes
The categories into which pigeons are placed; must be exhaustive and mutually exclusive.
ceiling function
⌈x⌉ is the smallest integer greater than or equal to x. Used in the Generalized Pigeonhole Principle.
minimum guarantee
The smallest N such that some box is certain to hold at least m objects: N = (m − 1) · n + 1.
remainder class
The set of integers with a given remainder when divided by n; forms one of n natural boxes in modular pigeonhole arguments.
hash collision
Two different inputs that map to the same hash value; guaranteed to exist whenever the input space exceeds the output space.
Ramsey theory
The study of how large a structure must be before a certain ordered pattern must appear within it.
Ramsey number R(m,n)
The smallest N such that any two-coloring of K_N's edges contains a red K_m or a blue K_n.
non-constructive proof
A proof that establishes existence by contradiction, without producing the object claimed to exist.

Concept Review Questions

  1. What is the difference between an existence argument and an exact-count argument? Give an example of each type of question.
  2. State the basic Pigeonhole Principle in your own words. What must you identify before applying it to a problem?
  3. State the Generalized Pigeonhole Principle. What does the ceiling function do in this context?
  4. What is the minimum guarantee formula? Derive it from the Generalized Pigeonhole Principle rather than memorizing it.
  5. Why do pigeonhole arguments require you to identify the boxes explicitly? What goes wrong if you do not?
  6. Explain why degrees 0 and n − 1 cannot both occur in a simple graph with n ≥ 2 vertices. How does this fact reduce the number of available boxes in a degree pigeonhole argument?
  7. What is a hash collision? Why does the Pigeonhole Principle guarantee that every hash function must produce some collisions?
  8. What is Ramsey theory, in general terms? How does the friends-and-strangers result illustrate Ramsey thinking?
  9. Why is a non-constructive proof logically valid, even though it does not produce the object it claims exists?
  10. What are three common mistakes students make when writing pigeonhole arguments?

Pigeonhole Practice

Practice PBasic and Generalized
  1. A bag contains marbles colored red, blue, green, yellow, and orange. How many marbles must you draw to guarantee that at least two marbles share the same color?
  2. A deck of 52 cards (4 suits, 13 values) is shuffled. How many cards must be drawn to guarantee at least two cards of the same suit?
  3. There are 367 students at a school. Prove that at least two students share the same birthday. (Assume 366 possible birthdays, including February 29.)
  4. A bin contains screws in 8 different sizes. How many screws must be taken to guarantee at least 4 screws of the same size?
  5. A professor gives letter grades (A, B, C, D, F) in a class of 31 students. Prove that at least 7 students received the same grade.
  6. Ten points are placed on a line segment of length 1. Prove that at least two are within distance 1/9 of each other.
Practice EExistence Proofs
  1. Let a₁, a₂, …, a₉ be any 9 distinct integers chosen from {1, 2, …, 16}. Prove that some two of them differ by at most 1. (Hint: partition {1, …, 16} into pairs of consecutive integers.)
  2. Prove that among any 5 integers, some two have a difference divisible by 4.
  3. Five points are placed inside a square with side length 4. Prove that at least two of the points are within distance 2√2 of each other.
  4. A sequence of 10 distinct integers is chosen from {1, 2, …, 17}. Prove that some two of the integers are consecutive.
  5. Prove that in any group of 5 people, at least two people have the same number of friends within the group. (Assume friendship is mutual and no one is friends with themselves.)
  6. Let S be any set of 6 integers from {1, 2, …, 10}. Prove that two elements of S sum to 11. (Hint: form pairs that sum to 11.)
Practice AApplications
  1. Password Security. A system uses 6-character PINs drawn from digits 0–9, giving 10⁶ = 1,000,000 possible PINs. The system stores 4-digit hash codes, giving 10⁴ = 10,000 possible hash codes. Prove that at least two different PINs must produce the same hash code.
  2. File Compression. An algorithm compresses 20-bit files to 18-bit files. How many possible 20-bit inputs are there? How many 18-bit outputs? Prove that the algorithm cannot losslessly compress every 20-bit file.
  3. Network Routing. A router receives packets from 250 IP addresses per second, but can route only 200 packets per second without delay. Prove that at least 50 packets per second must be delayed or dropped.
  4. Inventory Management. A warehouse stores 7 types of components. In one day, 43 components are shipped out. Prove that at least 7 components of the same type were shipped.
  5. Hash Collisions. A cryptographic hash function maps arbitrary-length messages to 256-bit hash values. Explain, using the Pigeonhole Principle, why hash collisions must exist in principle, even for a perfectly designed hash function.

Error Analysis

Each argument below contains an error. Identify it and explain how to correct it.

Error Analysis 1
"There are 7 students and 6 grades. By the Pigeonhole Principle, at least two students received the same grade."

Is there an error? If not, is the argument complete? What component is missing?

Error Analysis 2
"Twelve people are in a room. Proof that two share a birth month: there are 12 months and 12 people, so by the Pigeonhole Principle, each month gets exactly one person."

Identify two distinct errors in this argument.

Error Analysis 3
"To guarantee at least 5 cards of the same suit in a standard deck (4 suits), I need 5 × 4 = 20 cards."

Find the error and compute the correct answer using the minimum guarantee formula.

Error Analysis 4
"A sequence of integers from 1 to 5 has 11 terms. By the Pigeonhole Principle, at least two terms might be the same value."

What single word is wrong? What word should replace it?

Error Analysis 5
"I placed 10 books on 4 shelves. At least one shelf has at least 3 books. Since I can count and see shelves with 3, 3, 2, 2 — I don't need to write the proof."

Why is this reasoning flawed? What does a proof need to establish that counting a specific case does not?

Chapter 8 Checkpoint

Chapter 8 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 8
Section 1 — Vocabulary and Concepts
  1. State the Pigeonhole Principle precisely. Identify what you must define before applying it to a problem.
  2. State the Generalized Pigeonhole Principle and the minimum guarantee formula. Derive the formula — do not just state it.
  3. Explain the difference between an existence argument and a proof by construction. Why is a non-constructive proof logically valid?
Section 2 — Core Skills
  1. A bin contains gloves in 5 colors: black, white, gray, navy, and brown. The bin has 40 gloves total. How many gloves must be drawn to guarantee: (a) at least 2 of the same color? (b) at least 5 of the same color? (c) at least 9 of the same color? Write a complete proof for each part.
  2. Prove: among any 8 integers, at least two must have the same remainder when divided by 7.
  3. Nine points are placed inside a rectangle with dimensions 4 by 3. Prove that at least two points are within distance √2 of each other. (Hint: divide the rectangle into 8 unit squares.)
Section 3 — Proof Writing
  1. A class of 30 students is registered in courses coded 100–109 (10 possible course codes). Prove that at least 3 students share the same course code.
  2. In a group of 6 people, any two are either friends or strangers. Prove that there must exist either 3 mutual friends or 3 mutual strangers. (This is a full proof — identify the pigeons, boxes, and the two cases you must analyze.)
Section 4 — Applications and Reasoning
  1. Explain the data compression limit in your own words: why can no lossless algorithm compress every possible file to a shorter file? Use the Pigeonhole Principle explicitly in your explanation.
  2. A student writes: "There are 25 students and 5 project topics. Therefore, at least 5 students chose the same topic." Is this argument correct? If not, find the error and write the corrected version.
MGU Library Connection
  • Discrete Mathematics textbook, Chapters on Logic and Proof: foundations of formal proof methods
  • Graph Theory reference: extensions of the graph-based pigeonhole arguments from Section 8.8
  • Probability and Statistics textbook: the probabilistic birthday problem and expected collision thresholds
  • Cryptography module: hash function security, collision resistance, and the birthday attack
  • Algorithms chapter: comparison-based sorting lower bounds and decision-tree complexity
  • Chapter 9 of this textbook: combinatorial identities and proof — double counting, bijective arguments, and algebraic reasoning

Answers for the Chapter 8 Checkpoint may be placed in the Answer Key.