2005 USAMO Problems/Problem 6
Problem
(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
Solution
For the upper bound, let be the smallest integer such that
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 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.
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.