2001 USA TST Problems/Problem 9
Problem
(Zuming Feng)
Let be a finite set of positive integers. Prove that there exists
a finite set
of positive integers such that
and
Solution
Lemma 1. For any finite set of positive integers, there exists a finite set
of positive integers such that
and
.
Proof. Let us abbreviate and
. Suppose that
(otherwise, we may have
). Let
be a positive integer larger than
(and thus larger than any element of
). Taking
, evidently
, and
as desired.
Lemma 2. For any finite set of positive integers such that
, there exists a finite set
of positive integers such that
and
Proof. Let us abbreviate , and
. We induct on the quantity
, which by hypothesis is a nonnegative integer.
For our base case, , we may take
.
Now suppose that the lemma holds for . Suppose
. Let
. Then
so by inductive hypothesis, there exists a set
such that
and
Since
, this set
satisfies the lemma's conditions.
Combining the statments of Lemmata 1 and 2, we are done.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
- 2001 USA TST Problems
- <url>Forum/viewtopic.php?t=24756 Discussion on AoPS/MathLinks</url>