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 "1985 USAMO Problems/Problem 2"

(New solution)
m (→‎Solution)
 
Line 57: Line 57:
 
<cmath>\tilde{x}_2=10^5+\frac{1+\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}.</cmath>
 
<cmath>\tilde{x}_2=10^5+\frac{1+\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}.</cmath>
 
We can similarly prove it has the desired approximation.
 
We can similarly prove it has the desired approximation.
 +
 +
==Notes==
 +
 +
Another round of iteration can increase the accuracy to more than 10 decimal places:
 +
<cmath>\begin{align*}
 +
\tilde{x}_1^\prime=10^5+\frac{1-\sqrt{1+4(\tilde{x}_1+1)}}{2(\tilde{x}_1+10^5)},\\
 +
\tilde{x}_2^\prime=10^5+\frac{1+\sqrt{1+4(\tilde{x}_2+1)}}{2(\tilde{x}_2+10^5)}.
 +
\end{align*}</cmath>
 +
 +
J.Z.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 07:32, 18 May 2018

Problem

Determine each real root of

$x^4-(2\cdot10^{10}+1)x^2-x+10^{20}+10^{10}-1=0$

correct to four decimal places.

Solution

The equation can be re-written as \begin{align}\label{eqn1} (x+10^5)^2(x-10^5)^2 -(x+10^5)(x-10^5) -x-1=0. \end{align}

We first prove that the equation has no negative roots. Let $x\le 0.$ The equation above can be further re-arranged as \begin{align*}[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2]=x-1.\end{align*} The right hand side of the equation is negative. Therefore \[[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2)]<0,\] and we have $-1<(x+10^5)(x-10^5) <2.$ Then the left hand side of the equation is bounded by \[|[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2]|\le 3\times 3.\] However, since $|(x+10^5)(x-10^5)|\le 2$ and $x<0,$ it follows that $|x+10^5| <\frac{2}{|x-10^5|}<2\times 10^{-5}$ for negative $x.$ Then $x<2\times 10^{-5}-10^5.$ The right hand side of the equation is then a large negative number. It cannot be equal to the left hand side which is bounded by 9.

Now let $x>0.$ When $x=10^5,$ the left hand side of equation (1) is negative. Therefore the equation has real roots on both side of $10^5$, as its leading coefficient is positive. We will prove that $x=10^5$ is a good approximation of the roots (within $10^{-2}$). In fact, we can solve the "quadratic" equation (1) for $(x+10^5)(x-10^5)$: \[(x+10^5)(x-10^5)=\frac{1\pm\sqrt{1+4(x+1)}}{2}.\] Then \[x-10^5=\frac{1\pm\sqrt{1+4(x+1)}}{2(x+10^5)}.\] Easy to see that $|x-10^5| <1$ for positve $x.$ Therefore, $10^5-1<x<10^5+1.$ Then \begin{align*} |x-10^5|&=\left|\frac{1\pm\sqrt{1+4(x+1)}}{2(x+10^5)}\right |\\ &\le \left |\frac{1}{2(x+10^5)}\right |+\left |\frac{\sqrt{1+4(x+1)}}{2(x+10^5)}\right |\\ &\le \frac{1}{2(10^5-1+10^5)} +\frac{\sqrt{1+4(10^5+1+1)}}{2(10^5-1+10^5)} \\ &<10^{-2}. \end{align*}

Let $x_1$ be a root of the equation with $x_1<10^5.$ Then $0<10^5-x_1<10^{-2}$ and \[x_1-10^5=\frac{1-\sqrt{1+4(x_1+1)}}{2(x_1+10^5)}.\] An aproximation of $x_1$ is defined as follows: \[\tilde{x}_1=10^5+\frac{1-\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}.\] We check the error of the estimate: \begin{align*} |\tilde{x}_1-x_1|&=\left | \frac{1-\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}- \frac{1-\sqrt{1+4(x_1+1)}}{2(x_1+10^5)} \right | \\ &\le \left |\frac{1}{2(10^5+10^5)}- \frac{1}{2(x_1+10^5)}\right |+\left |\frac{\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}- \frac{\sqrt{1+4(x_1+1)}}{2(x_1+10^5)}\right |. \end{align*}

The first absolute value \[\left |\frac{1}{2(10^5+10^5)}- \frac{1}{2(x_1+10^5)}\right | =\frac{|x_1- 10^5|}{2(10^5+10^5)(x_1+10^5)}<10^{-12}.\]

The second absolute value \begin{align*} &\left |\frac{\sqrt{1+4(10^5+1)}}{2(10^5+10^5)} - \frac{\sqrt{1+4(x_1+1)}}{2(x_1+10^5)} \right |\\ &\le \left |\frac{\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}- \frac{\sqrt{1+4(x_1+1)}}{2(10^5+10^5)}\right |+\left |\frac{\sqrt{1+4(x_1+1)}}{2(10^5+10^5)}- \frac{\sqrt{1+4(x_1+1)}}{2(x_1+10^5)}\right |\\ &\le 10^{-7}+10^{-9}, \end{align*} through a rationalized numerator.Therefore $|\tilde{x}_1-x_1|\le 10^{-6}.$

For a real root $x_2$ with $x_2>10^5,$ we choose \[\tilde{x}_2=10^5+\frac{1+\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}.\] We can similarly prove it has the desired approximation.

Notes

Another round of iteration can increase the accuracy to more than 10 decimal places: \begin{align*} \tilde{x}_1^\prime=10^5+\frac{1-\sqrt{1+4(\tilde{x}_1+1)}}{2(\tilde{x}_1+10^5)},\\ \tilde{x}_2^\prime=10^5+\frac{1+\sqrt{1+4(\tilde{x}_2+1)}}{2(\tilde{x}_2+10^5)}. \end{align*}

J.Z.

See Also

1985 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=1985_USAMO_Problems/Problem_2&oldid=94593"