Chapter 3: Pigeonhole Principle and Introductory Ramsey Theory

Why Must Six People Contain a Familiar or Unfamiliar Triple?

Suppose six people attend a gathering. For every pair of individuals, we record exactly one of two mutual relationships: either they know each other (friends), or they do not (strangers). Must there always exist a group of three people who are all mutual friends, or three people who are all mutual strangers?

This classic problem—often called the Theorem on Friends and Strangers—marks the primary entry point into Ramsey Theory, a branch of combinatorics concerned with unavoidable order in large discrete systems. To analyze this rigorously, we translate the social scenario directly into graph-theoretic terms:

The fundamental question can thus be rephrased: Is it impossible to color the 15 edges of $K_6$ with two colors(Red non-zero and Blue non-zero) without creating at least one single-color(Red or Blue) triangle? As we will prove using the Pigeonhole Principle, the answer is a definitive yes.

3.1 Basic Pigeonhole Principle

The Pigeonhole Principle (historically known as Dirichlet's Box Principle) states an intuitively obvious yet deeply powerful truth: If more objects than container boxes are distributed into those boxes, then at least one box must contain two or more objects.

The "boxes" in combinatorial proofs are abstract categories rather than physical bins. Identifying the correct choice of boxes is the key creative step.

Classic Applications:

• Birth Months: Among 13 people, at least two were born in the same month (13 objects, 12 month boxes).
• Modular Remainders: Every integer leaves one of 5 possible remainders ($\{0, 1, 2, 3, 4\}$) when divided by 5. Therefore, among any 6 integers, at least two share the same remainder $r$. Their difference $(5u + r) - (5v + r) = 5(u - v)$ is guaranteed to be divisible by 5!

3.2 Generalized Pigeonhole Principle

When the number of objects $N$ significantly exceeds the number of boxes $m$, the **Generalized Pigeonhole Principle** provides a higher minimum occupancy guarantee based on the ceiling of the average occupancy.

3.3 Average-Value and Weighted Pigeonhole Arguments

The pigeonhole principle is a discrete instance of a broader mathematical truth: In any set of real values, at least one value is greater than or equal to the average, and at least one value is less than or equal to the average. When components have varying sizes or capacities, we use weighted averages.

Capacity Overload Proof without Division: If box $i$ has capacity $c_i$ and total objects $N > \sum c_i$, then at least one box must exceed its capacity.

3.4 Infinite Pigeonhole Principle

The Infinite Pigeonhole Principle extends partitioning logic to infinite sets: If an infinite set is partitioned into finitely many subset classes, then at least one class must contain infinitely many elements.

Application to Sequences: In any infinite sequence over a finite alphabet (e.g., $R, B, G$), at least one symbol occurs infinitely often, forming an infinite constant subsequence.

3.5 Introductory Ramsey Theory and Ramsey's Theorem

Pigeonhole arguments force repetition of individual elements. Ramsey Theory asks a deeper structural question: How large must a system be to guarantee a completely monochromatic sub-structure?

For graph edge colorings, a Ramsey number $R(s, t)$ denotes the minimum number of vertices $N$ such that every Red-Blue edge coloring of $K_N$ contains either a solid Red $K_s$ or a solid Blue $K_t$.

3.6 Applications to Sequences, Geometry, and Number Theory

The pigeonhole principle yields profound results across diverse branches of mathematics when applied to clever choice of boxes.

1. Sequences: Consecutive Sub-Block Sum Divisibility

Theorem: Given any sequence of $m$ integers $(a_1, a_2, \dots, a_m)$, there is always a non-empty contiguous block whose sum is divisible by $m$.

Proof via Prefix Sums: Define $m+1$ prefix sums $S_0 = 0$ and $S_j = \sum_{\ell=1}^j a_\ell$. Since there are $m+1$ prefix sums and only $m$ remainder classes modulo $m$, two prefix sums $S_i$ and $S_j$ ($i < j$) must share the same remainder modulo $m$. Subtracting them gives:

2. Geometry: Nearby Points in a Unit Square

Theorem: Place 5 points inside a $1 \times 1$ closed unit square. At least two points are separated by a Euclidean distance $d \le 1/\sqrt{2}$.

3. Number Theory: Divisibility in $\{1, 2, \dots, 2n\}$

Theorem: Choose $n+1$ distinct integers from $\{1, 2, \dots, 2n\}$. At least one chosen integer strictly divides another!

Find the Sharp Pigeonhole Bound and Test a Ramsey Coloring

In this investigation, we combine proof diagnosis, sharp threshold constructions, and algorithmic verification to examine the exact boundaries of the Pigeonhole Principle and Ramsey Theory.

function find_divisible_subblock(arr, m):
    remainder_map = {0: 0}  // Base prefix sum S0 = 0 at index 0
    current_sum = 0

    for j from 1 to length(arr):
        current_sum += arr[j]
        rem = ((current_sum % m) + m) % m  // Non-negative remainder

        if rem in remainder_map:
            i = remainder_map[rem]
            return arr[i+1 ... j]  // Contiguous sub-block
        else:
            remainder_map[rem] = j