# 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>