Problem 1955

First, let us prove the following lemma.

Lemma: For any set of positive integers $m_1, m_2, \dots, m_k$, we have the inequality
$$S\left(\sum_{i=0}^{k} m_i\right) \le \sum_{i=0}^{k} S(m_i).$$
Furthermore, equality holds in the inequality above if the following condition is satisfied:
For any nonnegative integer $j$, the $10^j$-th digit of $m_i = 0$ for all but at most one $i$.

Proof: Whenever there is a carry-over of digits when the addition $\sum_{i=0}^{k} m_i$ is performed, there occurs the reduction by 9 for the value of the sum of digits. Thus, the inequality is satisfied. If the additional condition is satisfied then no carry-over of digits will occur and we get the equality.

For a quintuple $(a_1, \dots, a_5)$ of non-negative integers satisfying the condition $a_1 + \dots + a_5 = 5$ (in the sequel, we simply call such "a quintuple"), denote by $f(a_1, \dots, a_5)$ the coefficient of the term $X_1^{a_1} \cdots X_5^{a_5}$ in the expansion of the multinomial $(X_1 + X_2 + X_3 + X_4 + X_5)^5$. The values of $f(a_1, \dots, a_5)$ are given by $\frac{5!}{a_1! a_2! \cdots a_5!}$ for each quintuple $(a_1, \dots, a_5)$ (we use the convention $0! = 1$).

Now, since $n$ satisfies the condition $S(n) = 5$, we can represent $n$ in the form $n = 10^{k_1} + 10^{k_2} + 10^{k_3} + 10^{k_4} + 10^{k_5}$, using non-negative integers $k_1, k_2, k_3, k_4, k_5$. (Note that the $k_j$'s need not have distinct values.) Then, using the multinomial expansion we can write
$$n^5 = \sum f(a_1, \dots, a_5) 10^{a_1 k_1 + \dots + a_5 k_5},$$
where the sum is taken over all possible quintuples $(a_1, \dots, a_5)$. By using the Lemma, we then get
$$S(n^5) \le \sum S(f(a_1, \dots, a_5) \cdot 10^{a_1 k_1 + \dots + a_5 k_5}) = \sum S(f(a_1, \dots, a_5)) \quad (1)$$
Here again the sums are taken over all possible quintuples $(a_1, \dots, a_5)$.

For a quintuple $(a_1, \dots, a_5)$, let us denote by $(b_1, \dots, b_5)$ a quintuple obtained by rearranging the entries in decreasing order. Then, there are only the following 7 possibilities for $(b_1, \dots, b_5)$:
$$(5, 0, 0, 0, 0),\ (4, 1, 0, 0, 0),\ (3, 2, 0, 0, 0),\ (3, 1, 1, 0, 0),\\ (2, 2, 1, 0, 0),\ (2, 1, 1, 1, 0),\ (1, 1, 1, 1, 1),$$
and each of these $(b_1, \dots, b_5)$ corresponds to 5, 20, 20, 30, 30, 20, 1 different $(a_1, \dots, a_5)$'s, respectively. Furthermore, we have $f(a_1, \dots, a_5) = f(b_1, \dots, b_5)$ if $(b_1, \dots, b_5)$ is the decreasing arrangement of $(a_1, \dots, a_5)$. The value of $f(b_1, \dots, b_5)$ for the 7 different $(b_1, \dots, b_5)$'s are given by 1, 5, 10, 20, 30, 60, 120, respectively. Therefore, we have that the value of $\sum S(f(a_1, \dots, a_5))$ is given by
$$5 \cdot S(1) + 20 \cdot S(5) + 20 \cdot S(10) + 30 \cdot S(20) + 30 \cdot S(30) + 20 \cdot S(60) + 1 \cdot S(120), \\ \text{which equals } 5 \cdot 1 + 20 \cdot 5 + 20 \cdot 1 + 30 \cdot 2 + 30 \cdot 3 + 20 \cdot 6 + 1 \cdot 3 = 398. \text{ Therefore,} \\ \text{we have } S(n^5) \le 398.$$

Finally, let us show that it is possible to construct $n$ for which $S(n^5) = 398$. Choose $k_1, \dots, k_5$ suitably so that for any pair of different quintuples $(a_1, \dots, a_5)$ the corresponding values of $a_1 k_1 + \dots + a_5 k_5$ differ at least by 3 (for instance, let $k_i = 3 \times 6^{i-1}$ for $i = 1, \dots, 5$). Then, since $f(a_1, \dots, a_5) < 10^3$ is satisfied for any quintuple $(a_1, \dots, a_5)$, for any non-negative $j$ the coefficient of $10^j$ term in the sum $\sum f(a_1, \dots, a_5) 10^{a_1 k_1 + \dots + a_5 k_5}$ is 0 except for at most one quintuple $(a_1, \dots, a_5)$.

Therefore, by the Lemma, we have the equality in the inequality (1). This shows that 398 is the desired answer to the problem.