Iranian Mathematical Olympiad

Consider numbers of the form $k^m(k^i + j)$ for $i \in \{1, \dots, n-k+1\}$, $j \in \{1, \dots, k-1\}$ and $m \ge 0$.
Note that for such $i$ and $j$ in these intervals, we have $i + j \le n$. Based on $n - (i + j)$ is an odd number or an even number, we have two cases.

* If $n - (i + j)$ is odd, there is some integer $t \ge 0$ such that
$$n - (i + j) = 2t + 1.$$
In this case, the number $k^i + j$ can be represented using $n$ number of $k$'s as
$$k^i + j = \underbrace{(k \times \dots \times k)}_{i+t} \div \underbrace{(k \times \dots \times k)}_{t} + \underbrace{(k + \dots + k)}_{j} \div k.$$

* If $n - (i + j)$ is even, there is some integer $t \ge 0$ such that
$$n - (i + j) = 2t.$$
In this case, the number $k(k^i + j)$ can be shown using $n$ number of $k$'s as
$$k(k^i + j) = k \times \underbrace{((k \times \dots \times k))}_{i+t-1} \div \underbrace{(k \times \dots \times k)}_{t-1} + \underbrace{(k + \dots + k)}_{j} \div k.$$
(In case when $t = 0$, we have $t - 1 = -1$, so in the above equation, instead of multiplying the parentheses to $-1$ $k$'s, we divide it by one $k$.)

So in both cases, there is $m \ge 0$ such that $k^m(k^i + j)$ can be represented using $n$ number of $k$'s. Set $m$ to be the largest number such that $k^m(k^i + j)$ can be represented using only $n$ number of $k$'s (for fixed $i$ and $j$). There are a total of $(n-k+1)(k-1)$ numbers created with given properties. We prove that they are all distinct numbers and also cannot be represented using $n-1$ number of $k$'s.

If some number $u = k^m(k^i + j)$ can be shown using $n-1$ number of $k$'s, then clearly $k \times u = k^{m+1}(k^i + j)$ has a representation, using $n$ number of $k$'s, therefore $m$ cannot be the largest number such that $k^m(k^i + j)$ has a representation using $n$ number of $k$'s, so we conclude that it is impossible to reach these numbers with only $n-1$ number of $k$'s.

Finally, if for two such triples $(i_1, j_1, m_1) \ne (i_2, j_2, m_2)$ with $m_1 \ge m_2$, we have
$$k^{m_1} (k^{i_1} + j_1) = k^{m_2} (k^{i_2} + j_2),$$
then
$$k^{m_1 - m_2} (k^{i_1} + j_1) = k^{i_2} + j_2.$$

But if $m_1 - m_2 > 0$, the above equation implies $k \mid j_2$, which is impossible because $j_2 < k$. Therefore $m_1 = m_2$ and so $k^{i_1} + j_1 = k^{i_2} + j_2$. Without loss of generality, we assume $i_1 \ge i_2$. So
$$k^{i_2} (k^{i_1 - i_2} - 1) = j_2 - j_1.$$
Again, if $i_1 > i_2$, we get $k \mid j_2 - j_1$. Note that $j_1, j_2 \in \{1, \dots, k-1\}$, therefore $-k < |j_1 - j_2| < k$, so we must have $j_1 - j_2 = 0$ and thus $k^{i_1} = k^{i_2}$ which means $i_1 = i_2$, that is impossible in this case because we assumed that $i_1 > i_2$. The only possible case is when $i_1 = i_2$ which leads to $j_1 = j_2$. Therefore $(i_1, j_1, m_1) = (i_2, j_2, m_2)$, contradiction. So indeed, all of the created numbers are distinct and hence the claim of the problem. ■