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.