Who is the author of this problem? I have one very strong supposition...

I am not sure what the AMC shortcuts as "AND" but it might be Titu Andreescu ...

I have another opinion. But I don't want to reveal it till the author will confirm I am right.

You are right.

Pierre.

harazi wrote: You are right. You??

No, Titu Andreescu and me.

harazi wrote: No, Titu Andreescu and me. You assured yourself of some cursing

harazi wrote: You are right. Wow, you and Titu proposed this problem? From the people I talked to, many people thought it was a hard, but good problem

I am glad to hear that, but I would prefer to see a nice solution to this problem.

Is there something unsatisfactory to the solution on the UNL website? I think a lot of people got the RHS looking at sets consisting of all the same integer = 10^k - 1 for whatever k.

Did I say there is something unsatisfactory about the solution presented there? I just wanted to see many solutions. . Indeed, the part with the construction was not difficult, the trick with $10^k-1$ being quite standard. But the other part was not easy (I think), even if it also used only standard arguments and lemmas. The main difficulty is to put everything together, I thinK.

darktreb wrote: Is there something unsatisfactory to the solution on the UNL website? I belive it is the author's (ie Harazi's) solution

No, Titu has found this final version of the solution, a little bit easier than my initial solution, but on the same way. I think that when we created the problem, we found nice bounds: the smallest constant can be taken 8 and the largest one 19 or something like this.

Quote: But the other part was not easy (I think), even if it also used only standard arguments and lemmas. The main difficulty is to put everything together, I thinK. I agree completely. It was a beautiful problem in that way. I had Lemma 1 of the "standard solution" (the one posted on the website) with at least 2 1/2 hours to go. Putting everything together really didn't work out for me at all. It was a great problem, and definitely very difficult.

So...any solutions that woul denlighten me ? Masoud Zargar

Solution by math154, dysfunctionalequations, and myself. Lemma 1: Let $n$ be any positive integer, and let $k$ be any integer less than $10^n$. Then $s((10^n - 1)k) = 9n$. Proof: Let $k = \sum_{i=0}^{n-1} c_i 10^i$, where $0 \leq c_i < 10$. We may suppose without loss of generality that $10 \not | k$, since otherwise $s((10^n - 1)k) = s((10^n - 1) \frac{k}{10})$, so $c_0 \geq 1$. Then \begin{align*} s((10^n - 1)k) &= s(10^n k - k) \\ &= s(\sum_{i=0}^{n-1} c_i 10^{n+i} - \sum_{i=0}^{n-1} c_i 10^i) \\ &= s(1 + \sum_{i=0}^{n-1} 9 \cdot 10^i + (c_0 - 1) 10^n + \sum_{i=n+1}^{2n-1} c_{i-n} 10^i - \sum_{i=0}^{n-1} c_i 10^i) \\ &= s((10 - c_0) + \sum_{i=1}^{n-1} (9 - c_i) 10^i + (c_0 - 1) 10^n + \sum_{i=n+1}^{2n-1} c_{i-n} 10^i) \\ &= (10 - c_0) + \sum_{i=1}^{n-1} (9 - c_i) + (c_0 - 1) + \sum_{i=1}^{n-1} c_i \\ &= 9n. \end{align*} Lemma 2: Let $n$ and $k$ be any positive integers. Then $s((10^n - 1)k) \geq 9n$. Proof: We will prove this by induction on $k$. For the base case $k = 1$, $s(10^n - 1) = 9n$. We now wish to show that for any $k > 1$, if our claim is true for all $j < k$, then $s((10^n - 1)k) \geq 9n$. If the base $10^n$ representation of $(10^n - 1)k$ is $a_0 10^0 + a_1 10^n + \cdots + a_p 10^{np}$, then $0 \equiv (10^n - 1)k = a_0 10^0 + a_1 10^n + \cdots + a_p 10^{np} \equiv a_0 + a_1 + \cdots + a_p \pmod{10^n - 1}$. Since $k > 1$, $p > 0$, so $a_0 + a_1 + \cdots + a_p < a_0 10^0 + a_1 10^n+ \cdots + a_p 10^{np}$, so we can find some $j < k$ such that $(10^n - 1)j = a_0 + a_1 + \cdots + a_p$. But \begin{align*} s((10^n - 1)k) &= s(a_0 10^1 + a_1 10^n + \cdots + a_p 10^{np}) \\ &= s(a_0) + s(a_1) + \cdots + s(a_p) \\ &\geq s(a_0 + a_1 + \cdots + a_p) \\ &= s((10^n- 1)j) \\ &\geq 9n, \end{align*} which completes our proof. Let $m$ be any positive integer. For the upper bound, we consider the set $S = \{(10^m - 1), 2(10^m - 1), \ldots, 3^m (10^m - 1)\}$. For any non-empty subset $X$ of $S$, the sum of the elements of $X$ must be divisible by $10^m - 1$ and less than or equal to $(10^m - 1)(1 + 2 + \cdots + 3^m) = (10^m - 1)\frac{3^m (3^m + 1)}{2} < (10^m - 1)^2$, so by lemma 1 the sum of the digits of the sum of the elements of $X$ must equal $9m$. Hence, $f(3^m) \leq 9m$ for any positive integer $m$. Let $n$ be any positive integer larger than 1. Because $f$ is clearly increasing, we have \begin{align*} f(n) &\leq f(3^{\lceil \log_3 n \rceil}) \\ &\leq 9(\lceil \log_3 n \rceil) \\ &\leq 9(\log_3 n + 1) \\ &= \frac{9}{\log_{10} 3} \log_{10} n + 9. \end{align*} Letting $C_2 = \frac{9}{\log_{10} 3} + \frac{9}{\log_{10} 2}$, we have $\frac{9}{\log_{10} 3} \log_{10} n + 9 \leq \frac{9}{\log_{10} 3} \log_{10} n + \frac{9}{\log_{10} 2} \log_{10} n = C_2 \log_{10} n$, so $f(n) \leq C_2 \log_{10} n$. For the lower bound, let $s_1, s_2, \ldots, s_n$ be the elements of $S$, let $y_i = s_1 + s_2 + \ldots + s_i$ for $1 \leq i \leq n$, and let $j = \lfloor \log_{10} n \rfloor - 1$. $n > 10^j - 1$, so by the pigeonhole principle we can find some $k$ and $l$ with $k>l$ for which $10^j - 1 | y_k- y_l$. Hence, by lemma 2, $s(y_k - y_l) \geq 9j$. But since $y_k - y_l = x_{l+1} + x_{l+2} + \ldots + x_k$ is the sum of the elements of some subset of $S$, we have $f(n) \geq 9j \geq 9 \log_{10} n - 18$. Letting $C_1 = 9 - \frac{18}{\log_{10} 2} > 0$ gives $(9-C_1) \log_{10} n \geq \frac{18}{\log_{10} 2} \log_{10} 2 \geq 18$, so $f(n) \geq 9 \log_{10} n - 18 \geq C_1 \log_{10} n$, which completes our proof.

Zhero wrote: ... Letting $C_1 = 9 - \frac{18}{\log_{10} 2} > 0$ gives $(9-C_1) \log_{10} n \geq \frac{18}{\log_{10} 2} \log_{10} 2 \geq 18$, so $f(n) \geq 9 \log_{10} n - 18 \geq C_1 \log_{10} n$, which completes our proof.

By the way, very cool solution. I got the first lemma part but couldn't think to use an inequality variant of it for the second part.

Let $\Sigma(X)$ denote the sum of the elements in a set $X$. Obviously $f$ is nondecreasing. Therefore, to prove the upper bound it suffices to show that $f(10^k) \leq 2k$ for all $k$. We first have the following lemma. Lemma: Let $e$ be a positive integer. Then for any $1 \leq n<10^e$, $s(n(10^e-1))=9e$. Proof: Motivated by how "subtraction by hand" is done, rewrite the number as $(n-1)10^e+(10^e-n)$ and note that $$s(n(10^e-1))=s(n-1)+s(10^e-n)=s(n-1)+s((10^e-1)-(n-1)).$$Since $n-1$ and $(10^e-1)-(n-1)$ sum to $10^e-1$ without any carries, the conclusion is clear. $\blacksquare$ I claim that the set $S=\{1(10^{2k}-1),\ldots,(10^k)(10^{2k}-1)\}$ works. Indeed, the sum of any of its nonempty subsets is of the form $n(10^{2k}-1)$ where $n \leq \frac{10^k(10^k+1)}{2}<10^{2k}$, hence we are done by the above lemma. To prove the lower bound, I will prove the more general claim that for any nonnegative integer $N$ and any multiset $T$ containing at least $1000^k$ positive integers, there exists some $B \subseteq T$ such that $N+\Sigma(B)$ contains at least $k$ nonzero digits. This is by induction on $k$, with the base case of $k=1$ being obvious. For the inductive step, we may WLOG assume that either $N$ or at least one of the elements of $T$ is not divisible by $10$. If $10 \mid N$, then remove some element $e \in T$ with $10 \nmid e$, and add it to $N$; this only makes our task harder. Therefore assume that $10 \nmid N$ and $|T| \geq 1000^k-1$. Then split the elements of $T$ into as many "blocks" of size $10$ as possible, where elements within each block are congruent modulo $10$. At most $90$ elements are not part of a block, so we have at least $\frac{1000^k-91}{10}$ such blocks. Then let $T'$ be the multiset of size at least $\frac{1000^k-91}{10}$ formed by taking the sum of each of the blocks, so every element in $T'$ is divisible by $10$, and let $N'$ be the result of replacing the units digit of $N$ with a zero. Since $\frac{1000^k-91}{10} \geq 1000^{k-1}$, it follows by inductive hypothesis that there exists some $B' \subseteq T$ such that $N'+\Sigma(B')$ has at least $k-1$ nonzero digits. Since this number is always divisible by $10$, it follows that $N+\Sigma(B')$ has at least $k$ nonzero digits, so by letting $B$ be the multiset of elements in the blocks chosen to form $B'$ we are done. This proves the lower bound due to the non-decreasingness of $f$, since by taking $N=0$ we have $f(1000^k) \geq k$. $\blacksquare$ Remark: first post in this thread since 11 years lmao. not as slick of a proof of the lower bound as the above but I think this works too. there are a lot of ideas for the lower bound that don't work but I think the ideas vaguely got refined into what I have here. in particular it would be nice to induct down somehow (and there are lots of possible setups but I think most straightforward approaches don't work), and one possible way to do this would be to find some number not divisible by $10$ and then force yourself to include it, and then try not to disturb the units digit as you choose the rest of the subsets, but it took me a while to realize that this generalization was possible since there are so many other possibilities. also doing math at midnight is not efficient

First, notice that $s(n) \equiv n \pmod{9}$, so all elements of $X$ are congruent to $k$ modulo $9$. Since the sum of any two elements of $X$ is also congruent to $k$ modulo $9$, we must have $9 \mid k$. Let a set be $c$-regular if it satisfies the problem conditions for $k=9c$. It suffices to prove that there exists a $c$-regular set of size at least an exponential function of $c$ all $c$-regular sets have size at most an exponential function of $c$. For the construction, consider $X=\{10^c-1,2(10^c-1),\ldots,a(10^c-1)\}$ for $a$ with $\tfrac{a(a+1)}{2} \le 10^c$. All subsets of $X$ have elements that sum to a multiple of $10^c-1$ no greater than $10^c(10^c-1)$. For a positive integer $b \le 10^c$, the digits of $b(10^c-1)$ consist of the concatenation of the digits of $b-1$ and the digits of $10^c-b$, possibly with leading zeros to make a $c$-digit integer. Since $(b-1)+(10^c-b)=10^c-1$ and both $b-1$ and $10^c-b$ are nonnegative, the corresponding digits of $b-1$ and $10^c-b$ sum to $9$, so the digit sums of $b-1$ and $10^c-b$ add up to $9c$. Thus, $X$ is $c$-regular. We can set $a=2^c$ to give a $c$-regular set with exponential size, as desired. For the upper bound, we claim that any set $X$ whose subsets of size $1$, $|X|-1$, and $|X|$ contain elements summing to numbers with a digit sum $9c$ has at most exponential size. Let $X=\{a_1,\ldots,a_n\}$, and let $s=a_1+\cdots+a_n$. The idea is to limit the number of digit places that can hold nonzero digits. Suppose that $s$ has nonzero digits on the $10^{b_1},10^{b_2},\ldots,10^{b_m}$ digit places, where $b_1<\cdots<b_m$. Notice that $m \le 9c$. We can check that $s(a-b)=s(a)-s(b)+9d$, where $d$ is the number of carries when doing standard decimal subtraction. Thus, the number of carries when subtracting $s-a_i$ is $c$ for $i=1,\ldots,n$. Fix $i$, and let $c_j$ be the largest nonnegative integer less than $b_j-b_{j-1}$ (where $b_0=-1$) such that the $10^{b_j-c_j}$ digit place of $a_i$ is nonzero, if there exists one $0$ otherwise for $j=1,\ldots,m$. The crux of the problem is the following. Claim: $c_1+\cdots+c_m \le c$. Proof: There will be carries on the \[10^{b_1-c_1},10^{b_1-c_1+1},\ldots,10^{b_1-1},10^{b_2-c_2},10^{b_2-c_2+1},\ldots,10^{b_2-1},\ldots,10^{b_m-c_m},10^{b_m-c_m+1},\ldots,10^{b_m-1}\]digit places when subtracting $s-b_j$. This gives $c_1+\cdots+c_m$ carries, so $c_1+\cdots+c_m \le c$. $\square$ By stars and bars, there are at most $\tbinom{c+m}{c} \le \tbinom{10c}{c}$ ways to choose $c_1,\ldots,c_m$. After choosing $c_1,\ldots,c_m$, we have fixed $m+c_1+\cdots+c_m \le 10c$ digit places as the only possible nonzero digit places of $a_i$ with nonzero digits. Thus, there are at most $10^{10c}$ choices of $a_i$ given $c_1,\ldots,c_m$. We conclude that there are at most \[\tbinom{10c}{c}10^{10c} \le \frac{(10c)^c}{c!}10^{10c} \sim \frac{10^cc^c}{\frac{c^c}{e^c}\sqrt{2\pi c}}10^{10c} \le (10^{11}e)^c\]possible values of $a_i$, where the second last equivalence is by Stirling. Thus, $n$ is bounded above by an exponential function of $c$, as desired. $\square$