In one sentence
If there are more objects than boxes, some box holds more than one.
The idea fits in one sentence. Its power is that you never need to know how the objects were placed.
Why you can't avoid it
Step 1 / 4- Suppose you can avoid it
Suppose there is a way to place the balls so that every one of the boxes has at most ball. Let us count how many balls such a placement can hold at most.
Predict first
Put balls into boxes. However you do it, the fullest box holds at least how many balls?
If every box held at most , there would be room for only balls. There are , so some box holds at least .
Try it below: can you keep every box at or fewer? Then change the numbers of balls and boxes and watch how the “unavoidable” number changes.
In a real problem, nobody tells you what the “balls” and the “boxes” are. In the four stops below the principle is the same but the boxes look completely different, and at every stop, choosing the right boxes is the whole solution.
Stop 1 · Integers: sort by remainder
Among any integers, there are two whose difference is a multiple of . Why?
First pick numbers from to , trying to make sure no two of them differ by a multiple of . How many can you pick at most? Then try the options under “Boxes” one by one: which way of sorting proves “at most ”?
There are only five remainders on division by : . With numbers and boxes, two numbers have the same remainder, and numbers with the same remainder differ by a multiple of . Boxes = remainders.
Stop 2 · Pairing: lock the “troublemakers” up together
If you take any numbers from to , two of them add up to .
Predict first
Don't look below yet. To prove this, how would you sort to into boxes?
The conclusion we want is “the sum is ”, so make the two numbers in each box add up to exactly : , which is boxes. Take numbers and two of them must come from the same box.
The trick is to think backwards: whatever you want to collide, put in the same box.
Stop 3 · Geometry: cut the shape up
Put any points in a square of side . Two of them are at most apart.
First drag the points to spread them as far apart as you can. Then choose a way to cut the square.
Getting the number of boxes right is not enough; the shape of the boxes must be right too. The two farthest points in one box must be no farther apart than the distance you want to prove.
Stop 4 · The same numbers, two kinds of boxes
Boxes are tailor-made for the conclusion. Both problems below start with “take numbers from to ”, but the conclusions differ, so the boxes are completely different.
One problem, several solutions
Take any numbers from to . Prove that (a) two of them are coprime; (b) there are two of them such that one is a multiple of the other.
(a) Coprime: lock up neighbors together
Use as boxes. Among numbers, two share a box. They are neighbors, so they are coprime.
CostThe boxes are easy to find: two consecutive integers are always coprime.
(b) Multiples: lock up “doubling chains” together
Keep halving a number until you reach an odd number. Put the numbers that end at the same odd number together: , , , … There are odd numbers from to , so there are exactly boxes. Of two numbers in the same box, the larger is , , , … times the smaller.
CostThe boxes are hard to find, but once you see them it is one step.
Each side also offers the other side's boxes. Swap them around and see why they do not work.
What if there are no more objects than boxes?
Break it
Counterexample lab: remove one condition
Conclusion: Two points are at most apart ← still true?
points and small squares. With “2×2 small squares” chosen, however you drag, one square is always outlined in bold: two points are crowded into it.
Remove one point, leaving . Now drag them close to the four corners of the square and see how far apart you can push the “closest pair”.
With one point in each corner, every two points are at least apart, more than . If there are no more points than boxes, the principle guarantees nothing. This also shows that the in “ points” cannot be made any smaller.
Practice
A bag holds balls of each of four colors: red, yellow, blue and green. With your eyes closed, what is the smallest number of balls you must take out to be sure of having of the same color?
You take any integers and want to be sure that two of them differ by a multiple of . What is the smallest ?
From the numbers to , what is the smallest number you must take to be sure that two of them add up to ?
Prove: if you put any points in a square of side , two of them are at most apart.
Take some numbers from to so that no number is a multiple of another. What is the largest number you can take? (Show both that you cannot take more, and that you really can take that many.)