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"

(Created page with "== Problem == Determine each real root of <math>x^4-(2\cdot10^{10}+1)x^2-x+10^{20}+10^{10}-1=0</math> correct to four decimal places. ==Solution== {{solution}} == See Also...")
 
m (→‎Solution)
 
(One intermediate revision by the same user not shown)
Line 7: Line 7:
  
 
==Solution==
 
==Solution==
−
{{solution}}
+
The equation can be re-written as
 +
<cmath>\begin{align}\label{eqn1}
 +
(x+10^5)^2(x-10^5)^2 -(x+10^5)(x-10^5) -x-1=0.
 +
\end{align}</cmath>
 +
 
 +
We first prove that the equation has no negative roots.
 +
Let <math>x\le 0.</math> The equation above can be further re-arranged as
 +
<cmath>\begin{align*}[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2]=x-1.\end{align*}</cmath>
 +
The right hand side of the equation is negative. Therefore <cmath>[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2)]<0,</cmath> and we have
 +
<math>-1<(x+10^5)(x-10^5) <2.</math> Then the left hand side of the equation is bounded by
 +
<cmath>|[(x+10^5)(x-10^5)+1][(x+10^5)(x-10^5)-2]|\le 3\times 3.</cmath>
 +
However, since <math>|(x+10^5)(x-10^5)|\le 2</math> and <math>x<0,</math> it follows that <math>|x+10^5| <\frac{2}{|x-10^5|}<2\times 10^{-5}</math> for negative <math>x.</math> Then <math>x<2\times 10^{-5}-10^5.</math> 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 <math>x>0.</math> When <math>x=10^5,</math> the left hand side of equation (1) is negative. Therefore the equation has real roots on both side of <math>10^5</math>, as its leading coefficient is positive. We will prove that <math>x=10^5</math> is a good approximation of the roots (within <math>10^{-2}</math>). In fact, we can solve the "quadratic" equation (1) for <math>(x+10^5)(x-10^5)</math>:
 +
<cmath>(x+10^5)(x-10^5)=\frac{1\pm\sqrt{1+4(x+1)}}{2}.</cmath>
 +
Then <cmath>x-10^5=\frac{1\pm\sqrt{1+4(x+1)}}{2(x+10^5)}.</cmath>
 +
Easy to see that
 +
<math>|x-10^5| <1</math> for positve <math>x.</math> Therefore, <math>10^5-1<x<10^5+1.</math> Then
 +
<cmath>\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*}</cmath>
 +
 
 +
Let <math>x_1</math> be a root of the equation with <math>x_1<10^5.</math> Then <math>0<10^5-x_1<10^{-2}</math> and
 +
<cmath>x_1-10^5=\frac{1-\sqrt{1+4(x_1+1)}}{2(x_1+10^5)}.</cmath>
 +
An aproximation of <math>x_1</math> is defined as follows:
 +
<cmath>\tilde{x}_1=10^5+\frac{1-\sqrt{1+4(10^5+1)}}{2(10^5+10^5)}.</cmath>
 +
We check the error of the estimate:
 +
<cmath>\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*}</cmath>
 +
 
 +
The first absolute value
 +
<cmath> \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}.</cmath>
 +
 
 +
The second absolute value
 +
<cmath>\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*}</cmath>
 +
through a rationalized numerator.Therefore <math>|\tilde{x}_1-x_1|\le 10^{-6}.</math>
 +
 
 +
For a real root <math>x_2</math> with <math>x_2>10^5,</math> we choose
 +
<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.
 +
 
 +
==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"