Maths Olympiad Prep

Library / /12 of 22

Combinatorics Difficulty 5.8 AIME, harder Prove it Romania

Consider 64 distinct natural numbers less than or equal to 2012. Prove that among them there are four numbers, denoted by a,b,c,da, b, c, d, such that a+bcda + b - c - d is a multiple of 2013.

Solution

Using the 64 given numbers, there can be formed 2016 pairs (a,b)(a, b), with a<ba < b; these pairs generate 2016 sums a+ba+b which give 2016 remainders when divided by 2013. Consequently, there are two different pairs (a,b)(a, b) and (c,d)(c, d) having the same remainder when divided by 2013, hence 2013(a+b)(c+d)2013 \mid (a+b) - (c+d).

Assuming that (a,b)(a, b) and (c,d)(c, d) have a common component, e.g. a=ca = c, then 2013bd2013 \mid b - d, and, since bd2012|b-d| \le 2012, we get b=db = d, 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.

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