Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

(a) Suppose that two such integers, $a < b$, exist. Let $m$ be the squarefree part of $a$; $a = ms^2$, $s \in \mathbb{Z}$. Then $mb$ is a square, so since $m$ is squarefree, $b = mt^2$ for some integer $t \ge s + 1$. Hence
$$\left(1 + \frac{1}{s}\right)^2 \le \frac{t^2}{s^2} = \frac{b}{a} < \frac{(k+1)^2}{k^2} = \left(1 + \frac{1}{k}\right)^2,$$
so $s > k$. Consequently, $b = mt^2 \ge m(s+1)^2 > (k+1)^2$ – a contradiction.

(b) We show that the statement holds whenever $k \ge 3^{n-1}$; if $n$ is odd, the weaker condition $k \ge 2^{n-1}$ suffices. We require a LEMMA whose proof offers no difficulty.
LEMMA. If $C > 0$ and $n \ge 2$, then $(k+1)^n > (k^{n/(n-1)} + C)^{n-1}$ for all $k \ge C^{n-1}$.
Now let $n$ be odd, let $a$ be the smallest integer greater than $k^{n/(n-1)}$, and let $b = a+1$. The $n$ integers $a^{n-i-1}b^i$, $i = 0, 1, 2, \dots, n-1$, are distinct, and their product is the $n$-th power of $(ab)^{(n-1)/2}$. The smallest of them, $a^{n-1}$, exceeds $k^n$, and the largest, $b^{n-1}$, is at most $(k^{n/(n-1)} + 2)^{n-1}$. By the LEMMA, this is at most $(k+1)^n$ when $k \ge 2^{n-1}$.
Next, we turn to the case of even $n$. Let again $a$ be the smallest integer greater than $k^{n/(n-1)}$, and let $b = a+1$ and $c = a+2$. Let further $x_i = a^{n-i}b^i$ and $y_i = b^{i-1}c^{n-i}$, $i = 1, 2, \dots, n-1$. Note that
$$k^n < x_1 < x_2 < x_3 < \dots < x_{n-1} < y_{n-1} < y_{n-2} < \dots < y_2 < y_1 \le (k^{n/(n-1)} + 3)^{n-1},$$
so these $2n-2$ integers are distinct, and by the LEMMA they are in the proper range when $k \ge 3^{n-1}$. We end the proof by showing that we can choose $n$ of these integers so that the product is a perfect $n$-th power.
If $n$ is divisible by 4, say $n = 4m$, choose
$x_1, x_3, x_5, \dots, x_{4m-1}, y_1, y_3, y_5, \dots, y_{4m-1}$;
their product is the $n$-th power of $a^m b^{2m-1} c^m$.
If $n = 8m + 2$, $m > 0$, take
$x_2, x_3, x_4, \dots, x_{4m+2}, y_2, y_3, y_4, \dots, y_{4m+2}$;
the product of these is the $n$-th power of $a^{3m}b^{2m+1}c^{3m}$.
Finally, if $n = 8m + 6$, select
$$x_1, x_2, x_3, \dots, x_{4m+3}, y_1, y_2, y_3, \dots, y_{4m+3},$$
in which case the product is the $n$-th power of $a^{3m+2}b^{2m+1}c^{3m+2}$.