1978 USAMO Problems/Problem 3
Contents
[hide]Problem
An integer will be called good if we can write
,
where are positive integers (not necessarily distinct) satisfying
.
Given the information that the integers 33 through 73 are good, prove that every integer is good.
Hint
Is there an algorithm to deduce another good integer given a good integer? You might want to use the fact that .
Solution
Lemma: If is a good integer, then so is and .
Proof: Let such that where the are positive integers. Then, notice that so is also a good integer. Furthermore, so is also good.
This completes the lemma. Now, we use induction to show that the integers from 33 to are all good, where .
Base case: Our given takes care of . Inductive step: Assume the integers between 33 and , inclusive, are all good. Now, we casework on parity of .
If is odd, then write for some integer .
It follows that because , we must have
Thus, , and so is good by the inductive hypothesis. Applying the lemma gives as a good integer.
If is even, write for some integer . Therefore, so that , meaning that is a good integer by the inductive hypothesis. From the lemma, must be good as well.
This completes the inductive step and thus the induction. Therefore, all integers are good integers.
See Also
1978 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.