In one sentence
Put objects into boxes, and at least one box holds two or more.
The reason takes one line: if every box held at most one, there would be at most objects, not .
Everyone understands this sentence. The real skill is that the problem never hands you the boxes: you have to build them yourself. Build them well, and “two in the same box” is exactly the pair the problem is asking for.
Predict first
Choose any numbers from . Must two of them add up to ?
Yes, always. Split the ten numbers into pairs, each adding up to . When numbers fall into pairs, some pair must be chosen completely.
Example: choose 6 numbers from 1 to 10; two of them must add up to 11
Step 1 / 4- First, try to avoid it
Pick . Any two add up to at most , so there is no clash. numbers can avoid it.
Solving a problem with the pigeonhole principle really means answering three questions: What are the objects? What are the boxes? What does it mean for two to share a box?
Stop 1 · Building the boxes (Vol. 7)
Sometimes the boxes are hidden a little deeper.
Choose any numbers from . Prove that one of them is a multiple of another.
Every positive integer can be written as “an odd number × some s”. Put numbers with the same odd part in the same box: for two numbers in the same box, the larger one is , or times the smaller one.
Example: choose 6 numbers from 1 to 10; one must be a multiple of another
Step 1 / 4- First, try to avoid it
Pick . None of these five numbers is a multiple of another.
Stop 2 · Residue systems (Vol. 6)
When you divide integers by , there are only possible remainders: . Remainders are natural boxes, and two numbers in the same box have a difference that is a multiple of .
Example: among any 6 integers, two have a difference that is a multiple of 5
Step 1 / 3- The boxes: remainders
Sort by the remainder when dividing by : that gives boxes. Only to are drawn here, but every other integer goes into one of these five boxes too.
You can even use the boxes twice in a row.
Example: among any 5 integers, three have a sum that is a multiple of 3
Step 1 / 4- The boxes: remainders mod 3
Put the integers into three boxes: “remainder ”, “remainder ”, “remainder ”. There are two cases.
Stop 3 · Boxes in a figure (Vol. 4)
In geometry the boxes are small regions: cut the figure into a few pieces, and two points in the same piece cannot be too far apart.
Place any points in a square of side (edges included).
Predict first
You want the points to be as far apart from each other as possible. How large can “the distance between the closest two points” be?
Cut the big square into four small squares of side . With points and small cells, two points must land in the same cell. The farthest apart two points in one small cell can be is opposite corners, at distance . So the closest two points are never more than apart, and the four corners plus the center reach exactly .
The Pythagorean theorem is used only once here: a square of side has a diagonal of length . What really does the work is “”.
Practice
What is the smallest number of numbers you must choose from to guarantee that two of them add up to ?
What is the smallest number of integers you must take to guarantee that two of them have a difference that is a multiple of ?
What is the smallest number of numbers you must choose from to guarantee that one of them is a multiple of another?