Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2005 USAMO Problems/Problem 6

Problem

(Titu Andreescu, Gabriel Dospinescu) For $m$ a positive integer, let $s(m)$ be the sum of the digits of $m$. For $n\ge 2$, let $f(n)$ be the minimal $k$ for which there exists a set $S$ of $n$ positive integers such that $s\left(\sum_{x\in X} x\right) = k$ for any nonempty subset $X\subset S$. 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.\]

Solution

For the upper bound, let $p$ be the smallest integer such that $10^p\geq n(n+1)/2$ and let \[S = \{10^p - 1, 2(10^p - 1), \ldots, n(10^p - 1)\}.\] The sum of any nonempty set of elements of $S$ will have the form $k(10^p - 1)$ for some $1\leq k\leq n(n+1)/2$. Write $k(10^p - 1) = [(k - 1)10^p] + [(10^p - 1) - (k - 1)]$. The second term gives the bottom $p$ digits of the sum and the first term gives at most $p$ top digits. Since the sum of a digit of the second term and the corresponding digit of $k - 1$ is always 9, the sum of the digits will be $9p$. Since $10^{p-1} < n(n+1)/2$, this example shows that \[f(n)\leq 9p\leq 9\log_{10}(5n(n+1)).\] Since $n\geq 2$, $5(n + 1) < n^4$, and hence \[f(n) < 9\log_{10}n^5 = 45\log_{10}n.\] For the lower bound, let $S$ be a set of $n\geq 2$ positive integers such that any nonempty $X\subset S$ has $s\left(\sum_{x\in X} x\right) = f(n)$. Since $s(m)$ is always congruent to $m$ modulo 9, $\sum_{x\in X} x\equiv f(n)\pmod{9}$ for all nonempty $X\subset S$. Hence every element of $S$ must be a multiple of 9 and $f(n)\geq 9$. Let $q$ be the largest positive integer such that $10^q - 1\leq n$. Lemma 1 below shows that there is a nonempty subset $X$ of $S$ with $\sum_{x\in X} x$ a multiple of $10^q - 1$, and hence Lemma 2 shows that $f(n)\geq 9q$.

Lemma 1. Any set of $m$ positive integers contains a nonempty subset whose sum is a multiple of $m$.

Proof. Suppose a set $T$ has no nonempty subset with sum divisible by $m$. Look at the possible sums mod $m$ of nonempty subsets of $T$. Adding a new element $a$ to $T$ will give at least one new sum mod $m$, namely the least multiple of $a$ which does not already occur. Therefore the set $T$ has at least $|T|$ distinct sums mod $m$ of nonempty subsets and $|T| < m$. $\blacksquare$

Lemma 2. Any positive multiple $M$ of $10^q - 1$ has $s(M)\geq 9q$.

Proof. Suppose on the contrary that $M$ is the smallest positive multiple of $10^q - 1$ with $s(M) < 9q$. Then $M\neq 10^q - 1$, hence $M > 10^q$. Suppose the most significant digit of $M$ is the $10^m$ digit, $m\geq q$. Then $N = M - 10^{m-q}(10^q - 1)$ is a smaller positive multiple of $10^q - 1$ and has $s(N)\leq s(M) < 9q$, a contradiction. $\blacksquare$

Finally, since $10^{q+1} > n$, we have $q + 1 > \log_{10} n$. Since $f(n)\geq 9q$ and $f(n)\geq 9$, we have \[f(n)\geq \frac{9q + 9}{2} > \frac{9}{2}\log_{10}n.\] Weaker versions of Lemmas 1 and 2 are still sufficient to prove the desired type of lower bound.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

2005 USAMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last Question
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_USAMO_Problems/Problem_6&oldid=77850"