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>