Mathematical Reflections 2014, Issue 2 - Problem J299

Problem:
Prove that no matter how we choose $n$ numbers from the set $\{1, 2, \ldots, 2n\}$, one of them
will be a square-free integer.



Solution:
Let $A=\{1,2,\ldots,2n\}$. We will prove that there are at most $n-1$ elements in $A$ which are not square-free integers. The number of the elements in $A$ which are divisible by $p^2$, where $p$ is a prime number, are
$$\left\lfloor \dfrac{2n}{p^2} \right\rfloor \leq \dfrac{2n}{p^2}.$$ Therefore, the number of elements in $A$ which are not square-free integers are $$\sum_{p=2 \atop p \textrm{ prime}}^{n} \left\lfloor \dfrac{2n}{p^2} \right\rfloor \leq \sum_{p=2 \atop p \textrm{ prime}}^{n} \dfrac{2n}{p^2} < \sum_{i=2}^{n} \dfrac{2n}{i^2} < \sum_{i=2}^{n} \dfrac{2n}{i(i-1)}=2n\left(\dfrac{1}{2}-\dfrac{1}{n(n-1)}\right)<n,$$ and the conclusion follows.