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

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

(New page: ==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</...)
 
m (→‎Solution)
 
(8 intermediate revisions by 5 users not shown)
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=
+
== 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}}

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.

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"