# Difference between revisions of "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 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.