Problem 1944

Given two positive integers $a, b$ in decimal representation, we say $a$ contains $b$ if $a$ can be obtained from $b$ by adding some digits on the right. We first prove a lemma.

Lemma Let $n_1, n_2, ..., n_r$ be pairwise distinct positive integers with digit 1 or 2. If none contains another, then the number of $n_i$'s with $S(n_i) \le t$ is at most $F_t$, where $t$ is an arbitrary positive integer and $F_t$ is a Fibonacci number satisfying $F_1 = 1, F_2 = 2, F_{n+2} = F_{n+1} + F_n$ ($n \ge 1$).

*Proof of lemma.* We induct on $t$. It is clear for $t = 1, 2$ (when $t = 2$, $1$ and $11$ cannot both appear). Suppose that the lemma is true for all positive integers less than $t$ ($t \ge 3$); we shall prove that it is also true for $t$. Suppose that without loss of generality $S(n_1), S(n_2), ..., S(n_l)$ are all the numbers with the sum of digits $\le t$, where $n_1, n_2, ..., n_j$ start with 1 and $n_{j+1}, n_{j+2}, ..., n_l$ start with 2. If one of $n_1, n_2, ..., n_j$ is 1, then $j = 1 \le F_{t-1}$, otherwise by deleting the first digit of $n_1, n_2, ..., n_j$ we obtain $j$ positive integers with none containing another and the sum of digits $\le t-1$, and thus we again have $j \le F_{t-1}$ by the inductive hypothesis. Analogously, we have $l-j \le F_{t-2}$. And therefore $l \le F_{t-1} + F_{t-2} = F_t$, i.e. the lemma is also true for $t$. The proof of the lemma is completed.

Going back to the original problem, we consider a more general question. Replacing 26 by $m$, denote the least possible value of $\sum_{i=1}^{m} S(n_i)$ by $f(m)$. Fix $m \ge 3$, and let $n_1, n_2, \dots, n_m$ be a set of numbers satisfying the conditions in the problem which attains the minimum $f(m)$. Without loss of generality, assume that $\max_{1 \le i \le m} S(n_i) = S(n_1)$ and $n_1$ is maximum among all these numbers attaining the maximum digital sum. Since $m \ge 3$, $n_1$ contains at least two digits.

If the last digit of $n_1$ is 1, replace $n_1$ by $\frac{n_1-1}{10}$, which is not one of $n_2, n_3, \dots, n_m$, otherwise $n_1$ would contain some $n_i$. Notice that $\frac{n_1-1}{10}, n_2, \dots, n_m$ again satisfy the conditions in the problem, for if $n_i$ contains $\frac{n_i-1}{10}$ for some $i \ge 2$, then $S(n_i) > S(n_1)$ and $n_i > n_1$, a contradiction. Now
$$S\left(\frac{n_1-1}{10}\right) + S(n_2) + \dots + S(n_m) = f(m) - 1,$$
a contradiction to the definition of $f(m)$. Thus, the last digit of $n_1$ is 2.

If $n_1-1$ is not one of $n_2, n_3, \dots, n_m$, replace $n_1$ by $n_1-1$, and these $m$ numbers again satisfy the conditions in the problem, for if $n_i$ contains $n_i-1$ for some $i \ge 2$, then $n_i$ must be $10(n_i-1)+1$, $S(n_i) = S(n_1)$; however, $n_i > n_1$ is a contradiction to the choice of $n_1$. Now
$$S\left(\frac{n_1-1}{10}\right) + S(n_2) + \dots + S(n_m) = f(m) - 1,$$
a contradiction to the definition of $f(m)$. Thus, $n_1-1$ appears in $n_2, n_3, \dots, n_m$.

Without loss of generality, assume that $n_2 = n_1 - 1$. Consider $\frac{n_1-2}{10}, n_3, \dots, n_m$; since $\frac{n_1-2}{10} \ne n_i$ for $i \ge 3$, these are $m-1$ pairwise distinct numbers. There is no containment among $n_2, \dots, n_m$, and $\frac{n_1-2}{10}$ does not contain any of $n_3, \dots, n_m$, otherwise $n_1$ would contain that number. If one of $n_3, \dots, n_m$ contains $\frac{n_1-2}{10}$, say $n_3$, since $S\left(\frac{n_1-2}{10}\right) = S(n_1)-2$, $n_3$ is obtained by adding 1, 2 or 11 after $\frac{n_1-2}{10}$. Adding 1 or 2 yields $n_2, n_1$, and we must have $n_3 = 100 \cdot \frac{n_1-2}{10} + 11 = 10n_1 - 9$. Now $S(n_3) = S(n_1)$ and $n_3 > n_1$, a contradiction to the choice of $n_1$. So $\frac{n_1-2}{10}$, $n_3, \dots, n_m$ satisfy the conditions in the problem, and therefore the sum of their digits is at least $f(m-1)$. Thus,
$$f(m) - S(n_1) - (S(n_1) - 1) + (S(n_1) - 2) \ge f(m-1),$$
i.e.
$$f(m) \ge f(m-1) + S(n_1) + 1.$$
Let $u$ be such that $F_{u-1} < m \le F_u$. By the lemma, there are at most $F_{u-1}$ of $S(n_1), S(n_2), \dots, S(n_m)$ less than or equal to $u-1$, so $S(n_1) \ge u$, and
$$f(m) \ge f(m-1) + u + 1. \qquad \textcircled{1}$$
It is easy to see that $f(1) = 1$, $f(2) = 3$, and hence
$$\begin{aligned} f(26) &= f(2) + \sum_{i=3}^{26} (f(i) - f(i-1)) \\ &= f(2) + (f(3) - f(2)) + (f(5) - f(3)) + (f(8) - f(5)) \\ &\quad + (f(13) - f(8)) + (f(21) - f(13)) + (f(26) - f(21)) \\ &\ge 3 + 4 \times 1 + 5 \times 2 + 6 \times 3 + 7 \times 5 + 8 \times 8 + 9 \\ &\quad \times 5 \text{ (by equation \textcircled{1})} \\ &= 179, \end{aligned}$$
i.e. $\sum_{i=1}^{26} S(n_i) \ge 179$.

On the other hand, by the property of Fibonacci numbers, there are exactly 8 numbers consisting of digits 1 and 2, with digital sum 5, denoted by $a_1, a_2, ..., a_8$, and there are exactly 13 such numbers with digital sum 6, denoted by $b_1, b_2, ..., b_{13}$. Add a digit 2 after each of $a_1, a_2, ..., a_8$, denoting these new numbers by $c_1, c_2, ..., c_8$. Add a digit 1 (resp. digit 2) to each of $b_1, b_2, b_3, b_4, b_5$, denoting these new numbers by $d_1, d_2, d_3, d_4, d_5$ (resp. $e_1, e_2, e_3, e_4, e_5$). Now consider
$c_1, c_2, ..., c_8, d_1, d_2, ..., d_5, e_1, e_2, ..., e_5, b_6, b_7, ..., b_{13}$.
These are pairwise distinct numbers consisting of digits 1 and 2, with total digital sum $7 \times 8 + 7 \times 5 + 8 \times 5 + 6 \times 8 = 179$. And there is none containing another. In fact, if $x$ contains $y$, since their digital sum is either 6, 7 or 8, and a number with digital sum 8 ends up with 2, it follows that $x$ has exactly one more digit than $y$. However, deleting the last digit of $d_1, d_2, ..., d_5$ and $e_1, e_2, ..., e_5$ yields $b_1, b_2, ..., b_5$, and deleting the last digit of $c_1, c_2, ..., c_8$ yields $a_1, a_2, ..., a_8$, none of which is in this set of 26 numbers.

We conclude that the least possible value of $\sum_{i=1}^{26} S(n_i)$ is 179.