Problem: For a positive integer $m$,
let $s(m)$ denote the sum of the decimal digits of $m$.
A set $S$ positive integers is \emph{$k$-stable}
if $s(\sum_{x \in X} x) = k$ for any nonempty subset $X \subseteq S$.

For each integer $n \ge 2$ let $f(n)$ be the minimal $k$
for which there exists a $k$-stable set with $n$ integers.
Prove that there are constants $0 < C_1 < C_2$ with
\[ C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n. \]

\end{enumerate}

Solution: \paragraph{Construction showing $f(n) \le 9 \left\lceil \log_{10} \binom{n+1}{2} \right\rceil$.}
Let $n \ge 1$ and $e \ge 1$ be integers satisfying $1 + 2 + \dots + n < 10^e$.
Consider the set
\[ S = \left\{ 10^e-1, \; 2(10^e-1), \; \dots, \; n(10^e-1) \right\}. \]
For example, if $n = 6$ and $e = 3$,
we have $S = \{999, 1998, 2997, 3996, 4995, 5994\}$.

The set $S$ here is easily seen to be $9e$-stable.
Thus $f(n) \le 9 \left\lceil \log_{10} \binom{n+1}{2} \right\rceil$,
proving one direction.

\begin{remark*}
  I think the problem is actually more natural
  with a multiset $S$ rather than a vanilla set,
  in which case $S = \{10^e-1, 10^e-1, \dots, 10^e-1\}$ works fine,
  and is easier to think of.

  In some sense the actual construction is obtained
  by starting with this one,
  and then pushing together the terms together
  in order to get the terms to be distinct,
  hence the $1+2+\dots+n$ appearance.
\end{remark*}

\paragraph{Proof that $f(n) \ge \log_{12} n$.}
We are going to prove the following, which obviously sufficient.
\begin{claim*}
  Let $k$ be a positive integer.
  In any (multi)set $S$ of more than $12^k$ integers,
  there exists a subset whose sum of decimal digits exceeds $k$.
\end{claim*}
\begin{proof}
  Imagine writing entries of $S$ on a blackboard,
  while keeping a running sum $\Sigma$ initially set to zero.
  For $i = 1, 2, \dots$ we will have a process such that
  at the end of the $i$th step all entries on the board
  are divisible by $10^i$.
  It goes as follows:
  \begin{itemize}
    \ii If the $i$th digit from the right of $\Sigma$ is nonzero,
    then arbitrarily partition the numbers on the board
    into groups of $10$, erasing any leftover numbers.
    Within each group of $10$, we can find
    a nonempty subset with sum $0 \bmod{10^i}$;
    we then erase each group and replace it with that sum.

    \ii If the $i$th digit from the right of $\Sigma$ is zero,
    but some entry on the board is not divisible by $10^i$,
    then we erase that entry and add it to $\Sigma$.
    Then we do the grouping as in the previous step.

    \ii If the $i$th digit from the right of $\Sigma$ is zero,
    and all entries on the board are divisible by $10^i$,
    we do nothing and move on to the next step.
  \end{itemize}
  This process ends when no numbers remain on the blackboard.
  The first and second cases occur at least $k+1$ times
  (the number of entries decreases by a factor of at most $12$ each step),
  and each time $\Sigma$ gets some nonzero digit,
  which is never changed at later steps.
  Therefore $\Sigma$ has sum of digits at least $k+1$ as needed.
\end{proof}

\begin{remark*}
  The official solutions contain a slicker proof:
  it turns out that any multiple of $10^e-1$ has
  sum of decimal digits at least $9e$.
  However, if one does not know this lemma it seems
  nontrivial to imagine coming up with it.
\end{remark*}