
TN2b. ${ }^{7}$ Let $n(n \geq 1)$ be a positive integer and $U=\{1, \ldots, n\}$. Let $S$ be a nonempty subset of $U$ and let $d(d \neq 1)$ be the smallest common divisor of all elements of the set $S$. Find the smallest positive integer $k$ such that for any subset $T$ of $U$, consisting of $k$ elements, with $S \subset T$, the greatest common divisor of all elements of $T$ is equal to 1 .


Solution. We will show that $k_{\min }=1+\left[\frac{n}{d}\right]$ (here [.] denotes the integer part).

Obviously, the number of elements of $S$ is not grater than $\left[\frac{n}{d}\right]$, i.e. $|S| \leq\left[\frac{n}{d}\right]$, and $S \neq U$.

If $S \subset T$ and the greatest common divisor of elements of $T$ is equal to 1 , then $|T| \geq|S|+1$.

1) Assume that $|S|1$. Thus, $k \geq 1+\left[\frac{n}{d}\right]$.
2) Assume $|S|=\left[\frac{n}{d}\right]$. Let $T$ be any subset of $U$ with $S \subset T, S \neq T$. Therefore, $|T| \geq 1+\left[\frac{n}{d}\right]$. Let $q$ be the greatest common divisor of all elements of $T$. Assume that $q>1$. Therefore, $q$ is a common divisor of all elements of $S$ as well. Hence, $q \geq d$. It follows that $|T| \leq\left[\frac{n}{q}\right] \leq\left[\frac{n}{d}\right]$, contradiction. Hence, $q=1$.

Therefore, the minimal possible value of $k$ is $1+\left[\frac{n}{d}\right]$.[^5]

## COMBINATORICS
