jump to navigation

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



\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



\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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: