Back to the on-screen lesson ·
More objects than boxes forces a crowded box; how to choose the boxes, why the rounding goes up, and exactly how little the conclusion says.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the pigeonhole principle with its ceiling, prove it in two lines by contradiction, and apply it by naming the objects and choosing the boxes — which is where every real difficulty lies. You will also be able to run it backwards to find how many objects force a box of a given size, and to say exactly what the conclusion does and does not claim: some box, never a named one, and nothing about how the objects were distributed.
Lesson 15 counted the injections from $A$ to $B$ and found there are none when $|A| > |B|$ — the targets run out. That is this lesson's principle, already proved. What is added is the habit of choosing the boxes, which is where every difficulty in using it lies.
$\lceil x \rceil$ is the ceiling of $x$: the smallest whole number at least as large. The pigeonhole principle says that $m$ objects in $n$ boxes force some box to hold at least $\lceil m/n \rceil$ of them. The objects and boxes are whatever the argument chooses them to be, and choosing them is the whole technique.
The principle. Put $m$ objects into $n$ boxes. Then some box holds at least $\lceil m/n \rceil$ objects.
The proof is two lines by contradiction. Suppose every box held at most $\lceil m/n \rceil - 1$. Then the total is at most $n(\lceil m/n \rceil - 1) < m$, and the objects do not fit. So some box is crowded.
Read what it claims, carefully. It says some box. It does not say which, it does not say how many boxes are crowded, and it says nothing about how the objects got distributed — indeed the proof never looks at a single box. It is a pure existence claim, established without producing the thing whose existence it claims, which is why it feels like it should not work.
Rounding up, not down. Thirteen people in twelve months: $13/12$ is a little over one, and the ceiling is two, so two people share a birth month. Rounding down would give one, which is true of every box and guarantees nothing.
Run backwards. The useful form is usually the other question: how many objects are needed to force a box of $k$? The worst case is every box holding $k-1$, which accounts for $n(k-1)$, and that arrangement is genuinely possible. So $n(k-1) + 1$ is the answer, and the plus one is not a safety margin — it is exactly the first number that leaves no room.
The technique is choosing the boxes. The principle itself is trivial. What makes a pigeonhole argument is deciding what the objects are, what the boxes are, and why there are fewer boxes than objects — and the last of those is often the only hard step.
Another way: steps
To use the principle:
Another way: example
Among any five integers, two leave the same remainder on division by four. Objects: the five integers. Boxes: the four remainders $0, 1, 2, 3$. Five into four, so two share a box — and two integers with the same remainder have a difference divisible by four, which is the conclusion worth having.
| Objects | Boxes | What falls out |
|---|---|---|
| $n+1$ integers | the $n$ remainders mod $n$ | two with a difference divisible by $n$ |
| $n+1$ points in a square of side $s$ | $n$ smaller squares | two points close together |
| the guests at a party | the possible friend counts | two guests with the same count |
The third is the one worth studying, because it does not work as stated: $n$ guests have $n$ possible friend counts, $0$ through $n-1$, and $n$ objects in $n$ boxes force nothing. The argument needs one more observation — that $0$ and $n-1$ cannot both occur, since a friendless guest and a universally befriended one cannot coexist — which prunes the boxes to $n-1$ and lets the principle bite.
That extra observation is typical. The principle is the last line of a pigeonhole argument, and everything interesting happens before it.
Rounding down. $\lceil m/n \rceil$, always. The average guarantees nothing.
Naming the crowded box. The principle does not identify it, and an argument that goes on to use the crowded box by name has assumed something it was not given.
Confusing the two questions. What is guaranteed by $m$ objects and how many objects force $k$ are different, and the answers differ by more than a rounding.
Using it where the boxes are not disjoint. Every object must go into exactly one box; if an object could be in two, the count on the left is wrong before the principle is reached.
The principle is not probabilistic and has nothing to do with what is likely. It holds for every distribution, including the deliberately even ones: with $13$ people and $12$ months, it does not matter how the birthdays were chosen, and no arrangement avoids a shared month. That is what makes it a proof rather than an expectation, and it is why the conclusion is guaranteed even though nothing in the argument ever looked at a single person.
Claim: among any six integers, two have a difference divisible by five. Objects: the six integers.
Name the objects first.
Boxes: the five possible remainders on division by five. Every integer goes into exactly one box.
The boxes are remainders, and they are disjoint.
Six objects, five boxes, so two share a remainder — and two integers with the same remainder have a difference divisible by five. The difficulty was choosing remainders as the boxes; the principle itself was one line.
The choice was the work.
Ten socks, three colours. What is guaranteed? $\lceil 10/3 \rceil = 4$, so some colour appears at least four times.
Divide and round up.
How many socks are needed to guarantee four of one colour? The worst case is three of each, which is nine socks and is genuinely possible.
Find the largest arrangement that avoids the conclusion.
So ten is the answer, and here the two questions happen to meet. They usually do not: to guarantee five of one colour needs thirteen, while ten guarantees only four.
Two different questions with two different arithmetics.
Objects: the eight people. Boxes: the seven days of the week, and every person was born on exactly one.
Name the objects and the boxes, and check the boxes are disjoint.
Eight objects into seven boxes, so $\lceil 8/7 \rceil = 2$: some day holds at least two people.
Apply the principle, and round up.
Two people share a day of the week. Note what the argument never needed: nothing about how births are distributed, nothing about the particular eight people, and no example. The conclusion holds for every group of eight, which is what a proof gives and a survey never could.
There are $10$ socks to be shared among $3$ colours. Fill in the size some group is guaranteed to reach.
| Number | |
|---|---|
| How many socks | 10 |
| How many colours | 3 |
| Some group holds at least |
$10$ socks are shared among $3$ colours. What is the largest number the principle guarantees some group holds?
Answer:
With $3$ colours available, mark the smallest number of socks that guarantees some group holds $4$ of them.
0 |——————————| 40
Mark the position with a cross, then write the value:
$13$ people are shared among $12$ birth months. Which of these does the pigeonhole principle actually establish?
At a party of $7$ people, some pairs are friends. Put in order the steps of the argument that two people have the same number of friends present.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
There are $10$ socks to be shared among $3$ colours. Fill in the size some group is guaranteed to reach.
| Number | |
|---|---|
| How many socks | 10 |
| How many colours | 3 |
| Some group holds at least |
You can choose objects and boxes, apply the principle with the rounding the right way, and say how many objects force a given crowd. Say in your own words why the rounding goes up, and why the principle never tells you which box is crowded. Next: graphs, where the objects are vertices and the boxes are degrees.
10. Your turn: show that among any $8$ people, two were born on the same day of the week, step 3