The Pigeonhole Principle

Imagine you have 10 boxes and you need to put 11 socks into them. No matter how you try, at least two socks will share a box. This seemingly childish observation is the Pigeonhole Principle — and it is one of the most powerful tools in all of mathematics.

Formally stated: if n+1 items are placed into n containers, then at least one container must hold at least two items. The proof is a single sentence of logic (assume otherwise, count, reach a contradiction), but the applications span an enormous range.

The principle dates to 1834, when the German mathematician Peter Gustav Lejeune Dirichlet used it to prove that some rational numbers approximate irrational ones with startling precision. In German literature the result still carries his name: Schubfachprinzip (drawer principle). In English, the metaphor of pigeons filing into holes on a dovecote gave it the name we use today.

What makes this principle remarkable is not the statement — it is genuinely obvious. What is remarkable is how far that obvious fact reaches, from proving two Londoners share a hair count to showing every lossless compression algorithm must sometimes make files larger.

Choose a number of boxes, then keep dropping items one by one. The moment you place the (boxes + 1)-th item, the principle guarantees at least one collision — no matter where you drop them.

<p class="hint">Choose the number of boxes, then drop items one by one. The moment you exceed the box count, a <b>collision is guaranteed</b> — no matter where you drop.</p>
<div class="controls">
  <label>Boxes: <select id="boxCount">
    <option value="3">3</option>
    <option value="4">4</option>
    <option value="5" selected>5</option>
    <option value="6">6</option>
    <option value="7">7</option>
  </select></label>
  <button id="dropBtn" type="button">Drop item</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div id="arena" class="arena"></div>
<div class="status" id="status">Drop items to fill the boxes.</div>
<div id="counter" class="counter"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .9rem; }
label { font-size: .9rem; }
select { font: inherit; padding: .2rem .4rem; border: 1px solid #ccc; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.arena { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: .6rem; }
.box { flex: 1 1 60px; min-width: 52px; border: 2px solid #8aa8c2; border-radius: 10px;
       padding: 6px 4px 4px; background: #eef3f7; display: flex; flex-direction: column;
       align-items: center; gap: 4px; min-height: 60px; transition: background .2s, border-color .2s; }
.box.collision { background: #fde8ea; border-color: #e63946; }
.box-label { font-size: .7rem; color: #556; font-weight: 600; letter-spacing: .04em; }
.item { width: 24px; height: 24px; border-radius: 50%; background: #1d3557;
        display: flex; align-items: center; justify-content: center;
        font-size: .65rem; color: #fff; font-weight: 700; animation: pop .15s ease; }
.item.new { background: #e63946; }
@keyframes pop { from { transform: scale(.4); opacity: .3; } to { transform: scale(1); opacity: 1; } }
.status { font-size: 1rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.warn { color: #c92f3c; }
.counter { font-size: .85rem; color: #555; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Pigeonhole demo: drop items randomly into boxes.
// The principle guarantees: once items > boxes, some box holds >= 2.
// We verify this invariant after every drop.

let boxes = [];       // boxes[i] = count of items in box i
let totalItems = 0;
let numBoxes = 5;
let collisionOccurred = false;

function init() {
  numBoxes = parseInt(document.getElementById('boxCount').value, 10);
  boxes = new Array(numBoxes).fill(0);
  totalItems = 0;
  collisionOccurred = false;
  document.getElementById('dropBtn').disabled = false;
  renderArena();
  setStatus('Drop items to fill the boxes.', '');
  updateCounter();
}

function renderArena() {
  const arena = document.getElementById('arena');
  arena.innerHTML = '';
  boxes.forEach((count, i) => {
    const boxEl = document.createElement('div');
    boxEl.className = 'box' + (count >= 2 ? ' collision' : '');
    const label = document.createElement('div');
    label.className = 'box-label';
    label.textContent = fmt('Box %i%%v%', { i: i, v: 1 });
    boxEl.appendChild(label);
    for (let j = 0; j < count; j++) {
      const item = document.createElement('div');
      item.className = 'item' + (j === count - 1 && count >= 2 ? ' new' : '');
      item.textContent = '' + (totalItems - count + j + 1);
      boxEl.appendChild(item);
    }
    arena.appendChild(boxEl);
  });
}

function dropItem() {
  // Choose a random box
  const target = Math.floor(Math.random() * numBoxes);
  boxes[target]++;
  totalItems++;

  renderArena();
  updateCounter();

  // Check invariant: if items > boxes, collision MUST exist
  const hasCollision = boxes.some(c => c >= 2);

  if (hasCollision && !collisionOccurred) {
    collisionOccurred = true;
    const collisionBox = boxes.findIndex(c => c >= 2) + 1;
    setStatus(
      fmt('✓ Collision in box %collisionBox%! The pigeonhole principle guaranteed this.', { collisionBox: collisionBox }),
      'warn'
    );
    // Verify the invariant is correct
    console.assert(
      totalItems > numBoxes || hasCollision,
      'Invariant: collision must exist when items > boxes'
    );
  } else if (!hasCollision) {
    if (totalItems === numBoxes) {
      setStatus('Every box has exactly one item — one more drop must collide.', 'ok');
    } else {
      setStatus('Drop items to fill the boxes.', '');
    }
  }

  // Verify the core claim: totalItems > numBoxes => collision exists
  if (totalItems > numBoxes) {
    console.assert(hasCollision, 'Pigeonhole: items > boxes must imply collision');
  }
}

function setStatus(text, cls) {
  const s = document.getElementById('status');
  s.textContent = text;
  s.className = 'status ' + cls;
}

function updateCounter() {
  document.getElementById('counter').textContent =
    fmt('Items placed: %totalItems%  |  Boxes: %numBoxes%  |  Collision guaranteed when items > %numBoxes%', { totalItems: totalItems, numBoxes: numBoxes });
}

document.getElementById('dropBtn').addEventListener('click', dropItem);
document.getElementById('resetBtn').addEventListener('click', init);
document.getElementById('boxCount').addEventListener('change', init);

init();

<p class="hint">Choose the number of boxes, then drop items one by one. The moment you exceed the box count, a <b>collision is guaranteed</b> — no matter where you drop.</p>
<div class="controls">
  <label>Boxes: <select id="boxCount">
    <option value="3">3</option>
    <option value="4">4</option>
    <option value="5" selected>5</option>
    <option value="6">6</option>
    <option value="7">7</option>
  </select></label>
  <button id="dropBtn" type="button">Drop item</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
</div>
<div id="arena" class="arena"></div>
<div class="status" id="status">Drop items to fill the boxes.</div>
<div id="counter" class="counter"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .9rem; }
label { font-size: .9rem; }
select { font: inherit; padding: .2rem .4rem; border: 1px solid #ccc; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.arena { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: .6rem; }
.box { flex: 1 1 60px; min-width: 52px; border: 2px solid #8aa8c2; border-radius: 10px;
       padding: 6px 4px 4px; background: #eef3f7; display: flex; flex-direction: column;
       align-items: center; gap: 4px; min-height: 60px; transition: background .2s, border-color .2s; }
.box.collision { background: #fde8ea; border-color: #e63946; }
.box-label { font-size: .7rem; color: #556; font-weight: 600; letter-spacing: .04em; }
.item { width: 24px; height: 24px; border-radius: 50%; background: #1d3557;
        display: flex; align-items: center; justify-content: center;
        font-size: .65rem; color: #fff; font-weight: 700; animation: pop .15s ease; }
.item.new { background: #e63946; }
@keyframes pop { from { transform: scale(.4); opacity: .3; } to { transform: scale(1); opacity: 1; } }
.status { font-size: 1rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.status.ok { color: #0a7d33; }
.status.warn { color: #c92f3c; }
.counter { font-size: .85rem; color: #555; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Pigeonhole demo: drop items randomly into boxes.
// The principle guarantees: once items > boxes, some box holds >= 2.
// We verify this invariant after every drop.

let boxes = [];       // boxes[i] = count of items in box i
let totalItems = 0;
let numBoxes = 5;
let collisionOccurred = false;

function init() {
  numBoxes = parseInt(document.getElementById('boxCount').value, 10);
  boxes = new Array(numBoxes).fill(0);
  totalItems = 0;
  collisionOccurred = false;
  document.getElementById('dropBtn').disabled = false;
  renderArena();
  setStatus('Drop items to fill the boxes.', '');
  updateCounter();
}

function renderArena() {
  const arena = document.getElementById('arena');
  arena.innerHTML = '';
  boxes.forEach((count, i) => {
    const boxEl = document.createElement('div');
    boxEl.className = 'box' + (count >= 2 ? ' collision' : '');
    const label = document.createElement('div');
    label.className = 'box-label';
    label.textContent = fmt('Box %i%%v%', { i: i, v: 1 });
    boxEl.appendChild(label);
    for (let j = 0; j < count; j++) {
      const item = document.createElement('div');
      item.className = 'item' + (j === count - 1 && count >= 2 ? ' new' : '');
      item.textContent = '' + (totalItems - count + j + 1);
      boxEl.appendChild(item);
    }
    arena.appendChild(boxEl);
  });
}

function dropItem() {
  // Choose a random box
  const target = Math.floor(Math.random() * numBoxes);
  boxes[target]++;
  totalItems++;

  renderArena();
  updateCounter();

  // Check invariant: if items > boxes, collision MUST exist
  const hasCollision = boxes.some(c => c >= 2);

  if (hasCollision && !collisionOccurred) {
    collisionOccurred = true;
    const collisionBox = boxes.findIndex(c => c >= 2) + 1;
    setStatus(
      fmt('✓ Collision in box %collisionBox%! The pigeonhole principle guaranteed this.', { collisionBox: collisionBox }),
      'warn'
    );
    // Verify the invariant is correct
    console.assert(
      totalItems > numBoxes || hasCollision,
      'Invariant: collision must exist when items > boxes'
    );
  } else if (!hasCollision) {
    if (totalItems === numBoxes) {
      setStatus('Every box has exactly one item — one more drop must collide.', 'ok');
    } else {
      setStatus('Drop items to fill the boxes.', '');
    }
  }

  // Verify the core claim: totalItems > numBoxes => collision exists
  if (totalItems > numBoxes) {
    console.assert(hasCollision, 'Pigeonhole: items > boxes must imply collision');
  }
}

function setStatus(text, cls) {
  const s = document.getElementById('status');
  s.textContent = text;
  s.className = 'status ' + cls;
}

function updateCounter() {
  document.getElementById('counter').textContent =
    fmt('Items placed: %totalItems%  |  Boxes: %numBoxes%  |  Collision guaranteed when items > %numBoxes%', { totalItems: totalItems, numBoxes: numBoxes });
}

document.getElementById('dropBtn').addEventListener('click', dropItem);
document.getElementById('resetBtn').addEventListener('click', init);
document.getElementById('boxCount').addEventListener('change', init);

init();

Notice: when every box already holds one item, the very next drop must create a shared box. You cannot avoid it by being clever about where you click — the math forbids it. This is the essence of the principle: it is a counting argument that leaves no room for strategy.

The principle is proven — it is a theorem, not a conjecture. The proof is a one-line contradiction: if every box held at most one item, the total number of items would be at most n, but we placed n+1. Contradiction.

The generalized form is even more useful: if n·k + 1 items are placed into n boxes, at least one box must hold k+1 or more items. This lets us prove statements like "among any 13 people, at least two were born in the same month."

Surprising consequences:

• Hair counts in a city: a human head has at most around 200,000 hairs. London has more than 9 million people. Therefore at least $\lceil 9{,}000{,}000 / 200{,}000 \rceil = 45$ people in London share the exact same number of hairs. You cannot name which ones — but the principle proves they exist.
• The birthday paradox: with 367 people in a room, two must share a birthday (365 days + leap day = 366 pigeonholes). The probabilistic birthday problem asks when a collision becomes likely — a subtler question answered by Catalan numbers and probability theory.
• Compression is impossible to win universally: any lossless algorithm maps file strings to shorter strings. But there are more strings of length n than of length n−1, so some two inputs must map to the same output — making the algorithm fail on at least one of them. The pigeonhole principle makes this inevitable.
• Rational approximation (Dirichlet, 1834): for any real number $\alpha$ and integer N, there exist integers p and q with $1 \le q \le N$ and $|\alpha - p/q| \le 1/(qN)$. The proof slots the N+1 fractional parts $\{0\cdot\alpha\}, \{1\cdot\alpha\}, \ldots, \{N\cdot\alpha\}$ into N equal subintervals of [0,1) and invokes the principle.

The pigeonhole principle is a solved tool — fully proven, with no open questions about its validity. What remains open is the question of how cleverly it can be applied in new settings.

"More items than containers" appears across computer science and mathematics whenever we count:

• Hash tables: a hash function maps a large key space to a fixed-size table. Since there are more keys than slots, collisions are mathematically guaranteed. Every hash table design must therefore handle them — chains, open addressing, or cuckoo hashing all exist because the pigeonhole principle says they are necessary.
• Network routing: an Internet router with n output links cannot route n+1 simultaneously arriving packets without buffering or dropping at least one. The pigeonhole principle sets the fundamental capacity limit.
• Data compression: as seen above, any lossless scheme must enlarge some inputs. The principle explains why universal compression is impossible.
• Graph theory and Ramsey theory: many results in graph coloring and Ramsey theory are pigeonhole arguments in disguise — color the edges, note that n+1 edges land on n color classes, conclude that some class is large.
• Cryptography: birthday attacks on hash functions exploit the probabilistic version — with enough messages, two will hash identically. The attack is practical because collisions are not rare; the pigeonhole principle guarantees their existence from the start.

Learn to spot "more items than containers" and you have unlocked one of the most versatile proof techniques in discrete mathematics.

The Pigeonhole Principle is perhaps the only mathematical theorem whose proof you understood before you ever heard the word "theorem." Put more things in fewer boxes — one box must overflow. Simple.

Yet from that simplicity flows a river of non-trivial results: two strangers in a city sharing a hair count, compression algorithms that must fail on some input, hash collisions that every programmer must handle, Dirichlet's sharp bounds on rational approximation, and birthday attacks that break naive cryptographic designs.

The principle is proven beyond doubt — the only open question is where it will show up next. Any time you hear "there are more X than Y," the pigeonhole principle is already at work, silently guaranteeing a collision you might not have noticed. Keep it in your toolkit alongside P vs NP and the other great lenses of theoretical computer science.