Maths Olympiad Prep

Library / /80 of 105

Combinatorics Difficulty 6.4 National Olympiad Prove it JBMO

Problem:
What is the greatest number of integers that can be selected from a set of 2015 consecutive numbers so that no sum of any two selected numbers is divisible by their difference?

Solution

Solution:
We take any two chosen numbers. If their difference is 11, it is clear that their sum is divisible by their difference. If their difference is 22, they will be of the same parity, and their sum is divisible by their difference. Therefore, the difference between any chosen numbers will be at least 33. In other words, we can choose at most one number of any three consecutive numbers. This implies that we can choose at most 672672 numbers.

Now, we will show that we can choose 672672 such numbers from any 20152015 consecutive numbers. Suppose that these numbers are a,a+1,,a+2014a, a+1, \ldots, a+2014. If aa is divisible by 33, we can choose a+1,a+4,,a+2014a+1, a+4, \ldots, a+2014. If aa is not divisible by 33, we can choose a,a+3,,a+2013a, a+3, \ldots, a+2013.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.