Maths Olympiad Prep

Library / Danube Mathematical Competition /16 of 28

Danube Mathematical Competition

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+b−c−da + 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 2013∣b−d2013 \mid b - d, and, since ∣b−d∣≤2012|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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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