Japan Junior Mathematical Olympiad First Round

By symmetry, it is sufficient to determine the number of those positive integers having digits less than or equal to $2009$ that can be represented in the form $a^{2009} + b^{2009}$ by using a pair of integers $a$ and $b$ with the additional hypothesis $a \ge b$.

Note also that the requirement that $a^{2009} + b^{2009}$ is positive and has digits less than or equal to $2009$ is equivalent to the condition $10^{2009} > a^{2009} + b^{2009} > 0$.

Let us first show the following:
If a pair of integers $(a, b)$ satisfies either one of the following conditions, then $a^{2009} + b^{2009}$ is positive and has digits less than or equal to $2009$.
$$(A) : 1 \le a \le 9 \quad \text{and} \quad -a < b \le a.$$
$$(B) : a = 10 \quad \text{and} \quad -10 < b < 0.$$
We first prove the following simple lemma.

Lemma: $(9/10)^{2009} < 1/3$.

Proof: In fact, you can check that $(9/10)^n < 1/3$ if $n \ge 11$, but we can give a simpler proof for $n \ge 15$. Note that $9^5 = 59049$ so that $(9/10)^5 < 3/5 < 2/3$ and $(2/3)^3 < 1/3$. Therefore, $(9/10)^{15} = \{(9/10)^5\}^3 < (2/3)^3 < 1/3$.

If the condition (A) is satisfied, then it is clear that $a^{2009} + b^{2009}$ is positive, and since its maximum value is attained when $a = b = 9$, $a^{2009} + b^{2009} \le 2 \times 9^{2009} < 10^{2009}$ by the lemma. When the condition (B) is satisfied, we have $10^{2009} = 10^{2009} - 0^{2009} > a^{2009} + b^{2009} > 10^{2009} + (-1)^{2009} = 0$, therefore, we conclude that under either of the conditions (A) or (B), $10^{2009} > a^{2009} + b^{2009} > 0$.

We next show that there are no other pairs $(a, b)$, which satisfy the requirement. So, suppose that $10^{2009} > a^{2009} + b^{2009} > 0$ and $a \ge b$. Then, we must have $a \ge 1$ and $b > -a$. Therefore, if $9 \ge a \ge 1$, there are no solutions unless $a \ge b > -a$. If $a = 10$, then if $b \ge 0$ we get $a^{2009} + b^{2009} \ge 10^{2009}$, which contradicts the assumption, hence $0 > b > -a = -10$ must be satisfied. Finally, if $a \ge 11$, then it is clear that we need $0 > b > -a$. But then, $a^{2009} + b^{2009} = a^{2009} - (-b)^{2009} \ge a^{2009} - (a-1)^{2009}$ since $0 < -b \le a - 1$. Since
$$\begin{aligned} & a^{2009} - (a-1)^{2009} \\ &= \{a - (a-1)\}\{a^{2008} + a^{2007}(a-1) + \dots + a(a-1)^{2007} + (a-1)^{2008}\} \\ &> 2009(a-1)^{2008} \ge 2009 \cdot 10^{2008} > 10^{2009}, \end{aligned}$$
we see that $a \ge 11$ cannot occur. Thus, we conclude that either (A) or (B) must be satisfied.

The number of pairs $(a, b)$ which satisfies the condition (A) is $\sum_{a=1}^{9} 2a = (9+1) \cdot 9 = 90$, and the number of pairs $(a, b)$ satisfying the condition (B) is $9$, so if we can show that no $2$ pairs satisfying either condition (A) or (B) give the same number $a^{2009} + b^{2009}$, then we can conclude that $90+9=99$ is the desired answer to the problem.

So, suppose $a^{2009} + b^{2009} = c^{2009} + d^{2009}$, with $a \ge b$ and $c \ge d$. We may suppose $a \ge c$. If $a=c$, then $b=d$. So, let us suppose $1 \le c \le a-1 \le 8$. Then, since $1-a \le b \le a$ and $2-a \le 1-c \le d \le c \le a-1$, we have $a^{2009} = c^{2009} + d^{2009} - b^{2009} \le 3 \cdot (a-1)^{2009}$. Since $2 \le a \le 9$, we have $\frac{a-1}{a} \le \frac{8}{9} < \frac{9}{10}$, and by the lemma $(\frac{a-1}{a})^{2009} < (\frac{9}{10})^{2009} < \frac{1}{3}$, from which it follows that $a^{2009} \le 3 \cdot (a-1)^{2009} < a^{2009}$, a contradiction. Thus, the numbers $a^{2009} + b^{2009}$ for pairs $(a, b)$ satisfying the condition (A) are distinct.

Finally, if $10^{2009} + b^{2009} = c^{2009} + d^{2009}$ with $0 > b > -10$, $10 \ge c \ge 1$ and $c \ge d > -c$, the condition $c=10$ forces $d$ to be equal to $b$, while if $9 \ge c$, we get $10^{2009} = c^{2009} - b^{2009} + d^{2009} < 3 \cdot 9^{2009}$, and we obtain a contradiction since $3 \cdot 9^{2009} < 10^{2009}$ again by the lemma. Thus the numbers $a^{2009} + b^{2009}$ corresponding to the pairs satisfying the condition (B) are all distinct and different from any of those corresponding to pairs satisfying the condition (A).

Therefore, the answer is $99$.