1995 USAMO Problems/Problem 2
A calculator is broken so that the only keys that still work are the and buttons. The display initially shows 0. Given any positive rational number show that pressing some finite sequence of buttons will yield . Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians.
We will prove the following, stronger statement : If and are relatively prime nonnegative integers such that , then the some finite sequence of buttons will yield .
To prove this statement, we induct strongly on . For our base case, , we have and , and , which is initially shown on the screen. For the inductive step, we consider separately the cases , , and .
If , then , and we have the base case.
If , then by inductive hypothesis, can be obtained in finitely many steps; then so can
If , then by the previous case, can be obtained in finitely many steps. Since , it follows that can be obtained in finitely many steps. Thus the induction is complete.
Alternate Solution (using infinite descent):
This solution is similar to the above solution. We can invert a number with and we can get Then we do to in reverse, trying to get 1. Subtracting one inside the radical for a fraction will eventually result in a fraction less than or equal to 1. Taking the reciprocal of this will result in a fraction greater than or equal to 1, and we can keep subtracting one inside the radical.
We do this repeatedly, and this should eventually result in 1 in a finite number of steps. This is because each time we do this, m+n is smaller. This is true even if can be simplified, as simplifying will only result in a smaller value. The smallest possible value of the fraction is 1/1, so this will be achieved after finite steps.
Finally, we know that 1 is achievable as cos(0) = 1.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|1995 USAMO (Problems • Resources)
|1 • 2 • 3 • 4 • 5
|All USAMO Problems and Solutions