1998 USAMO Problems/Problem 5
Problem
Prove that for each , there is a set of integers such that divides for every distinct .
Solution
Proof by induction. For n=2, the proof is trivial, since satisfies the condition. Assume now that there is such a set S of n elements, which satisfy the condition. The key is to note that if , then if we define for all , where k is a positive integer, then and , and so .
Let . Consider the set . To finish the proof, we simply need to choose a k such that for all . Since , simply choose k so that .
See Also
1998 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
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.