China National Team Selection Test

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)+\cdots +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)+\cdots +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.\stackrel{◯}{1}$$ It is easy to see that $f(1)=1$, $f(2)=3$, and hence $$\begin{array}{rl}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))\\ & +(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\\ & \times 5\text{ (by equation 1◯)}\\ & =179,\end{array}$$ 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.