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