Twenty minutes on one counting problem, then you give up and open the solution. It’s three lines long, and the first line says “By the pigeonhole principle.” You follow every step, and every step is right, but you have no idea how anyone looked at that problem and saw pigeons.
You do know the pigeonhole principle. You know that with socks of two colors in a drawer, 3 socks pulled out blind guarantee a matching pair. The trouble is that this problem had no socks in it. Somewhere inside it were boxes, and whoever wrote the solution found them before line one, in the part nobody writes down.
That part is a skill, and you can practise it. Start with three questions that tell you when a problem wants pigeonhole, then build the boxes yourself on five original problems, grade 4 to grade 10.
Why Doesn’t Knowing the Principle Help You Solve the Problem?
You probably met the pigeonhole principle like this. You got the statement, a sock drawer and maybe a question about birthdays. Then you read solutions. Each one made sense, so it felt like progress, and after ten of them the idea felt solid.
Then a problem asks about numbers that add up to 25, or remainders when you divide by 8, or rabbits in a field. Nothing in it looks like a drawer. You never think of pigeonhole, because this time the problem doesn’t hand you the boxes. Every example you practised printed them on the page (two colors, twelve months), and this one makes you build them.
So the principle sits in your head, known and unused. The cost is quiet: a pile of problems that stay closed, and hours of practice spent reading other people’s boxes when you could have been finding your own.
A 1995 olympiad training note from the Hong Kong University of Science and Technology put it simply: “forming the right boxes is the key to success.” Even the best explanations say the trick is choosing the boxes, then teach it only by example. In our view, that means you see plenty of boxes and almost never practise finding one.
What Is the Pigeonhole Principle, in One Line?
The pigeonhole principle says that if you put more items into boxes than there are boxes, some box gets two or more. The general form: put n items into m boxes and some box holds at least n ÷ m, rounded up. Put 25 students into 6 rooms: 25 ÷ 6 is about 4.2, so some room holds at least 5.
The German mathematician Peter Dirichlet used it in the 1840s and later called it the Schubfachprinzip, the drawer principle, which is why you’ll also see it called Dirichlet’s box principle.
That’s the whole statement. Everything hard about it lives in one word, boxes, because in a real problem nobody tells you what they are.
How Do You Know a Problem Wants Pigeonhole?
This is the check we use. Ask the three questions in order.
- Does it ask what must happen? Look for “at least”, “must”, “always”, “prove that two” or “the fewest you need to be sure”.
- What can’t you control? Which sock comes out, which numbers get picked, where a point lands. Those are your pigeons.
- What’s the smallest list of places each pigeon can land? Those are your boxes, so count them.
Try it on a small one: prove that among any 8 days, two fall on the same day of the week. Question 1 says yes, because “prove that two” is a must. Question 2: you don’t choose which 8 days, so the days are the pigeons. Question 3: every day is one of 7 weekdays, so there are 7 boxes. Eight pigeons, seven boxes, and two days share a weekday.
When a question asks for the fewest you need, the answer is usually one more than the worst case you can build without the thing happening. For “two the same”, that worst case is one pigeon in every box. For “k the same”, it’s k − 1 in every box, as long as every box can hold that many. Problem 2 below shows what happens when one box can’t.
If a problem fails all three questions, it probably isn’t a pigeonhole problem at all, and a general method for any olympiad problem you’re stuck on is the better place to start.
Where Do the Boxes Come From?
The third question is where the work is. In the weekday problem the boxes sat in plain sight. Most of the time they don’t. In our experience, most pigeonhole problems at this level hide the boxes in one of four places, and each one leaves a clue in the wording.
| Box type | The clue in the question | What the boxes are | Practise it in |
|---|---|---|---|
| Categories | Colors, shapes, kinds of thing; “how many to be sure of two (or five) the same” | The categories themselves, already given | Problems 1 and 2 |
| Pairs | “Two of them add up to” a target number | Each pair that hits the target, plus a box of its own for every number with no partner | Problem 3 |
| Remainders | “Divisible by”, “a multiple of”, “differ by a multiple of” | The remainders you can get when you divide by that number | Problem 4 |
| Regions | Points in a shape or on a track; “within” or “how far apart” | Equal pieces you cut the shape into | Problem 5 |
Two habits make the last two rows easier. When the clue is divisibility, list the possible remainders before you do anything else, and then ask which of them can really occur. When the clue is distance, let the distance in the question decide the size of your pieces. Both habits come up in the problems below.
Five Pigeonhole Problems, Grade 4 to Grade 10
We wrote these five problems for this page; none is taken from a contest. The grade labels are a rough guide. Try each one before you open the solution, and answer the three questions on paper first. If you want to see what olympiad questions look like at each grade, these sit inside that range.
Problem 1 (Grade 4): Categories
A big jar holds animal stickers in 6 shapes: cats, dogs and owls, plus fish, frogs and bees. There are lots of each shape. Maya reaches in without looking. What is the fewest stickers she must take out to be sure she has two with the same shape?
Show solution
Answer: 7.
- Must? Yes: “to be sure”.
- Pigeons: the stickers Maya pulls out. She can’t control which ones she gets.
- Boxes: the 6 shapes.
Seven stickers and only 6 shapes means two stickers share a shape. Why isn’t 6 enough? Maya could pull out one of each shape: 6 stickers and no match. So 7 is the fewest.
Problem 2 (Grade 6): Categories, Five of a Kind
A gym bin holds team pinnies: 10 red, 10 blue, 10 yellow and 2 green. The coach grabs pinnies without looking. What is the fewest pinnies the coach must grab to be sure of 5 the same color, enough for one team of five?
Show solution
Answer: 15.
- Must? Yes: “to be sure”.
- Pigeons: the pinnies the coach grabs.
- Boxes: the 4 colors. One box is small, though. Green can never hold more than 2.
Build the worst case first. Before any color reaches 5, the coach can hold 4 red, 4 blue, 4 yellow and both greens. That’s 4 + 4 + 4 + 2 = 14 pinnies with no color at 5, so 14 isn’t enough.
Now grab a 15th. At most 2 of the 15 are green, so at least 13 are red, blue or yellow. Put 13 pinnies into 3 color boxes and some box holds at least 13 ÷ 3 rounded up, which is 5. So 15 is the fewest.
If you plug straight into the general form with 4 colors, you get 4 × 4 + 1 = 17. That many is enough, but it isn’t the fewest, because the green box can’t hold 4.
Problem 3 (Grade 7): Pairs
A bag holds 20 tiles numbered 1 to 20. You draw tiles without looking. What is the fewest tiles you must draw to be sure that two of them add up to 25?
Show solution
Answer: 13.
- Must? Yes: “to be sure”.
- Pigeons: the tiles you draw.
- Boxes: groups where any two tiles in the same group add up to 25.
The pairs that make 25 are 5 and 20, 6 and 19, 7 and 18, and so on up to 12 and 13. That’s 8 pairs, so 8 boxes. The tiles 1 to 4 have no partner, because 25 − 4 = 21 is bigger than 20. Each of them gets a box of its own. Total: 8 + 4 = 12 boxes.
Why isn’t 12 enough? Draw the tiles 1 to 12. The two biggest add up to 11 + 12 = 23, so no two of them make 25.
Why does 13 work? Thirteen tiles and 12 boxes means two tiles share a box. A one-tile box can’t hold two tiles, so the shared box is one of the pairs, and those two tiles add up to 25.
Problem 4 (Grades 8–9): Remainders
Pick some different positive perfect squares (1, 4, 9 and so on). What is the fewest squares you must pick to be sure that two of them differ by a multiple of 8?
Show solution
Answer: 4.
- Must? Yes: “to be sure”.
- Pigeons: the squares you pick.
- Boxes: two whole numbers differ by a multiple of 8 exactly when they leave the same remainder after you divide by 8. So the boxes are remainders.
There are 8 possible remainders (0 to 7), which suggests the answer is 9. Before you write that down, ask which remainders a square can leave.
- An odd number is 2k + 1, and its square is 4k(k + 1) + 1. One of k and k + 1 is even, so 4k(k + 1) is a multiple of 8. The remainder is 1.
- An even number is 2k, and its square is 4k². If k is even, 4k² is a multiple of 16, so the remainder is 0. If k is odd, k² is odd and 4k² leaves remainder 4.
So every square leaves remainder 0, 1 or 4. That’s only 3 boxes. Pick 4 squares and two of them share a remainder, so they differ by a multiple of 8.
Why isn’t 3 enough? Take 1, 4 and 16. Their remainders are 1, 4 and 0. The differences are 3, 12 and 15, and none of them is a multiple of 8. So 4 is the fewest.
Problem 5 (Grade 10): Regions
A drone photographs a rectangular field 40 m long and 30 m wide and counts 13 rabbits in it. Treat each rabbit as a point. Show that some two rabbits are no more than 15 m apart.
Show solution
Answer: cut the field into 12 squares, each 10 m on a side. Two rabbits must share a square, so they are at most about 14.1 m apart.
- Must? Yes: “show that some two”.
- Pigeons: the 13 rabbits.
- Boxes: pieces of the field. Each piece has to be small enough that any two rabbits inside it are within 15 m, and there have to be fewer than 13 pieces.
Cut the field into a 4 by 3 grid of squares, 10 m on a side. That makes 12 squares. A rabbit sitting on a shared edge can count in either square, so just pick one. Thirteen rabbits and 12 squares means two rabbits share a square. The farthest apart two points in a 10 m square can be is the length of its diagonal, 10 × √2, which is about 14.1 m. So those two rabbits are at most 14.1 m apart, under 15 m.
Why this cut? The distance in the question sets the box size. A square with side s has a diagonal of s × √2, so you need s × √2 to be 15 or less. That allows a side up to about 10.6 m. A 10 m side divides both 40 and 30 evenly and gives 12 squares, one fewer than the rabbits. A 5 m grid keeps rabbits close too, but it makes 48 squares for 13 rabbits, and the argument falls apart.
When these start to feel easy, look at what an AIME problem looks like and try the three questions on it.
You started with a three-line solution you could follow but couldn’t have found. Now you have a check that tells you when a problem wants pigeonhole, four places to look for the boxes and five problems where you built the boxes yourself. Use them on the next solution you open. When it starts with “by pigeonhole”, cover everything after the first line, answer the three questions and find the boxes before you read on. Do that with five solutions in a row and the first line stops looking like a magic trick.
For more problems to practise on, the Berkeley Math Circle posts free pigeonhole handouts for its intermediate group, like this October 2024 handout. If you’d like a contest to try these on, this guide to middle school math contests helps you pick one.
Finding boxes takes reps, and reps work best in order. That’s the thinking behind Gonit’s line “A sequence. Not a pile of problems.” Gonit has 10,000+ original questions for grades 1–12, and its combinatorics and logical reasoning questions are a good place to keep practising the three questions.
Make Preparing for Math Olympiad Simple!
FAQ
What is the pigeonhole principle in simple terms?
If you put more items into boxes than there are boxes, at least one box ends up with two or more. With n items and m boxes, some box gets at least n ÷ m, rounded up. In problems, the hard part is deciding what the boxes are.
Why is it called the pigeonhole principle?
A pigeonhole is a small open compartment in a desk for letters, and the word first meant a small hole for pigeons to nest. The English name comes from translating Dirichlet’s German and French words for drawer. That’s also why it’s called Dirichlet’s box principle or the drawer principle.
Who came up with the pigeonhole principle?
The earliest known written mention is in a 1622 Latin book by the French Jesuit Jean Leurechon, which says two people must have the same number of hairs or coins. The German mathematician Peter Dirichlet used it in the 1840s and later called it the Schubfachprinzip, or drawer principle.
Related guides
- How to solve math word problems when you don’t know where to start
- MATHCOUNTS practice problems for every round
Donald A. Kroll holds a Master's degree in Mathematics and has spent years helping students prepare for competition-level problem solving. Based in the United States, he writes about study strategy, test readiness, and the habits that turn steady practice into real results.
There are no comments posted here yet.
Sign in to leave a comment