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

Latest revision as of 22:59, 29 March 2016

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.

@@ Line 1: / Line 1: @@
-==Problem==
+== Problem ==
-For <math>m</math> a positive integer, let <math>s(m)</math> be the sum of the digits of <math>m</math>. For <math>n\ge 2</math>, let <math>f(n)</math> be the minimal <math>k</math> for which there  exists a set <math>S</math> of <math>n</math> positive integers such that  <math>s\left(\sum_{x\in X} x\right) = k</math> for any nonempty subset <math>X\subset S</math>.  Prove that there are constants <math>0 < C_1 < C_2</math> with
+(''Titu Andreescu, Gabriel Dospinescu'') For <math>m</math> a positive integer, let <math>s(m)</math> be the sum of the digits of <math>m</math>. For <math>n\ge 2</math>, let <math>f(n)</math> be the minimal <math>k</math> for which there  exists a set <math>S</math> of <math>n</math> positive integers such that  <math>s\left(\sum_{x\in X} x\right) = k</math> for any nonempty subset <math>X\subset S</math>.  Prove that there are constants <math>0 < C_1 < C_2</math> with
-<cmath>
+<cmath>C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n.</cmath>
-C_1 \log_{10} n \le f(n) \le C_2 \log_{10} n.
-</cmath>
+== Solution ==
+For the upper bound, let <math>p</math> be the smallest integer such that <math>10^p\geq n(n+1)/2</math> and let
+<cmath>S = \{10^p - 1, 2(10^p - 1), \ldots, n(10^p - 1)\}.</cmath>
+The sum of any nonempty set of elements of <math>S</math> will have the form <math>k(10^p - 1)</math> for some <math>1\leq k\leq n(n+1)/2</math>. Write <math>k(10^p - 1) = [(k - 1)10^p] + [(10^p - 1) - (k - 1)]</math>. The second term gives the bottom <math>p</math> digits of the sum and the first term gives at most <math>p</math> top digits. Since the sum of a digit of the second term and the corresponding digit of <math>k - 1</math> is always 9, the sum of the digits will be <math>9p</math>. Since <math>10^{p-1} < n(n+1)/2</math>, this example shows that
+<cmath>f(n)\leq 9p\leq 9\log_{10}(5n(n+1)).</cmath>
+Since <math>n\geq 2</math>, <math>5(n + 1) < n^4</math>, and hence
+<cmath>f(n) < 9\log_{10}n^5 = 45\log_{10}n.</cmath>
+For the lower bound, let <math>S</math> be a set of <math>n\geq 2</math> positive integers such that any nonempty <math>X\subset S</math> has <math>s\left(\sum_{x\in X} x\right) = f(n)</math>. Since <math>s(m)</math> is always congruent to <math>m</math> modulo 9, <math>\sum_{x\in X} x\equiv f(n)\pmod{9}</math> for all nonempty <math>X\subset S</math>. Hence every element of <math>S</math> must be a multiple of 9 and <math>f(n)\geq 9</math>. Let <math>q</math> be the largest positive integer such that <math>10^q - 1\leq n</math>. Lemma 1 below shows that there is a nonempty subset <math>X</math> of <math>S</math> with <math>\sum_{x\in X} x</math> a multiple of <math>10^q - 1</math>, and hence Lemma 2 shows that <math>f(n)\geq 9q</math>.
+'''Lemma 1.''' Any set of <math>m</math> positive integers contains a nonempty subset whose sum is a multiple of <math>m</math>.
+''Proof.'' Suppose a set <math>T</math> has no nonempty subset with sum divisible by <math>m</math>. Look at the possible sums mod <math>m</math> of nonempty subsets of <math>T</math>. Adding a new element <math>a</math> to <math>T</math> will give at least one new sum mod <math>m</math>, namely the least multiple of <math>a</math> which does not already occur. Therefore the set <math>T</math> has at least <math>|T|</math> distinct sums mod <math>m</math> of nonempty subsets and <math>|T| < m</math>. <math>\blacksquare</math>
+'''Lemma 2.''' Any positive multiple <math>M</math> of <math>10^q - 1</math> has <math>s(M)\geq 9q</math>.
+''Proof.'' Suppose on the contrary that <math>M</math> is the smallest positive multiple of <math>10^q - 1</math> with <math>s(M) < 9q</math>. Then <math>M\neq 10^q - 1</math>, hence <math>M > 10^q</math>. Suppose the most significant digit of <math>M</math> is the <math>10^m</math> digit, <math>m\geq q</math>. Then <math>N = M - 10^{m-q}(10^q - 1)</math> is a smaller positive multiple of <math>10^q - 1</math> and has <math>s(N)\leq s(M) < 9q</math>, a contradiction. <math>\blacksquare</math>
+Finally, since <math>10^{q+1} > n</math>, we have <math>q + 1 > \log_{10} n</math>. Since <math>f(n)\geq 9q</math> and <math>f(n)\geq 9</math>, we have
+<cmath>f(n)\geq \frac{9q + 9}{2} > \frac{9}{2}\log_{10}n.</cmath>
+Weaker versions of Lemmas 1 and 2 are still sufficient to prove the desired type of lower bound.
+{{alternate solutions}}
+== See Also ==
+{{USAMO newbox|year=2005|num-b=5|after=Last Question}}
+{{MAA Notice}}

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

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

Latest revision as of 22:59, 29 March 2016

Problem

Solution

See Also