2. What is the smallest possible sum of four natural numbers such that pairs formed from these numbers have the greatest common divisors of $2, 3, 4, 5, 6$, and 9? Provide an example of a quadruple $s$ with such a sum and explain why there does not exist a quadruple $s$ with a smaller sum.

(Tomáš Jurík)
Solution. Suppose we have four numbers with the required properties. Since exactly three pairs have an even greatest common divisor (GCD), exactly three of them are even and one is odd (they cannot all be even, and two even numbers are insufficient for three even GCDs). Let the three even numbers be $a, b,$ and $c$, such that for their GCDs with the odd number $d$, we have $(d, a)=3, (d, b)=5, (d, c)=9$. From this, it follows that the even numbers $a, b, c$ are multiples of 6, 10, and 18, respectively, and the number $d$ must be a multiple of 45.

The numbers $a, c$ have a common divisor of 6, so it must be that $(a, c)=6$. The values of $(a, b)$ and $(b, c)$ are therefore 2 and 4 in some order. We have two possibilities:

- The numbers $a, b$ are multiples of 4. Then the numbers $a, b, c, d$ are multiples of 12, 20, 18, and 45, respectively. Such a suitable quadruple has the smallest sum $12+20+18+45=95$.
- The numbers $b, c$ are multiples of 4. Then the numbers $a, b, c, d$ are multiples of 6, 20, 36, and 45, respectively. Such a suitable quadruple has the smallest sum $6+20+36+45=107$.

The smallest possible sum is thus 95, corresponding to the quadruple 12, 20, 18, 45.

For a complete solution, award 6 points. Of these, 1 point should be awarded for mentioning that three of the four sought numbers are even and one is odd, and another point for determining that the individual numbers are multiples of 6, 10, 18, and 45. Award 2 points for using divisibility by four, and finally 2 points for the conclusion and determining the correct quadruple. For merely guessing the correct quadruple, award 2 points.