On this page
Most pigeonhole problems look impossible until you name the boxes. After that, the proof is usually three lines.
What is the pigeonhole principle?
The pigeonhole principle says that if more than n objects go into n boxes, at least one box contains more than one object (Wolfram MathWorld). MathWorld credits Dirichlet with first stating it in 1834, which is why it is also called Dirichlet's box principle.
The general form is the one you will use most: if N objects go into k boxes, some box holds at least ⌈N/k⌉ objects, where ⌈ ⌉ means "round up". The proof is one line: if every box held at most ⌈N/k⌉ − 1 objects, the total would be less than N.
How do you choose the pigeonholes?
Ask these four questions every time.
What must two objects share? That shared property is your box.
How many values can it take? That is k.
How many objects are there? That is N. You need N > k, or N > m·k to force m + 1 into one box.
Once two objects share a box, why does that finish the proof? Write this step out; it is where marks are lost.
Common matches between the question and the boxes:
"Two of the same colour": one box per colour.
"Two share a birth month": 12 boxes, one per month.
"Difference divisible by n": n boxes, one per remainder on division by n.
"Some sum divisible by n": boxes for the remainders of running totals.
"Two subsets with equal sums": one box per possible sum.
How do you solve sock-drawer and birthday-month problems?
Socks. A dark drawer holds red, blue and black socks. How many must you take to be sure of a pair? Three colours give 3 boxes. Three socks can all differ, but the fourth must repeat a colour, so the answer is 4.
For two black socks from 10 red, 10 blue and 10 black, you might draw all 20 red and blue first, so you need 22.
Birth months. Among 13 people, two share a birth month, because 13 people go into 12 boxes. To guarantee three with the same month you need 2 × 12 + 1 = 25 people, since ⌈25/12⌉ = 3.
That is certainty, not chance. For the chance version, read the probability that two people share a birth month and the birthday problem worked out.
How does it solve divisibility questions?
Example 1. Among any 6 integers, two have a difference divisible by 5. Remainders on division by 5 are 0, 1, 2, 3 or 4: five boxes. Six integers in five boxes means two, a and b, share a remainder, so 5 divides a − b.
Example 2. Among any n integers a₁, …, aₙ, some block of consecutive terms has a sum divisible by n. Form the running totals S₁ = a₁, S₂ = a₁ + a₂, up to Sₙ. If one leaves remainder 0, you are done. If not, n totals share only n − 1 nonzero remainders, so two of them, Sᵢ and Sⱼ with i < j, match. Their difference, aᵢ₊₁ + … + aⱼ, is divisible by n.
The boxes in Example 2 are not the numbers but a quantity built from them. The same habit drives the invariant method in olympiad maths.
How is it used in olympiads and JEE?
IMO 1972 Problem 1 asks you to prove that from any set of ten distinct two-digit numbers you can select two disjoint subsets with the same sum (problem statement). The solution in the Kalva IMO archive counts 2¹⁰ − 1 = 1,023 non-empty subsets, each with a sum of at most 90 + 91 + … + 99 = 945 (Kalva archive solution). Sums run from 10 to 945, only 936 possible values, so two different subsets share a sum. Remove the numbers they have in common; both sums drop equally, leaving two disjoint subsets with equal sums.
In the JEE Main 2025 syllabus that NTA publishes, the maths counting unit covers "the fundamental principle of counting, permutations and combinations" and does not name the pigeonhole principle (NTA syllabus page). For JEE, treat it as a quick check on "minimum number to guarantee" answers; for olympiads, where proofs are marked, it is a core tool.
If your boxes keep coming out wrong, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can see why one choice of boxes works. To revise remainders first, the Fermi Concept Library gives each mathematics concept its own lesson.
Try it now: pick any 11 numbers from 1 to 20 and show that two of them differ by a multiple of 10.
