Maths Olympiad Prep

Library / Romanian Mathematical Olympiad /103 of 275

Romanian Mathematical Olympiad

Number theory Difficulty 5.5 AIME, harder Prove it Romania

Show that there exists a multiple of 20132013 which ends in 20142014.

Solution

Consider the numbers a1,a2,…,a2014a_1, a_2, \dots, a_{2014}, where aka_k is the 4k4k-digit number whose digits are kk groups of the form 20142014, 1≤k≤20141 \le k \le 2014. Since there are only 20132013 possible remainders after the division by 20132013, two different aas must give the same remainder in this division, hence there exists i,ji, j, with 1≤j<i≤20141 \le j < i \le 2014, so that ai−aja_i - a_j is divisible by 20132013. Since
ai−aj=20142014…2014⏟i−j times 201400…0⏟4j times=20142014…2014⏟i−j times 2014⋅100…0⏟4j times=ai−j⋅104j a_i - a_j = \underbrace{20142014\dots2014}_{i-j \text{ times } 2014} \underbrace{00\dots0}_{4j \text{ times}} = \underbrace{20142014\dots2014}_{i-j \text{ times } 2014} \cdot \underbrace{100\dots0}_{4j \text{ times}} = a_{i-j} \cdot 10^{4j}
and 104j10^{4j} and 20132013 are relatively prime, 20132013 must divide ai−ja_{i-j}.

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.