BMO 2019 Shortlist

Let $t$ be the greatest common divisor of the elements in $T$. Due to the fact that $S\subset T$, we immediately get that $t/s$. Let us assume for the sake of contradiction that $t\ne 1$. From the previous observation we get that $t\ge d$. By taking into account that $|T|\ge 1+\lfloor \frac{n}{d}\rfloor$, we infer that we can find at least $1+\lfloor \frac{n}{d}\rfloor$ elements in $T$. All of them will be divisible by $t$, and the largest of them, which we shall denote by $M$, will be at least $t\cdot (1+\lfloor \frac{n}{d}\rfloor )$. On the other hand, $t\ge d$, hence $$M\ge t\cdot (1+\lfloor \frac{n}{d}\rfloor )\ge d\cdot (1+\lfloor \frac{n}{d}\rfloor )>d\cdot \frac{n}{d}=n.$$ Therefore, $M>n$, which contradicts the fact that $M\in \{1,\dots ,n\}$. In conclusion, $t=1$, as desired. $\square$

Solution: We will show that $k_{\min }=1+\lfloor \frac{n}{d}\rfloor$ (here $\lfloor \cdot \rfloor$ denotes the integer part). Obviously, the number of elements of $S$ is not greater than $\lfloor \frac{n}{d}\rfloor$, i.e. $|S|\le \lfloor \frac{n}{d}\rfloor$, and $S\ne U$. If $S\subset T$ and the greatest common divisor of elements of $T$ is equal to $1$, then $|T|\ge |S|+1$. 1) Assume that $|S|<\lfloor \frac{n}{d}\rfloor$. Let $T$ be the subset of $U$, consisting of all multiples of $d$ in $U$. Thus, $|T|=\lfloor \frac{n}{d}\rfloor$ and $S\subset T$. Therefore, the greatest common divisor of all elements of $T$ is $d>1$. Thus, $k\ge 1+\lfloor \frac{n}{d}\rfloor$. 2) Assume $|S|=\lfloor \frac{n}{d}\rfloor$. Let $T$ be any subset of $U$ with $S\subset T,S\ne T$. Therefore, $|T|\ge 1+\lfloor \frac{n}{d}\rfloor$. 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\ge d$. It follows that $|T|\le \lfloor \frac{n}{q}\rfloor \le \lfloor \frac{n}{d}\rfloor$, contradiction. Hence, $q=1$. Therefore, the minimal possible value of $k$ is $1+\lfloor \frac{n}{d}\rfloor$. $\square$