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}+\cdots +\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\ne j}\frac{T}{p_i{p}_j}+\cdots =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=2q{p}_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.