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)}.\] (Error compiling LaTeX. Unknown error_msg)

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.

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

Page

Toolbox

Search

2005 USAMO Problems/Problem 6

Problem

Solution

See Also