Skip to main content

TL;DR

If n items are placed into m containers with \( n > m \), at least one container holds more than one item. The generalized form: some container holds at least \( \lceil n/m \rceil \) items.

By Valenke Exam Prep Team·Last updated 2026-06-03

Pigeonhole Principle

If n items are placed into m containers with \( n > m \), at least one container holds more than one item. The generalized form: some container holds at least \( \lceil n/m \rceil \) items.

Why it matters for interviews

A deceptively simple principle that solves existence problems in interviews. Used to prove that certain patterns must exist in sequences, that collisions are inevitable in hash functions, and in combinatorial game arguments.

Definition and Mathematical Foundation

If n items are placed into m containers with \( n > m \), at least one container holds more than one item. The generalized form: some container holds at least \( \lceil n/m \rceil \) items.

Application in Quantitative Finance

A deceptively simple principle that solves existence problems in interviews. Used to prove that certain patterns must exist in sequences, that collisions are inevitable in hash functions, and in combinatorial game arguments.

Related Concepts

Pigeonhole Principle

Related Terms

Ready to practice for the Quant Trading Interview?

Adaptive practice powered by Item Response Theory targets your weak areas. Start with 3 free sessions.

Start free practice →

Frequently Asked Questions

Can you give a classic pigeonhole interview problem?▼
Among any 5 points in a unit square, at least two are within distance \( \sqrt{2}/2 \). Proof: divide the square into 4 sub-squares of side 1/2. By pigeonhole, two points share a sub-square, and the maximum distance within is \( \sqrt{2}/2 \).
How does the pigeonhole principle relate to hash collisions?▼
If you hash n keys into m buckets with \( n > m \), at least one bucket has a collision. The birthday paradox quantifies: collisions become likely at \( \sqrt{m} \) keys.
What is the Erdos-Szekeres theorem?▼
Any sequence of more than \( mn \) distinct numbers contains an increasing subsequence of length \( m+1 \) or a decreasing subsequence of length \( n+1 \). Proved via pigeonhole.