Problem 11.3. (15 points) Natural numbers $a, b, c$ are such that $1 \leqslant a<b<c \leqslant 3000$. Find the greatest possible value of the quantity

$$
\text { GCD }(a, b)+\text { GCD }(b, c)+\text { GCD }(c, a)
$$
Answer: 3000.

Solution. Note that GCD $(a, b)=$ GCD $(a, b-a) \leqslant b-a$, since the GCD of two natural numbers does not exceed either of them. Similarly, we obtain that GCD $(b, c) \leqslant c-b$, and also GCD $(c, a) \leqslant a$.

Adding these three inequalities, we get

$$
\text { GCD }(a, b)+\text { GCD }(b, c)+\text { GCD }(c, a) \leqslant(b-a)+(c-b)+a=c \leqslant 3000
$$

As an example for 3000, we can provide, for instance, $a=1000, b=2000, c=3000$. In this case, GCD $(a, b)+$ GCD $(b, c)+$ GCD $(c, a)=1000+1000+1000=3000$.

## Criteria

The points for the estimate and the example are summed.

+14 p. Estimate - it is proven that the considered sum does not exceed 3000.

In the absence of such a proof, the following progress is evaluated:

+4 p. It is noted that the GCD of different natural numbers does not exceed their difference, but there is no further progress.

+1 p. Example - numbers $a, b, c$ are provided for which the considered sum equals 3000 (or it is otherwise proven that such numbers exist).

The following progress is not evaluated:

0 p. Only the answer is provided.

0 p. An incomplete enumeration, in which one of the cases is not considered, and this case is not analogous to the considered ones.