KA-0175The pigeonhole principle
5 points, difficulty 3 of 3Level 11–12about 150sWhat is the smallest number n such that ANY collection of n whole numbers must contain two of them whose difference is divisible by 7?
Hints
Take them one at a time. The first gives nothing away.
1A nudge
Two numbers differ by a multiple of 7 when their remainders agree.
2The strategy
There are only 7 possible remainders: 0, 1, 2, 3, 4, 5, 6. Those are the pigeonholes.
3The full solution
Seven numbers could have all seven different remainders, so seven is not enough. Eight numbers must repeat a remainder, so n = 8.
Solution
The reliable way
The difference of two numbers is divisible by 7 precisely when the two leave the same remainder on division by 7. There are exactly 7 possible remainders, so treat those as boxes. With 7 numbers you could get one in each box - for example 0, 1, 2, 3, 4, 5, 6, no two of which differ by a multiple of 7 - so 7 is not enough. With 8 numbers there are more numbers than boxes, so some box holds two, and those two differ by a multiple of 7. The answer is 8. The transferable idea: identify the boxes precisely, then the answer is boxes plus one.
The elegant way
Seven remainders are seven pigeonholes, so the eighth number forces a repeat.
Why this is on the test: Naming the pigeonholes correctly is the whole problem; once they are remainders modulo 7 the answer is immediate.