1995 USAMO Problems/Problem 2
Problem
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.
Solution
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.
Resources
1995 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |