Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1995 USAMO Problems/Problem 2"

m (→‎Resources)
(Bruh this logged me out in the middle of writing. Thankfully I saved it)
Line 20: Line 20:
  
 
{{alternate solutions}}
 
{{alternate solutions}}
 +
Alternate Solution (using infinite descent):
  
 +
This solution is similar to the above solution. We can invert it with<cmath>\tan \sin^{-1} \cos \tan^{-1} \sqrt{n/m} = \sqrt{m/n}</cmath>and we can get<cmath>\tan \sin^{-1} \cos \tan^{-1}\cos\tan^{-1}\sqrt{x} = \sqrt{x + 1}.</cmath>
 +
Then we do <math>\sqrt{x}</math> to <math>\sqrt{x + 1}</math> in reverse, trying to get 1. Subtracting one inside the radical for a fraction <math>\sqrt{m/n}</math> 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 <math>\sqrt{m/n}</math> 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.
 +
 +
~Unum
 
== See Also ==
 
== See Also ==
  

Revision as of 23:16, 5 April 2020

Problem

A calculator is broken so that the only keys that still work are the $\, \sin, \; \cos,$ $\tan, \; \sin^{-1}, \; \cos^{-1}, \,$ and $\, \tan^{-1} \,$ buttons. The display initially shows 0. Given any positive rational number $\, q, \,$ show that pressing some finite sequence of buttons will yield $\, q$. 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 $m$ and $n$ are relatively prime nonnegative integers such that $n>0$, then the some finite sequence of buttons will yield $\sqrt{m/n}$.

To prove this statement, we induct strongly on $m+n$. For our base case, $m+n=1$, we have $n=1$ and $m=0$, and $\sqrt{m/n} = 0$, which is initially shown on the screen. For the inductive step, we consider separately the cases $m=0$, $0<m\le n$, and $n<m$.

If $m=0$, then $n=1$, and we have the base case.

If $0< m \le n$, then by inductive hypothesis, $\sqrt{(n-m)/m}$ can be obtained in finitely many steps; then so can \[\cos \tan^{-1} \sqrt{(n-m)/m} = \sqrt{m/n} .\]

If $n<m$, then by the previous case, $\sqrt{n/m}$ can be obtained in finitely many steps. Since $\cos \tan^{-1} \sqrt{n/m} = \sin \tan^{-1} \sqrt{m/n}$, it follows that \[\tan \sin^{-1} \cos \tan^{-1} \sqrt{n/m} = \sqrt{m/n}\] can be obtained in finitely many steps. Thus the induction is complete. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page. Alternate Solution (using infinite descent):

This solution is similar to the above solution. We can invert it with\[\tan \sin^{-1} \cos \tan^{-1} \sqrt{n/m} = \sqrt{m/n}\]and we can get\[\tan \sin^{-1} \cos \tan^{-1}\cos\tan^{-1}\sqrt{x} = \sqrt{x + 1}.\] Then we do $\sqrt{x}$ to $\sqrt{x + 1}$ in reverse, trying to get 1. Subtracting one inside the radical for a fraction $\sqrt{m/n}$ 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 $\sqrt{m/n}$ 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.

~Unum

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1995_USAMO_Problems/Problem_2&oldid=120579"