Maths Olympiad Prep

Library / /99 of 264

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, 1k20141 \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 1j<i20141 \le j < i \le 2014, so that aiaja_i - a_j is divisible by 20132013. Since
aiaj=201420142014ij times 20140004j times=201420142014ij times 201410004j times=aij104j 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 aija_{i-j}.

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.