Difference between revisions of "2005 USAMO Problems/Problem 6"

(Problem)
(Solution)
Line 4: Line 4:
 
C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n.
 
C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n.
 
</cmath>
 
</cmath>
 
=Solution=
 

Revision as of 15:57, 30 March 2009

Problem

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.\]