## USAMO 1973 #4 August 19, 2009

Posted by lumixedia in algebra, Problem-solving.
Tags: , , , ,

A fairly straightforward algebra problem. Could appear on a modern AMC-12, though the decoy answers would have to be carefully written.

USAMO 1973 #4. Determine all the roots, real or complex, of the system of simultaneous equations

$\displaystyle x+y+z=3$

$\displaystyle x^2+y^2+z^2=3$

$\displaystyle x^3+y^3+z^3=3$

Solution. First note that

$\displaystyle (x+y+z)^2=x^2+y^2+z^2+2xy+2yz+2zx$

$\displaystyle 3^2=3+2(xy+yz+zx)$

$\displaystyle xy+yz+zx=3$

Let ${c=xyz}$, so that ${x,y,z}$ are the roots of the polynomial ${t^3-3t^2+3t-c}$. Then we have

$\displaystyle x^3-3x^2+3x-c=0$

$\displaystyle y^3-3y^2+3y-c=0$

$\displaystyle z^3-3z^2+3z-c=0$

Summing these three equalities together gives

$\displaystyle x^3+y^3+z^3-3(x^2+y^2+z^2)+3(x+y+z)-3c=0$

or

$\displaystyle 3-3(3)+3(3)-3c=0$

from which ${c=1}$. So ${x,y,z}$ are the roots of the polynomial ${t^3-3t^2+3t-1=(t-1)^3}$, and the only solution is ${x=y=z=1}$.

An interesting note is that the scan of the original test shows the last inequality as ${x^5+y^5+z^5=3}$. While the official solution makes clear that ${x^3+y^3+z^3=3}$ was intended, the problem is only slightly trickier as originally printed. Here’s how to do the typoed-up version. Let ${s_k=x^k+y^k+z^k}$. The calculation of ${xy+yz+xz=3}$ stands. We also have, just like before,

$\displaystyle x^3+y^3+z^3-3(x^2+y^2+z^2)+3(x+y+z)-3c=0$

or

$\displaystyle s_3-3(3)+3(3)-3c=0$

so we can write ${s_3=3c}$. By multiplying one of the equalities we used before by ${x}$, we get

$\displaystyle x^4-3x^3+3x^2-cx=0$

as well as the two analogous equations in ${y}$ and ${z}$, and summing these up gives

$\displaystyle s_4-3s_3+3s_2-cs_1=0$

$\displaystyle s_4-3(3c)+3(3)-3c=0$

$\displaystyle s_4=12c-9.$

Similarly, since we know

$\displaystyle x^5-3x^4+3x^3-cx^2=0$

as well as the two analogous equations, we can sum them up to get

$\displaystyle s_5-3s_4+3s_3-cs_2=0$

$\displaystyle 3-3(12c-9)+3(3c)-3c=0$

which gives ${c=1}$ as before, so we conclude that ${x=y=z=1}$ as before.

You can see from the intermediate step ${s_4=12c-9}$ that giving ${x^4+y^4+z^4=3}$ for the last equation would also have worked and given the same answer. Using ${x^6+y^6+z^6=3}$ makes things a little more complicated. The analogous solution gives the quadratic ${c^2+18c-19=0}$, so in addition to ${c=1}$ as before, we can also take ${c=-19}$, making the polynomial ${t^3-3t^2+3t+19=0}$ or ${(t-1)^3=-20}$, so we have a second solution ${x=1-\sqrt[3]{20}}$, ${y=1-\omega\sqrt[3]{20}}$, ${z=1-\omega^2\sqrt[3]{20}}$ where ${\omega}$ is an imaginary cube root of unity. For still higher powers things probably continue to get worse.

1. Akhil Mathew - August 19, 2009

I think a general system of equations in $n$ variables, say $\sum_{j=1}^n x_j^i = c_i$, for $c_i \ (1 \leq i \leq n)$ elements of some algebraically closed field can be solved up to permutation. Indeed, the polynomials $P_i := \sum_{j=1}^n x_j^i$ generate the ring of symmetric functions in the $x_j$. So by writing the elementary symmetric functions $s_i$ in terms of the $P_i$ (which we can do in any polynomial ring), yields what $s_i(x)$ is. Then note that the polynomial $\prod_{i=1}^n (T - x_i) = T^n - T^{n-1} s_1(x) \pm \dots$. We know what the polynomial to the right by the above, so we can find the roots in $T$ to get the $x_i$ up to a permutation.

Qiaochu Yuan - August 19, 2009

The subtlety is in solving a system like $\sum x_j^{b_i} = c_i$, since then one has to use Newton’s sums and so forth to determine the various relations that emerge. I’d like to add that in order to conclude that the power symmetric functions generate the symmetric functions one has to specify that the underlying ring is a field of characteristic zero. (On the other hand, the elementary symmetric functions generate the symmetric functions over any commutative ring.) I’ll be writing a post about symmetric functions soon if anyone wants details.

Akhil Mathew - August 19, 2009

Ok, I must have forgotten that subtlety. I’ll read your post to clarify my understanding.

Qiaochu Yuan - August 20, 2009

Maybe “subtlety” was too strong a word. All I meant is that even if you accept that your proposal works for $b_i = i$ it doesn’t follow that you can always solve for the $x_j$ up to permutation for arbitrary increasing sequences $b_i$ as in the $x^5 + y^5 + z^5$ extension; this is clearly false for $b_i = 2i$, for example, since you can at best solve up to sign. This is actually an interesting question to think about; is relative primality sufficient?

2. Akhil Mathew - August 20, 2009

Actually, my reference to a “subtlelty” (didn’t realize you had used that word for something else) was the fact that the power sums only generate the symmetric polynomials over a field of characteristic zero.
I did not expect the methods to generalize to arbitrary increasing sequences $b_i$.

By the way, is it enough to conclude that the power sums generate the symmetric polynomials, if the ring contains $\mathbb{Q}$?

Qiaochu Yuan - August 20, 2009

Yep. In practice, the choice of coefficient ring is irrelevant since the interesting relations among the common classes of symmetric functions can be defined over $\mathbb{Q}$ or even $\mathbb{Z}$ and then one can take tensor products to recover the general case.

Qiaochu Yuan - August 20, 2009

Well, not irrelevant. The positive characteristic case is very different from the characteristic zero case.