50th Mathematical Olympiad in Ukraine, Fourth Round (March 24, 2010)

From one hand, $k$ cannot be less than $1006$ (otherwise, the product of the $k$ smallest numbers from our set is less than the product of the $2010-k$ numbers which are left). We construct an example for $k=1006$ that will do.

Let $p_1,p_2,\dots ,p_{2010}$ be $2010$ distinct prime numbers and $a_i=p_1{p}_2\dots p_{i-1}{p}_{i+1}\dots p_{2010}=\frac{p_1{p}_2\dots p_{2010}}{p_i}$. Then, the product of $1006$ numbers $a_{n_1},a_{n_2},\dots ,a_{n_{1006}}$ equals $$\frac{(p_1{p}_2\dots p_{2010}{)}^{1006}}{p_{n_1}{p}_{n_2}\dots p_{n_{1006}}}=p_1^{a_1}{p}_2^{a_2}\dots p_{2010}^{a_{2010}},$$ where the degree $a_i$ of each prime number $p_i$, $1\le i\le 2010$, equals $1005$ or $1006$, which is greater than $1005$.

By analogy, the product of the rest $1004$ numbers can be expressed as $p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_{2010}^{{\beta }_{2010}}$, where each degree ${\beta }_i$, $1\le i\le 2010$, equals $1003$ or $1004$, which is less than $1004$.

To finish the proof, note that if $i\ne j$, then $a_i=\frac{p_1{p}_2\dots p_{2010}}{p_j}\ne p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_{2010}^{{\beta }_{2010}}=a_j$, therefore, all $\{a_i\}$ are distinct.