Consider 64 distinct natural numbers less than or equal to 2012. Prove that among them there are four numbers, denoted by , such that is a multiple of 2013.
Solution
Using the 64 given numbers, there can be formed 2016 pairs , with ; these pairs generate 2016 sums which give 2016 remainders when divided by 2013. Consequently, there are two different pairs and having the same remainder when divided by 2013, hence .
Assuming that and have a common component, e.g. , then , and, since , we get , contradiction. The conclusion now follows.
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.