2005 USAMO Problems/Problem 6
(Titu Andreescu, Gabriel Dospinescu) For a positive integer, let be the sum of the digits of . For , let be the minimal for which there exists a set of positive integers such that for any nonempty subset . Prove that there are constants with
For the upper bound, let be the smallest integer such that and let The sum of any nonempty set of elements of will have the form for some . Write . The second term gives the bottom digits of the sum and the first term gives at most top digits. Since the sum of a digit of the second term and the corresponding digit of is always 9, the sum of the digits will be . Since , this example shows that Since , , and hence For the lower bound, let be a set of positive integers such that any nonempty has . Since is always congruent to modulo 9, for all nonempty . Hence every element of must be a multiple of 9 and . Let be the largest positive integer such that . Lemma 1 below shows that there is a nonempty subset of with a multiple of , and hence Lemma 2 shows that .
Lemma 1. Any set of positive integers contains a nonempty subset whose sum is a multiple of .
Proof. Suppose a set has no nonempty subset with sum divisible by . Look at the possible sums mod of nonempty subsets of . Adding a new element to will give at least one new sum mod , namely the least multiple of which does not already occur. Therefore the set has at least distinct sums mod of nonempty subsets and .
Lemma 2. Any positive multiple of has .
Proof. Suppose on the contrary that is the smallest positive multiple of with . Then , hence . Suppose the most significant digit of is the digit, . Then is a smaller positive multiple of and has , a contradiction.
Finally, since , we have . Since and , we have 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)
|1 • 2 • 3 • 4 • 5 • 6
|All USAMO Problems and Solutions