Maths Olympiad Prep

Library / /19 of 39

Number theory Difficulty 5.5 AIME, harder Find the answer Italy

Problem:

Luca writes on a blackboard all the possible sequences consisting of 2017 distinct positive integers whose sum is 2016201720182016 \cdot 2017 \cdot 2018. Having done this, he replaces each of these sequences with the greatest common divisor of its elements. When this lengthy operation is finished, what is the maximum among the numbers written on the blackboard?

Pick one

Solution

Solution:

The answer is (B). Consider a sequence b1,b2,,b2017b_{1}, b_{2}, \ldots, b_{2017} of positive integers, all distinct, whose sum is 2016201720182016 \cdot 2017 \cdot 2018. Let dd be the greatest common divisor of the elements of this sequence. By definition, the numbers a1:=b1/d,a2:=b2/d,,a2017:=b2017/da_{1}:=b_{1} / d, a_{2}:=b_{2} / d, \ldots, a_{2017}:=b_{2017} / d are also positive integers, all distinct, and their sum is therefore at least equal to the sum 1+2++20171+2+\cdots+2017. We then have
201620172018=b1++b2017=d(a1+a2++a2017)d(1+2++2017)=d201720182, 2016 \cdot 2017 \cdot 2018 = b_{1} + \cdots + b_{2017} = d \cdot (a_{1} + a_{2} + \cdots + a_{2017}) \geq d \cdot (1+2+\cdots+2017) = d \cdot \frac{2017 \cdot 2018}{2},
from which d22016d \leq 2 \cdot 2016. On the other hand, letting D=22016D = 2 \cdot 2016, the sequence D,2D,3D,,2017DD, 2D, 3D, \cdots, 2017D is one of the sequences that are written on the blackboard, and clearly the greatest common divisor of its elements is exactly DD.

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 translated into English from it; metadata (topic, difficulty) added by this project.