1978 USAMO Problems/Problem 3
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.
Is there an algorithm to deduce another good integer given a good integer? You might want to use the fact that .
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.
|1978 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|