Or more precisely: if n + 1 objects are distributed into n containers, at least one container holds at least 2 objects.<\/strong><\/p>\n\n\n\n That’s it. The pigeonhole principle requires no algebra, no calculus, no advanced machinery. It is a statement about counting. And yet it produces some of the most surprising and elegant results in combinatorics, number theory, and geometry \u2014 including problems that appear regularly in the most challenging mathematics competitions in Canada and internationally.<\/p>\n\n\n\n Basic form:<\/strong><\/p>\n\n\n\n If n + 1 objects are placed into n containers, then at least one container contains at least 2 objects.<\/p>\n\n\n\n Generalised form:<\/strong><\/p>\n\n\n\n If m objects are placed into n containers where m > n, then at least one container contains at least \u2308m\/n\u2309 objects.<\/p>\n\n\n\n (Here \u2308m\/n\u2309 denotes the ceiling of m\/n \u2014 the smallest integer greater than or equal to m\/n.)<\/p>\n\n\n\n Why it’s true:<\/strong><\/p>\n\n\n\n Suppose for contradiction that every container holds at most 1 object. Then the total number of objects is at most n \u00d7 1 = n. But we have n + 1 objects \u2014 a contradiction. Therefore at least one container holds at least 2 objects. \u25a1<\/p>\n\n\n\n The proof by contradiction is essentially immediate. The difficulty in applying the pigeonhole principle is not in understanding the principle \u2014 it is in identifying the right objects and the right containers for a given problem.<\/p>\n\n\n\n Example 1 \u2014 Socks in a drawer<\/strong><\/p>\n\n\n\n A drawer contains red socks and blue socks. How many socks must you draw in the dark (without looking) to guarantee a matching pair?<\/p>\n\n\n\n Objects:<\/em> socks drawn. Containers:<\/em> colours (red, blue) \u2014 2 containers.<\/p>\n\n\n\n By the pigeonhole principle: drawing 3 socks guarantees at least one container (colour) has at least 2 \u2014 a matching pair.<\/p>\n\n\n\n Answer: 3 socks.<\/strong><\/p>\n\n\n\n Example 2 \u2014 Birthdays<\/strong><\/p>\n\n\n\n In a group of 13 people, must at least two share the same birth month?<\/p>\n\n\n\n Objects:<\/em> 13 people. Containers:<\/em> 12 months.<\/p>\n\n\n\n 13 > 12, so by the pigeonhole principle: yes. At least two people share a birth month.<\/p>\n\n\n\n Answer: Yes \u2014 guaranteed.<\/strong><\/p>\n\n\n\n Note: this does not tell you which month has two people, or who they are. It only guarantees that two people must share a month, purely from counting.<\/p>\n\n\n\n Example 3 \u2014 Handshakes<\/strong><\/p>\n\n\n\n At a party of 6 people, each person shakes hands with at least one other. Must at least two people shake hands with the same number of people?<\/p>\n\n\n\n Objects:<\/em> 6 people. Containers:<\/em> possible handshake counts.<\/p>\n\n\n\n Each person can shake hands with between 1 and 5 other people (1, 2, 3, 4, or 5 \u2014 they must shake at least one and cannot shake with themselves). That’s 5 possible values for 6 people.<\/p>\n\n\n\n 6 > 5, so by the pigeonhole principle: at least two people shake hands with the same number.<\/p>\n\n\n\n Answer: Yes \u2014 guaranteed.<\/strong><\/p>\n\n\n\n The generalised form is more powerful and produces tighter guarantees.<\/p>\n\n\n\n Generalised statement:<\/strong> If m objects are placed into n containers, at least one container holds at least \u2308m\/n\u2309 objects.<\/p>\n\n\n\n Example 4 \u2014 Guaranteed duplicates<\/strong><\/p>\n\n\n\n A bag contains marbles of 5 different colours. How many marbles must you draw to guarantee at least 4 marbles of the same colour?<\/p>\n\n\n\n Containers:<\/em> 5 colours. We want at least 4 in one container.<\/p>\n\n\n\n \u2308m\/5\u2309 \u2265 4 requires m \u2265 16 (since \u230815\/5\u2309 = 3, but \u230816\/5\u2309 = \u23083.2\u2309 = 4).<\/p>\n\n\n\n Answer: 16 marbles.<\/strong><\/p>\n\n\n\n Check: with 15 marbles, it’s possible to have exactly 3 of each colour (3 \u00d7 5 = 15). With 16, at least one colour must have 4 or more.<\/p>\n\n\n\n Example 5 \u2014 Numbers in a range<\/strong><\/p>\n\n\n\n From the integers 1 to 10, how many must you choose to guarantee two of them sum to 11?<\/p>\n\n\n\n Key insight:<\/em> Identify the pairs that sum to 11: {1,10}, {2,9}, {3,8}, {4,7}, {5,6}. These are 5 pairs \u2014 the containers.<\/p>\n\n\n\n If you choose 6 numbers from 1 to 10, by the pigeonhole principle, at least two must come from the same pair \u2014 and those two sum to 11.<\/p>\n\n\n\n Answer: 6 numbers.<\/strong><\/p>\n\n\n\n This example illustrates the key skill in pigeonhole problems: choosing the right containers. The pairs {1,10}, {2,9}, {3,8}, {4,7}, {5,6} are not immediately obvious \u2014 they must be constructed. Once constructed, the pigeonhole principle does the rest.<\/p>\n\n\n\n The real power of the pigeonhole principle emerges in harder problems where the objects and containers are not immediately obvious and must be cleverly constructed.<\/p>\n\n\n\n Prove that among any 5 integers, there exist two whose difference is divisible by 4.<\/strong><\/p>\n\n\n\n Setup:<\/em> Every integer has a remainder of 0, 1, 2, or 3 when divided by 4 \u2014 these are the 4 residue classes mod 4. These are our 4 containers.<\/p>\n\n\n\n Objects:<\/em> 5 integers.<\/p>\n\n\n\n 5 > 4, so by the pigeonhole principle, at least two integers share the same remainder when divided by 4.<\/p>\n\n\n\n If two integers a and b have the same remainder mod 4, then a \u2212 b \u2261 0 (mod 4), meaning 4 divides a \u2212 b.<\/p>\n\n\n\n Therefore their difference is divisible by 4.<\/strong> \u25a1<\/p>\n\n\n\n Given 5 points inside a unit equilateral triangle, prove that at least two points are within distance 1\/2 of each other.<\/strong><\/p>\n\n\n\n Setup:<\/em> Divide the equilateral triangle with side length 1 into 4 smaller equilateral triangles, each with side length 1\/2. (This is done by connecting the midpoints of the three sides.)<\/p>\n\n\n\n Objects:<\/em> 5 points. Containers:<\/em> 4 smaller triangles.<\/p>\n\n\n\n 5 > 4, so by the pigeonhole principle, at least one small triangle contains at least 2 of the 5 points.<\/p>\n\n\n\n The maximum distance between two points inside an equilateral triangle with side length 1\/2 is 1\/2 (the side length itself).<\/p>\n\n\n\n Therefore at least two of the 5 points are within distance 1\/2.<\/strong> \u25a1<\/p>\n\n\n\n This is a classic geometry pigeonhole argument. The key step \u2014 dividing the region into 4 smaller regions \u2014 is the insight. The pigeonhole principle then handles the rest.<\/p>\n\n\n\n Show that among any n + 1 integers chosen from {1, 2, …, 2n}, at least one divides another.<\/strong><\/p>\n\n\n\n Setup:<\/em> Write each chosen integer in the form 2^k \u00d7 m where m is odd (express each integer as a power of 2 times an odd number). The odd part m must be one of the odd numbers in {1, 3, 5, …, 2n \u2212 1} \u2014 there are n such odd numbers. These are our n containers.<\/p>\n\n\n\n Objects:<\/em> n + 1 chosen integers.<\/p>\n\n\n\n By the pigeonhole principle, at least two chosen integers share the same odd part m. Say these are 2^a \u00d7 m and 2^b \u00d7 m with a < b. Then 2^a \u00d7 m divides 2^b \u00d7 m.<\/p>\n\n\n\n Therefore one divides the other.<\/strong> \u25a1<\/p>\n\n\n\n This is one of the most elegant pigeonhole arguments \u2014 the construction of the containers (odd parts of the integers) is the mathematical insight, and the conclusion follows immediately.<\/p>\n\n\n\n The hardest part of a pigeonhole problem is almost never the application of the principle itself. It is constructing the right containers.<\/p>\n\n\n\n A general strategy:<\/strong><\/p>\n\n\n\n This backwards reasoning \u2014 starting from the conclusion and working toward the right container construction \u2014 is the skill that distinguishes students who can solve pigeonhole problems from those who know the principle but cannot apply it.<\/p>\n\n\n\n The pigeonhole principle is tested at every level of the Canadian competition mathematics ladder \u2014 and it rewards students who have genuinely understood it, not just memorised its statement.<\/p>\n\n\n\n Gauss Contest and AMC 8 (Grades 7\u20138):<\/strong> Simple pigeonhole problems \u2014 socks, birthdays, guaranteed duplicates \u2014 appear in Part A and Part B. These require knowing the principle and setting up the counting correctly, but the containers are usually provided or obvious. See our Gauss math contest guide<\/a> and AMC 8 guide<\/a>.<\/p>\n\n\n\n AMC 10 and Cayley\/Fermat Contests (Grades 9\u201311):<\/strong> Pigeonhole problems at this level require modular arithmetic as the container construction (like Example 6). The principle is not stated in the problem \u2014 the student must recognise that pigeonhole applies and construct the residue classes independently.<\/p>\n\n\n\n COMC Part C and Euclid Part C (Grade 12):<\/strong> Full-proof pigeonhole problems \u2014 requiring geometric subdivision (like Example 7) or algebraic container construction (like Example 8) \u2014 appear at the highest difficulty levels. These are the problems where container construction is the mathematical insight and pigeonhole is the tool that closes the argument. See our COMC math contest guide<\/a> and Euclid math contest guide<\/a>.<\/p>\n\n\n\n Canadian Mathematical Olympiad:<\/strong> The pigeonhole principle appears at the CMO level embedded within larger proofs \u2014 often as a lemma rather than the main argument. Combinatorics problems at the CMO frequently use pigeonhole-type reasoning in combination with other techniques. See our Canadian Mathematical Olympiad guide<\/a>.<\/p>\n\n\n\n The pigeonhole principle is one of those ideas that looks simple on the surface and becomes more interesting the further you go. A student who genuinely enjoys the clever container constructions in Examples 6\u20138 is showing the kind of mathematical instinct that competition training develops and rewards. Think Academy’s competition mathematics programmes \u2014 from Gauss preparation through to Euclid and beyond \u2014 build exactly this combinatorial reasoning systematically. Find out what competition-level training looks like \u2192<\/a><\/p>\n\n\n\n Work through these before looking at the answers. For each problem, identify the objects, the containers, and the guarantee before setting up the count.<\/p>\n\n\n\n Set A \u2014 Direct application<\/strong><\/p>\n\n\n\n Set B \u2014 Number theory<\/strong><\/p>\n\n\n\n Set C \u2014 Harder applications<\/strong><\/p>\n\n\n\n Answers:<\/strong><\/p>\n\n\n\n What is the pigeonhole principle?<\/strong> If n + 1 objects are distributed into n containers, at least one container must hold at least 2 objects. More generally, if m objects are placed into n containers with m > n, at least one container holds at least \u2308m\/n\u2309 objects.<\/p>\n\n\n\n Why is it called the pigeonhole principle?<\/strong> The name comes from the image of pigeons (objects) being placed into pigeonholes (containers). If there are more pigeons than holes, at least one hole must contain more than one pigeon. The principle is also sometimes called the Dirichlet box principle, after the mathematician Peter Gustav Lejeune Dirichlet who formalised it.<\/p>\n\n\n\n Is the pigeonhole principle only useful in combinatorics?<\/strong> No \u2014 it appears across many mathematical domains. In number theory it produces divisibility and remainder results (Examples 5\u20137). In geometry it proves proximity results (Example 7). In combinatorics it establishes existence results (Example 8). It is a foundational tool across all of these areas at the competition level.<\/p>\n\n\n\n What is the hardest part of using the pigeonhole principle?<\/strong> Choosing the right containers. The principle itself is simple \u2014 the mathematical challenge is always in identifying or constructing a partition of the objects into containers such that (a) the number of containers is less than the number of objects, and (b) two objects sharing a container implies the desired conclusion.<\/p>\n\n\n\n Does the pigeonhole principle appear on Canadian mathematics competitions?<\/strong> Yes, at every level from the Gauss Contest through to the Canadian Mathematical Olympiad. Simple forms appear at Gauss and AMC 8 level; modular arithmetic applications at AMC 10 and Cayley level; geometric and algebraic applications in proof form at COMC and Euclid Part C level.<\/p>\n\n\n\n Who invented the pigeonhole principle?<\/strong> The principle is attributed to Peter Gustav Lejeune Dirichlet (1805\u20131859), a German mathematician. It is sometimes called Dirichlet’s box principle or Dirichlet’s drawer principle in continental European mathematical traditions.<\/p>\n\n\n\n See our related guides: Canadian Mathematical Olympiad guide<\/a> \u00b7 Euclid math contest guide<\/a> \u00b7 COMC math contest guide<\/a> \u00b7 math induction proof guide<\/a> \u00b7 proof by contradiction guide<\/a> \u00b7 contrapositive math guide<\/a> \u00b7 Gauss math contest guide<\/a> \u00b7 AMC 8 guide<\/a> \u00b7 math enrichment guide<\/a><\/em><\/p>\n\n\n\n
\n\n\n\nThe Pigeonhole Principle: Formal Statement<\/h2>\n\n\n\n
\n\n\n\nSimple Examples<\/h2>\n\n\n\n
\n\n\n\n
\n\n\n\n![\"\"](\"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-6-2026-03_13_25-PM-1-1024x430.png\")
<\/a><\/figure>\n\n\n\n
\n\n\n\nThe Generalised Pigeonhole Principle<\/h2>\n\n\n\n
\n\n\n\n
\n\n\n\nCompetition-Level Applications<\/h2>\n\n\n\n
Example 6 \u2014 Number Theory (AMC 10 \/ Cayley level)<\/h3>\n\n\n\n
\n\n\n\nExample 7 \u2014 Geometry (COMC \/ Euclid level)<\/h3>\n\n\n\n
\n\n\n\nExample 8 \u2014 Combinatorics (Euclid \/ CMO level)<\/h3>\n\n\n\n
\n\n\n\nThe Pigeonhole Principle in Practice: Strategy<\/h2>\n\n\n\n
\n
\n\n\n\nWhere the Pigeonhole Principle Shows Up in Contests<\/h2>\n\n\n\n
![\"\"](\"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-6-2026-03_15_14-PM-1-1024x429.png\")
<\/a><\/figure>\n\n\n\n
\n\n\n\nPractice Problems<\/h2>\n\n\n\n
\n
\n
\n
\n\n\n\n\n
\n\n\n\nFrequently Asked Questions<\/h2>\n\n\n\n
\n\n\n\n
\n\n\n\n![\"pigeonhole](\"https:\/\/blog-admin.thethinkacademy.com\/wp-content\/uploads\/2026\/08\/ChatGPT-Image-Aug-6-2026-03_18_41-PM-1-1024x430.png\")
<\/a><\/figure>\n","protected":false},"excerpt":{"rendered":"