On BMO Round 1, a proof that invokes the Pigeonhole Principle earns marks only if the examiner can verify that the partition is valid before the counting begins. A gap in a proof is to announce that “by PHP, some box contains two objects” without ever showing that the boxes are disjoint and exhaustive. This article walks through a concrete decision—how to define the boxes before counting the objects—so that your write-up is complete rather than hopeful.
The Decision: Partition First, Count Second
The Pigeonhole Principle states that if more than m objects are placed into m boxes, at least one box contains at least two objects. In olympiad practice, the difficulty is never the statement itself; it is the construction of the boxes. A BMO marker will not guess your partition. You must define it explicitly, prove it covers every object, and only then compare the number of objects to the number of boxes.
Consider the following teaching illustration, constructed to isolate this decision:
Teaching illustration (not a contest problem): Prove that among any 7 integers, there exist three whose sum is divisible by 3.
Step 1 — Define the boxes by residue modulo 3. Let the boxes be
Box 0 = {integers ≡ 0 (mod 3)},
Box 1 = {integers ≡ 1 (mod 3)},
Box 2 = {integers ≡ 2 (mod 3)}.
These three boxes are disjoint and together contain every integer. The partition is locked before any counting occurs.
Step 2 — Count objects and apply the pigeonhole bound. We have 7 integers (objects) and 3 residue classes (boxes). By the Pigeonhole Principle, at least one box contains ⌈7/3⌉ = 3 integers. If a box of residue r contains three integers, their sum is congruent to 3r, which is 0 modulo 3 for each r = 0, 1 or 2. Thus any box containing three integers supplies the required triple.
Step 3 — Check why a box with three integers is forced. Suppose no box contains 3 integers. Then the maximum per box is 2, so the distribution across 3 boxes can hold at most 6 integers. But we have 7 integers. Therefore some box must contain 3, contradicting the supposition. Hence the condition in Step 2 always occurs, and the proof is complete.
The critical move was Step 1: the residue classes were named explicitly, proved disjoint, and proved exhaustive. Only after that did counting begin.
Contrasting Case: A Superficially Similar Approach That Fails
Students often try to force a pigeonhole argument where the natural structure is different. Here is a deliberate misfire:
Flawed attempt: Prove that among any 5 integers, there exist two whose sum is divisible by 4.
A student might define boxes by residue modulo 4: {0}, {1}, {2}, {3}. They might then argue that with 5 integers and 4 boxes, two share a residue, so their difference is divisible by 4. But the problem asks about the sum, not the difference. The student has defined boxes that solve the wrong problem. Even if they notice the sum condition and try to pair residues (0 with 0, 1 with 3, 2 with 2), the arithmetic fails: the list {1, 1, 1, 1, 1} contains five integers, yet no two sum to a multiple of 4. The statement itself is false for 5 integers, and no partition repair can save it.
The lesson: defining boxes is not enough. The boxes must be tailored to the exact condition in the problem, and the threshold (number of objects versus boxes) must be checked against a counterexample.
Diagnostic Application: Check Your Partition Discipline
Try this self-test:
Problem: Given 11 distinct integers chosen from {1, 2, …, 19}, prove that there exist two whose sum is 20.
Annotated reasoning:
- Target condition: Find two distinct integers with sum 20.
- Define boxes: Form the pairs {1, 19}, {2, 18}, …, {9, 11}. These are 9 boxes. The integer 10 is left unmatched because 10 + 10 = 20 requires a repeated integer, and the problem specifies distinct integers.
- Verify coverage: Every integer from 1 to 19 appears in exactly one box or as the singleton 10. The boxes are disjoint and exhaustive.
- Count objects: We select 11 integers. If we avoid a sum of 20, we can take at most one from each of the 9 paired boxes (9 integers) and possibly the singleton 10 (1 integer), for a maximum of 10 integers without a matching pair.
- Apply threshold: With 11 integers, we exceed this maximum. Therefore at least one paired box contributes both its members, giving two integers whose sum is 20.
Why 10 fails: The set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} contains 10 integers with no pair summing to 20. The threshold of 11 is tight. The counterexample establishes that 11 is the smallest forcing number. This strengthens the result; proving optimality is an additional task, not a requirement for the original existence statement unless the question asks for the smallest bound.
What the Diagnostic Result Means for Your Next Step
If you defined the pairs correctly but forgot to account for the singleton 10, your next task is to verify exhaustiveness—check that every element of the ambient set belongs to exactly one box. If you used 10 integers instead of 11, your next task is optimality checking: construct the counterexample explicitly to show the bound cannot be lowered. If you paired 1 with 3 instead of 1 with 19, your boxes were misaligned with the target condition; revisit Step 1 before counting.
Preparation Context for the 2026-27 Season
BMO Round 1 on 19 November 2026 consists of six proof questions over 3.5 hours. Partial credit is awarded for significant progress, which includes a correctly defined pigeonhole structure even if the final inequality is not resolved. For China-region students, direct registration is available without prior SMC participation, though SMC scores remain useful context. Registration closes 9 November 2026.
For further technique development, see The BMO1 Number Theory and Combinatorics Toolkit: Parity, Invariants, Pigeonhole and the Right Modulus for an overview of combinatorial tools, BMO Extremal Principle: Choosing the Largest or Smallest Object to Start a Proof for another structural starting move, and How BMO Solutions Are Marked: Writing Proofs That Score (2026-2027) for mark-scheme specifics.
From Partition to Proof: The Three-Step Verification Loop
Once you have defined your boxes and counted your objects, the work is not finished. A common failure mode in BMO Round 1 is stopping at the inequality n > m without verifying that the pigeonhole conclusion actually satisfies the problem’s specific condition. This gap between “some box has two items” and “those two items sum to a multiple of k” is where marks are lost. To bridge it, apply a three-step verification loop to every pigeonhole argument before writing the final line.
Step 1: Verify the Box Condition Matches the Target Property. Ask explicitly: “If two objects land in the same box, does that guarantee the property I need?” In the teaching illustration about sums divisible by 3, placing two integers with residue 1 into Box 1 guarantees their difference is divisible by 3, but their sum is congruent to 2 mod 3. The box definition must be tailored so that co-membership implies the target relation. For sums modulo 3, we needed three integers from the same box (0+0+0≡0) or one from each box (0+1+2≡0). Simply having two in one box was insufficient for the sum condition. Always test the implication: if x,y ∈ Box_i, then P(x,y)? If no, redefine the boxes.
Step 2: Check Exhaustiveness Against Edge Cases. Ensure every possible object falls into exactly one box. In the diagnostic problem involving pairs summing to 20 from {1,…,19}, the integer 10 was excluded from paired boxes because 10+10=20 requires repetition, which distinctness forbids. If you had accidentally placed 10 into a pair like {10,10}, you would violate disjointness. If you omitted 10 entirely from the partition, you would fail exhaustiveness—what if the selected set includes 10? The correct handling treats 10 as a singleton box that cannot contribute a pair. Verify that the union of all boxes equals the ambient set, and intersections are empty.
Step 3: Validate Tightness with a Counterexample. Before concluding, construct a maximal configuration that avoids the desired outcome. If you claim n objects force a pair, show that n−1 objects do not. In the sum-to-20 problem, the set {1,2,…,9,10} contains 10 integers with no pair summing to 20. This proves the threshold of 11 is sharp. If no counterexample is found at n−1, the bound may be improvable, or the search may simply be incomplete. This alone neither proves nor refutes the original argument. Show sharpness when the problem asks for the smallest possible bound. An existence proof at the stated bound can be complete without a sharpness argument.
Apply this loop to the flawed attempt mentioned earlier: proving two integers among five have a sum divisible by 4. Step 1 fails immediately. Residue classes modulo 4 do not ensure sums divisible by 4 upon collision. Two numbers ≡1 mod 4 sum to 2 mod 4. Even pairing residues (1 with 3) requires careful counting across different boxes, not just within one. The natural structure for sums divisible by 4 involves grouping residues {0}, {2}, {1,3}. With five integers, PHP on these three groups gives ⌈5/3⌉=2 in some group. If two are in {0}, sum ≡0. If two in {2}, sum ≡0. If two in {1,3}, they could be both 1s (sum 2) or both 3s (sum 6≡2), failing the condition. Thus, even a refined partition does not save the false claim. The counterexample {1,1,1,1,1} confirms impossibility. Recognizing this early saves time and prevents invalid proofs.
This verification discipline transforms pigeonhole arguments from hopeful guesses into rigorous proofs. It forces you to confront whether your boxes truly encode the required relationship, whether they cover all possibilities, and whether your count is optimal. Practice this loop on every combinatorial proof until checking becomes automatic.
Frequently Asked Questions
Why should a pigeonhole proof define its boxes explicitly?
The reader must be able to check that each object has an assigned box, that the count forces a shared box, and that sharing it implies the required property. Naming the principle alone does not supply those missing steps.
How do I know if my threshold is tight enough?
A counterexample at n−1, together with a proof that n always works, establishes sharpness. If no counterexample is found, the bound may still be valid; the search may be incomplete or the bound may be improvable. Sharpness is required when the question asks for a smallest threshold, not for every existence proof.
Can I use the Pigeonhole Principle in BMO Round 2 as well?
Yes. Round 2 problems in combinatorics and number theory often require more sophisticated partitions, such as residue classes modulo a composite or geometric regions with measure arguments. The same discipline—define boxes first—applies.