Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A teacher writes some whole numbers on the board. She claims that whenever there are at least of them, two can always be found whose sum or difference is divisible by .
Prove her claim with the pigeonhole principle. Say clearly what the boxes are and how many there are. Then show that numbers are not always enough, by giving six numbers with no such pair. Finally state the fewest numbers that always contain such a pair.
If objects go into boxes, some box holds at least two. Decide what the objects and the boxes are. A "fewest number" answer needs a proof that it is enough and an example showing that one fewer can fail.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Sort the numbers by their remainder on division by . Pair up remainders that add to .
Step 1. The boxes. Make the boxes , , , , and . Every remainder lies in exactly one box, and there are boxes.
Step 2. Two numbers in one box. With numbers and boxes, two numbers and fall in one box. If their remainders are equal, is divisible by . If their remainders are and , then is divisible by . The boxes and hold only equal remainders, so the difference works there.
Step 3. Six numbers can fail. Take 0, 1, 2, 3, 4, 5. Each difference is between and , so none is divisible by . Each sum of two different numbers is between and , so none is divisible by either.
Step 4. Conclusion. Seven numbers always work and six may not. The fewest number is .
Watch out. The box cannot be paired with anything: needs two numbers with remainder , and then their difference works anyway.
Answer: boxes, and the fewest number is . Proof complete.
Log in to join the discussion.
Loading…