Difference between revisions of "1995 USAMO Problems/Problem 2"
m (→Resources) |
|||
Line 21: | Line 21: | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | == | + | == See Also == |
{{USAMO box|year=1995|num-b=1|num-a=3}} | {{USAMO box|year=1995|num-b=1|num-a=3}} |
Revision as of 08:05, 19 July 2016
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.
See Also
1995 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
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.