A brief note on The Pigeonhole Principle . Read it before a test. Try each question at the end before you open its answer.
The principle Simple form: n + 1 n + 1 n + 1 objects in n n n boxes put at least two objects in some box. Generalised form: N N N objects in k k k boxes put at least ⌈ N k ⌉ \left\lceil \dfrac{N}{k} \right\rceil ⌈ k N ⌉ in some box. Forcing r r r : with k k k boxes, k ( r − 1 ) + 1 k(r - 1) + 1 k ( r − 1 ) + 1 objects make sure of r r r in one box. Averages: some number of a list is at least the average. A fewest-number answer needs two parts: a proof that it is enough and an example that one fewer fails. Choosing the boxes Remainders: m + 1 m + 1 m + 1 whole numbers include two with a difference divisible by m m m . Pairs: put r r r and m − r m - r m − r together for "a sum or a difference". Prefix sums: S 0 = 0 , S 1 , … , S m S_0 = 0, S_1, \dots, S_m S 0 = 0 , S 1 , … , S m give a block of neighbours with a sum divisible by m m m . Odd parts: n + 1 n + 1 n + 1 numbers from 1 1 1 to 2 n 2n 2 n include one that divides another. Pieces of a figure: two points in one piece are at most the width of the piece apart. Erdős and Szekeres: n 2 + 1 n^2 + 1 n 2 + 1 different numbers have a monotone run of length n + 1 n + 1 n + 1 . A worked example Show that among any 6 6 6 whole numbers, two have a difference divisible by 5 5 5 .
Objects and boxes. The six numbers, and the five remainders 0 0 0 to 4 4 4 . The principle. Two numbers share a remainder. Conclusion. Their difference is divisible by 5 5 5 . Practice with new numbers
A program to try The program checks two pigeonhole answers by trying every case.
Read it first. Then run it. Does the first answer match the pairs { 1 , 12 } , { 2 , 11 } , … \{1, 12\}, \{2, 11\}, \dots { 1 , 12 } , { 2 , 11 } , … ?
1. Change 13 to 11 in the first part, two times. Predict the new answer first.
Mistakes to avoid Rounding down where the ceiling is needed. Using k r kr k r in place of k ( r − 1 ) + 1 k(r - 1) + 1 k ( r − 1 ) + 1 . Forgetting S 0 = 0 S_0 = 0 S 0 = 0 in a prefix-sum argument. Boxes that overlap or miss some objects. No example for "one fewer is not enough". Check yourself How many people make sure that two share a birth month? Stuck? Show a hint Show the answer33 33 33 pencils go into 4 4 4 cups. At least how many pencils are in the fullest cup? Stuck? Show a hint Show the answerHow many whole numbers make sure that two have a difference divisible by 9 9 9 ? Stuck? Show a hint Show the answerFive points lie in a square of side 4 4 4 cm. How close must two of them be? Stuck? Show a hint Show the answerGive a list of 4 4 4 different numbers with no run of 3 3 3 going up or going down. Stuck? Show a hint Show the answerSources R. A. Brualdi, Introductory Combinatorics , Chapter 3. A. Engel, Problem-Solving Strategies , Chapter 4.