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 , it is clear that their sum is divisible by their difference. If their difference is , 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 . In other words, we can choose at most one number of any three consecutive numbers. This implies that we can choose at most numbers.
Now, we will show that we can choose such numbers from any consecutive numbers. Suppose that these numbers are . If is divisible by , we can choose . If is not divisible by , we can choose .
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.