Five objects, four boxes
Put five objects into four boxes, one at a time, and try to keep every box to a single object for as long as possible. The first four can go into four different boxes. Then every box holds one, and there is still an object in hand.
Four objects placed, one in each box, and one still to place.
The fifth has nowhere new to go
The fifth object has to go into a box that already holds one, and that box then holds two.
Placing them in a different order does not help. Four boxes with at most one object each hold at most 4 objects, and there are 5. So in every arrangement, some box holds at least two.
The fifth object goes into the first box, which now holds 2, while the others hold 1. Placed in any other order, some box would still hold 2.
The principle
If n objects are placed into k boxes and n > k, then some box holds at least two objects. The proof is the argument above. Suppose every box held at most one object. Then the k boxes would hold at most k objects, but there are n, which is more than k. That is impossible, so some box holds at least two.
It proves that such a box exists without saying which box it is. Often that is all a proof needs.
A drawer holds socks in 4 colors, mixed up in the dark. The colors are the boxes and the socks taken out are the objects. Four socks could be one of each color, with no pair. A fifth must match one of them, so 5 socks make a pair certain. Taking 8 also works, but a pair is forced long before that. With k colors, k + 1 socks are enough.
More than two in one box
The same argument gives more. Put 13 objects into 4 boxes. Suppose no box held 4 or more. Then each box would hold at most 3, and the four boxes at most 4 × 3 = 12 objects, one short of 13. So some box holds at least 4.
In general, if n objects are placed into k boxes, some box holds at least rounded up to a whole number. For 13 objects in 4 boxes, 13 ÷ 4 = 3.25, which rounds up to 4. Rounding down gives 3, which is what every box holds once 12 objects are placed; the thirteenth makes 4.
Nothing larger is forced. Dealt round the boxes in turn, the 13 objects land 4, 3, 3 and 3, so no box need hold 5.
13 objects dealt into 4 boxes in turn, as evenly as they go: 4, 3, 3 and 3. The fullest box holds 4, and 13 ÷ 4 = 3.25 rounded up is 4.
Remainders repeat, so decimals recur
Divide 1 by 7 by long division. Each step brings down a 0, divides by 7, and keeps a remainder smaller than 7. A remainder of 0 would end the division, and here it never comes, because 7 divides no power of 10. So every remainder is one of 1, 2, 3, 4, 5 and 6: six boxes.
Seven steps leave seven remainders, and there are only six possible values, so two of them are equal. Each step depends only on the remainder it starts from, so from the first repeat on, the division goes through the same steps again and writes the same digits again. The remainders run 1, 3, 2, 6, 4, 5 and then 1 again, and , with the block 142857 repeating.
The same holds for any fraction with denominator d: either a remainder of 0 ends the division, or at most d − 1 nonzero remainders are available and one of them must repeat.
The long division of 1 by 7 as its chain of remainders: 1, 3, 2, 6, 4, 5 and back to 1. The digit on each arrow is the digit that step writes, so the six arrows spell 142857.
The usual mistakes
Expecting to know which box. The principle says some box holds two, not which one.
Taking k socks for k colors. All k can differ; it takes k + 1.
Rounding down. 13 objects in 4 boxes force 4 into some box, not 3.
Multiplying where one more object is enough. To force 3 objects into one of 16 boxes takes 2 × 16 + 1 = 33 objects, not 3 × 16 = 48: with 32, every box can hold exactly 2.
Link codes and soil sensors
In the first application below, a link shortener’s four-character codes are the boxes and web addresses are the objects: there are codes, so 1679617 addresses make a shared code certain. In the second, a square plot is cut into 16 smaller squares, so 17 sensors put two in the same small square, no farther apart than its diagonal, .
Worked example: A Link Shortener's Four-Character Codes, and How Many Addresses Force a Shared Code
Question A company is designing a link shortener that would turn each web address into a code of 4 characters, each a lower-case letter or a digit, by a fixed rule, without checking whether a code is already in use. (a) How many different codes are there, and what is the smallest number of addresses that makes it certain that two of them get the same code? (b) Show that once 5000000 addresses have been shortened, some code is shared by at least 3 of them. How many more addresses would make it certain that some code is shared by at least 4?
1.Each of the 4 characters is one of 26 letters or 10 digits, which is 36 choices, and the choices multiply: 36 × 36 × 36 × 36 = 1679616 codes.
Each of the 4 places has 36 choices, so there are 364 = 1679616 codes. 2.With 1679616 addresses the rule could give every address its own code, so a shared code is not yet certain. With 1679617, if no code held two addresses there would be room for only 1679616, so two addresses share a code. (a) There are 1679616 codes, and 1679617 addresses make a shared code certain.
(a) 1679616 addresses can each have their own code; 1679617 cannot. 3.Suppose no code were shared by 3 or more of the 5000000 addresses. Then each code would hold at most 2, and all the codes together at most 2 × 1679616 = 3359232 addresses. That is fewer than 5000000, so some code is shared by at least 3.
At most 2 addresses per code covers only 3359232, fewer than 5000000, so some code has at least 3. 4.In the same way, up to 3 × 1679616 = 5038848 addresses could be spread with at most 3 to a code, so a code shared by 4 is certain only from 5038849 addresses.
At most 3 per code covers 5038848, so 5038849 addresses force a code shared by 4. 5.(b) That needs 5038849 − 5000000 = 38849 more addresses. Check: 50000001679616 ≈ 2.98, which rounds up to 3, the number of addresses on one code that is certain now.
(b) 5038849 − 5000000 = 38849 more addresses.
Answer: (a) 1679616 codes; 1679617 addresses; (b) 2 × 1679616 = 3359232 is less than 5000000, so some code is shared by at least 3; 38849 more addresses
Common mistakes
- Counting the codes as 36 × 4 = 144. Each of the 4 places has its own 36 choices, and the choices multiply, so there are 364 codes.
- Taking 4 × 1679616 = 6718464 as the number of addresses needed for a code shared by 4. Up to 3 to a code fits 5038848 addresses, and one more than that already forces a fourth onto some code.
Worked example: Seventeen Soil Sensors in a Square Plot, and a Radio Range of 15 m
Question A farmer places 17 soil sensors anywhere in a square research plot 40 m by 40 m, including its edges. Two sensors can pass readings to each other when they are no more than 15 m apart. (a) By dividing the plot into 16 equal squares, prove that some two sensors are no more than 15 m apart. What is the greatest distance two sensors in the same small square can be apart, to the nearest 0.01 m? (b) With the same 16 squares, what is the smallest number of sensors that makes it certain that some small square holds at least three of them? (Any one of those three is then within 15 m of the other two.)
1.Divide the plot into a 4 by 4 grid of squares, each 40 ÷ 4 = 10 m by 10 m. A sensor on an edge shared by two squares is counted in just one of them, so every sensor belongs to exactly one square.
Cut the plot into 16 squares, each 10 m by 10 m. 2.There are 17 sensors and 16 squares. If each square held at most one sensor, there would be at most 16 sensors, so some square holds at least two.
17 sensors in 16 squares: some square holds at least two. 3.Two points in a 10 m square are at most as far apart as opposite corners. By Pythagoras the diagonal is √102 + 102 = √200 ≈ 14.14 m. (a) The two sensors in one square are at most 14.14 m apart, which is within 15 m, so they can pass readings.
(a) Two sensors in one square are at most √200 ≈ 14.14 m apart, within 15 m. 4.Suppose every square held at most 2 sensors. Then there would be at most 2 × 16 = 32 sensors. So 33 sensors force some square to hold at least 3, while with 32 the farmer could place exactly 2 in each square.
With 32 sensors, the farmer could place exactly 2 in each square. 5.(b) The smallest number is 33. The three sensors in one square are each within 14.14 m of the other two, so one sensor can reach two others. Check: 3316 ≈ 2.06, which rounds up to 3.
(b) 33 sensors force 3 into one square.
Answer: (a) Some small square holds two sensors, which are at most 14.14 m apart; (b) 33 sensors
Common mistakes
- Using the side of a small square, 10 m, as the greatest distance inside it. Two sensors at opposite corners are √200 ≈ 14.14 m apart, and that is the distance to compare with 15 m.
- Answering 48 in (b), three for each of the 16 squares. Three sensors are needed in only one square, and 2 in every square is 32, so the 33rd sensor already makes three in some square.