Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Apply the pigeonhole principle

Use when: you need to show some repeat, collision, or shared property must exist among a group, without needing to identify which specific items collide

Goal: a proof that at least one box must hold more than one object, forcing the guaranteed repeat to exist

Taught in The pigeonhole principle

Quick recipe

  1. Identify the objects and the boxes
  2. Compare the object count to the box count
  3. Apply the generalized form for a target count above 2
  4. State the conclusion in terms of the original problem
  1. 1

    Decide what plays the role of the objects being placed, and what plays the role of the boxes they are placed into.

    Example

    "Among any 13 people, two share a birth month": the 13 people are the objects, and the 12 months are the boxes.

    Why: the whole argument is a comparison between two counts, and nothing else in the problem matters until these two roles are named correctly.

  2. 2

    Count the objects, n, and the boxes, m. Confirm n>m; if it holds, at least one box must receive more than one object.

    • the problem asks only whether a repeat exists at all — confirming n>m alone is enough to finish.
    • the problem asks for a guaranteed minimum count above 2 in one box — move to the generalized form in the next step instead.

    Why: n>m is the entire content of the plain pigeonhole principle, since m boxes holding at most one object each could never account for more than m objects.

  3. 3

    To guarantee at least k objects in some one box, confirm \lceil n/m \rceil \ge k, using the smallest n that makes this true when the problem asks how many objects must be pulled.

    Example

    To guarantee 3 socks of the same color from 4 colors, the worst case fills 2 per color first, 8 socks, without a triple; the 9th sock forces one color to 3, matching \lceil 9/4 \rceil = 3.

    Why: spreading objects as evenly as possible across the boxes is the worst case an adversary could arrange, and the ceiling is exactly the point past which even that worst case fails.

  4. 4

    Translate the box-and-object result back into the problem's own language, naming what is guaranteed to repeat or collide.

    Why: "some box holds two objects" only answers the question once it is translated back into people, socks, or whatever the problem was actually about.

Common mistakes

  • Naming the objects and boxes backward, which changes what the count actually guarantees.
  • Concluding a repeat exists when n \le m, where no repeat is actually forced.
  • Using the plain form's "2" when the problem asks for a larger guaranteed count, which needs the generalized ceiling formula instead.
  • Treating the guaranteed repeat as identifying which items collide; the principle only proves existence, never which one.