Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 36 · Pigeonhole and Ramsey

Pigeonhole Applications

Apply the pigeonhole principle to the Erdős–Szekeres monotone subsequence theorem and Dirichlet's rational approximation, with exhaustive and numeric checks in Python.

Two famous theorems show how far the pigeonhole principle can go. One is about order in sequences (Erdős–Szekeres), the other about approximating real numbers by fractions (Dirichlet). Both have short proofs and both can be tested by computer.

The Erdős–Szekeres theorem

Every sequence of n^2 + 1 distinct real numbers contains an increasing subsequence of length n + 1 or a decreasing subsequence of length n + 1.

For n = 2: any 5 distinct numbers have a monotone subsequence of length 3.

Proof. For each position i, let (a_i, b_i) be the length of the longest increasing subsequence ending at i and the longest decreasing subsequence ending at i. Suppose no monotone subsequence of length n + 1 exists. Then each pair lies in {1..n} x {1..n}: n^2 boxes for n^2 + 1 positions, so two positions i < j share a pair. But if x_i < x_j the increasing run ending at j could be extended by x_i, so a_j > a_i; if x_i > x_j then b_j > b_i. Contradiction.

The bound is sharp: arrange n blocks of n decreasing numbers so that the blocks increase, and the longest monotone subsequence has length exactly n.

Python Test Erdős–Szekeres

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line checks all 5! = 120 permutations: each has a monotone subsequence of length at least 3, as promised. The second line shows that with only 4 = 2^2 numbers you can avoid length 3 (the minimum is 2), so the +1 is needed. The loop tests random sequences of length n^2 + 1 and always finds length at least n + 1. (The lis helper uses patience-sorting tails with binary search, O(n log n).)

Dirichlet's approximation theorem

For every real number x and every positive integer N, there are integers p and q with 1 <= q <= N and |x - p/q| < 1/(qN).

Proof. Consider the N + 1 numbers {0 * x}, {1 * x}, ..., {N * x} (fractional parts), all in [0, 1). Cut [0, 1) into N boxes of width 1/N. Two of the fractional parts, say for q_0 < q_1, fall in the same box, so |(q_1 - q_0) x - p| < 1/N for some integer p. With q = q_1 - q_0 <= N, divide by q.

Consequently every irrational number has infinitely many fractions p/q with |x - p/q| < 1/q^2. These fractions are the famous good approximations such as 22/7 for pi.

Python The pigeonhole search for p/q

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The code literally runs the proof: it drops each q x mod 1 into one of N boxes and stops at the first collision. For sqrt2 it finds 7/5, 17/12 and 99/70; for pi with N = 20 it finds 22/7. Every returned fraction satisfies the bound 1/(qN).

flowchart TD
    A["Real number x, bound N"] --> B["N+1 fractional parts of 0x, 1x, ... , Nx"]
    B --> C["N boxes of width 1/N"]
    C --> D["Two land in one box"]
    D --> E["q = difference of indices, p = nearest integer"]
    E --> F["|x - p/q| < 1/(qN)"]

Dirichlet's proof as a pipeline.

More pigeonhole patterns

  • Points in a square: place 5 points in a unit square; two are within distance sqrt2/2 (split into four sub-squares).
  • Schedules and colorings: any coloring of the plane with two colors contains two points of the same color at distance 1 (use an equilateral triangle).
  • Sum-free sets and Ramsey-type results continue this theme, see Ramsey Theory.

When a pigeonhole argument is stuck, look for a hidden quantity that takes few values: a remainder, an odd part, a pair of lengths, a fractional part.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Erdős–Szekeres: a sequence of 26 distinct numbers must contain a monotone subsequence of length at least...

    26 = 5^2 + 1, so there is a monotone subsequence of length 6.
  2. 2. In the Erdős–Szekeres proof, what are the boxes?

    If both lengths were at most n there would be only n^2 pairs for n^2 + 1 positions.
  3. 3. Dirichlet's theorem with N = 100 guarantees a fraction p/q with q at most 100 and error below...

    The bound is |x - p/q| < 1/(qN).
  4. 4. Why are 4 sub-squares enough to show that 5 points in a unit square contain two close points?

    Pigeonhole puts two points in one sub-square of side 1/2, so their distance is at most sqrt2/2.

Summary

  • Erdős–Szekeres: n^2 + 1 distinct numbers have a monotone subsequence of length n + 1; boxes are pairs of run lengths.
  • Dirichlet: fractional parts of 0, x, 2x, ..., Nx in N boxes give |x - p/q| < 1/(qN).
  • Both proofs are algorithms you can run and test; both bounds are tight.

Next: Ramsey Theory