Let $n_1,n_2, \cdots, n_{26}$ be pairwise distinct positive integers satisfying (1) for each $n_i$, its digits belong to the set $\{1,2\}$; (2) for each $i,j$, $n_i$ can't be obtained from $n_j$ by adding some digits on the right. Find the smallest possible value of $\sum_{i=1}^{26} S(n_i)$, where $S(m)$ denotes the sum of all digits of a positive integer $m$.
Problem
Source:
Tags: floor function, inequalities, algorithm, combinatorics unsolved, combinatorics
08.09.2010 15:18
The answer is $179$; equality occurs when $s(n_i)=6$ for 8 numbers, $s(n_i)=7$ for 13 numbers,$s(n_i)=8$ for 5 numbers, which can happen in several ways Proof Suppose we have a set of 26 numbers that meet the condition. If there existed i,j such that $s(n_i)+3 < s(n_j)$, then replace $(n_i,n_j) \to (10n_i +1, 10n_i + 2)$ which decreases the sum, so we can assume $|s(n_i)-s(n_j)|\le 3$ for all $i,j \qquad (*)$ Let $A_k = \{n_i | s(n_i)=k\}$, so we need to minimise $A_{sum} = \sum_k k \cdot |A_k|$. Also let $S_k$ be the set of all numbers with digital sum $k$. By counting numbers numbers with $n$ digits of which $j$ of them are $2$ we have \[S_{n} = \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-j}{j}=F_{n-1}\] Then for each $n_i \in A_k$ we can append digits, with sum $\ell$, to $n_i$ in $S_{\ell}$ ways, which means there are $S_{\ell}\cdot |A_k|$ forbidden numbers with sum $k+\ell$ for all $\ell, k \qquad(**)$ So if $m = \max \{ s(n_i)\}$ then from (*) and (**) we have the following inequalities $|A_{m-3}|+|A_{m-2}|+|A_{m-1}|+|A_{m}| = 26 \qquad(1)$ $|A_{m-3}| + |A_{m-2}| \le S_{m-2} \qquad(2)$ $2|A_{m-3}| + |A_{m-2}| + |A_{m-1}| \le S_{m-1} \qquad(3)$ $3|A_{m-3}| + 2|A_{m-2}| + |A_{m-1}|+ |A_{m}| \le S_{m}\qquad(4) $ Combining the above we require $S_m \ge 26 \Rightarrow m \ge 8$. Now check 3 cases: If $m=8$ then (4)-(1) --> $2|A_5| + |A_6| \le 8$. So we use the greedy algorithm to find the minimum. $2|A_5|+|A_6|=8 \Leftrightarrow |A_6|=8-2|A_5|$. Then (3) --> $|A_7| = 13$ and (1)--> $|A_8|=5+|A_5|$. Finally checking we need to minimise $A_{sum} \ge 5|A_5| + 6( 8-2|A_5|) + 7\cdot 13 + 8(5+|A_5|) =179 - |A_5| \ge \boxed{179}$ If $m=9$ then by the same token $2|A_6|+|A_7| = 29 \rightarrow |A_8|=5, |A_9|=|A_6|-8$ and $A_{sum} \ge 6|A_6| + 7(29-2|A_6|) + 8\cdot 5 + 9(|A_6|-8) = 171 +|A_6| \ge \boxed{179}$ If $m>9$ then all digital sums are at least $7$ so trivially $A_{sum} \ge 7\cdot 26 = 182 > 179$. We conclude that the minimum is 179.