Concepts and theorems · Intermediate

The pigeonhole principle: count when collisions are unavoidable

Compare object and container counts to reason about unavoidable collisions, generalized lower bounds, hashes, and probability claims.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Identify objects and containers
  2. Use remainders as the containers
  3. Generalize the lower bound
  4. Apply the principle to finite hashes
  5. Read the guarantee at its actual strength
  6. Verify a collision witness
  7. Ask Logeia about this articleCheck your understanding

Identify objects and containers

If more than n objects are placed into n containers, some container must contain at least two objects. The pigeons and holes are a counting metaphor; the containers might be hash values, integer remainders, or weekdays. Identify exactly what is counted as an object and what counts as a possible destination. Ambiguous object identity or an incorrectly counted set of destinations can invalidate an application even though the principle itself is correct. The conclusion is existential: a collision occurs somewhere. It does not automatically identify the colliding objects or give an efficient procedure for finding them.

Use remainders as the containers

Classify any six integers by their remainders modulo five. There are only five remainder classes, so two of the integers share one. Their difference is divisible by five. The argument does not require the integers to be consecutive, small, or positive; the mathematical remainder classes are what matters. With only five integers, every class could appear once, so a collision is not forced. To find a particular pair, inspect the actual remainders. The principle proves existence without performing that search, while an algorithm that records a previous member of each class supplies a concrete witness.

Generalize the lower bound

Distributing m objects among n containers forces at least one container to hold at least the ceiling of m divided by n. Ten jobs assigned across three workers therefore leave some worker with at least four jobs: three each would account for only nine. This is a lower bound on a maximum count, not a promise that the busiest worker has exactly four jobs. Nor does equal job count imply equal execution time when jobs have different costs. The unit being counted matters. A scheduling argument about item counts should not silently become a claim about processor time, memory demand, or network traffic.

Apply the principle to finite hashes

A k-bit hash has at most two to the k possible output values. Mapping more distinct inputs into that space forces a collision. Cryptographic hashing cannot avoid the mathematical existence of collisions when the input domain is larger than the output space. Security instead includes the difficulty of finding a collision within a realistic resource budget. Collisions can also occur well before the number of tried inputs exceeds the output count. Calculating their probability requires additional assumptions about the distribution and dependence of outputs. The counting principle alone does not provide a probability for an arbitrary sampling process or establish the practical work needed to find a collision.

Read the guarantee at its actual strength

Having no more objects than containers does not guarantee absence of collisions. Three objects can all be placed in one of five boxes. The principle supplies a sufficient counting condition for an unavoidable collision, not a rule forbidding collisions below that threshold. Sharing a container also does not mean the original objects are equal. A hash table must compare keys after a hash collision rather than treating equal hash values as identical keys. When applying the conclusion, distinguish proving that a pair exists, locating an actual pair, and establishing what that pair means for the surrounding software or mathematical problem.

Verify a collision witness

A program can retain one previous integer per remainder and return a pair when that remainder recurs. For example, seven and twelve differ by five, verifying a collision witness modulo five. Separate the existence argument from verification of the returned witness. This makes remainder conventions and the treatment of repeated input values visible rather than letting an implementation error hide behind a correct general counting theorem.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 13

Choose a learning path