Belarus — Selection and Training Session

Recall (with proof) two well-known facts:
Lemma 1. The series $\sum_{i=1}^{+\infty} \frac{1}{i}$ is divergent. In other words for each $c \in \mathbb{R}$ there exists $m$ such that $\sum_{i=1}^{m} \frac{1}{i} \ge c$.
Proof. Note that $\sum_{i=2}^{2^{a+1}} \frac{1}{i} \ge \sum_{i=2}^{2^{a+1}} \frac{1}{2^{a+1}} = \frac{1}{2}$. Grouping the terms this way we obtain that $\sum_{i=1}^{2^t} \frac{1}{i} \ge 1 + \frac{t}{2}$ which can be sufficiently large.

Lemma 2. Order all prime numbers in ascending order: $p_1 < p_2 < \dots$. Then the product $\prod_{i=1}^{+\infty} \frac{1}{1 - \frac{1}{p_i}}$ is divergent. In other words for each $c \in \mathbb{R}$ there exists $m$ such that $\prod_{i=1}^{m} \frac{1}{1 - \frac{1}{p_i}} \ge c$.
Proof. By Lemma 1 for each $c \in \mathbb{R}$ there exists $m_0$ such that $\sum_{j=1}^{m_0} \frac{1}{j} \ge c$. Let all prime divisors of numbers between 1 and $m_0$ be among $p_1, p_2, \dots, p_m$ and the maximal exponent of these primes equal $\ell$. Then each integer $j$ from 1 to $m_0$ has the unique representation $p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{\alpha_m}$, $0 \le \alpha_i \le \ell$, $i = 1, \dots, m$. Hence,
$$\prod_{i=1}^{m} \frac{1}{1 - \frac{1}{p_i}} \ge \prod_{i=1}^{m} \left( 1 + \frac{1}{p_i} + \frac{1}{p_i^2} + \dots + \frac{1}{p_i^{\ell}} \right) \ge \sum_{j=1}^{m_0} \frac{1}{j} \ge c.$$

Solution of the problem. Choose an arbitrary $q \in (c, 1)$. Lemma 2 implies that there exists $L$ such that $\prod_{i=1}^{L} \frac{p_i - 1}{p_i} < 1 - q$. Denote $T = A p_1 p_2 \dots p_L$ where $A$ is an arbitrary even number.
Consider the set $U_T$ of all integers between 1 and $T$ which are divisible by at least one number from $p_1, p_2, \dots, p_L$. The cardinality of $U_T$ is
$$\sum_{i} \frac{T}{p_i} - \sum_{i \neq j} \frac{T}{p_i p_j} + \dots = T - T(1 - \frac{1}{p_1}) \dots (1 - \frac{1}{p_L}) \ge T - T(1 - q) \ge qT.$$
We will show that $U_T$ is good. Denote the sum of all elements of $U_T$ by $S$. The condition $\gcd(a_i, S - a_i) > 1$ is equivalent to $\gcd(a_i, S) > 1$. Hence it suffices to show that $S$ is divisible by $p_1 p_2 \dots p_L$.
Note that if $x \in U_T$ then $T - x \in U_T$ and their sum is divisible by $p_1 p_2 \dots p_L$. The numbers $T/2$ and $T$ are divisible by $p_1 p_2 \dots p_L$ (since $A$ is even) so $S$ is divisible by $p_1 p_2 \dots p_L$ as well.
Suppose we are given $K \ge 2p_1 p_2 \dots p_L$. By taking an appropriate $A$ choose $T$ to be the maximal integer such that $T \le K$ and $2p_1 p_2 \dots p_L \mid T$. All elements of the good set $U_T$ doesn't exceed $T$ and, moreover, $K$. The cardinality of $U_T$ is not less than $qT > q(K - 2p_1 p_2 \dots p_L) = qK - D$ where $D = 2qp_1 p_2 \dots p_L$ doesn't depend on $K$. Therefore for $K \ge D/(q-c)$ we obtain the inequality $qT \ge cK$ which implies that $U_T$ is the required good set.

Consequently $M = \lfloor D/(q-c) \rfloor$ satisfies the problem condition.