1985 USAMO Problems/Problem 2

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.

1985 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1985 USAMO Problems/Problem 2

Contents

Problem

Solution

Notes

See Also