Advanced book on Mathematics Olympiad

660 Geometry and Trigonometry

S^2 = 2 −^2 n

∏^2 n

k= 1

(ζk+ζ−k)= 2 −^2 n×

∏^2 n

k= 1

ζ−k×

∏^2 n

k= 1

( 1 +ζ^2 k).

The first of the two products is justζ−(^1 +^2 +···+^2 n). Because 1+ 2 +···+ 2 n=n( 2 n+ 1 ),
which is a multiple of 2n+1, this product equals 1.
As for the product

∏ 2 n

k= 1 (^1 +ζ

2 k), note that it can be written as∏^2 n

k= 1 (^1 +ζ

k), since

the numbersζ^2 krange over the( 2 n+ 1 )st roots of unity other than 1 itself, taking each
value exactly once. We compute this using the factorization

zn+^1 − 1 =(z− 1 )

∏^2 n

k= 1

(z−ζk).

Substitutingz=−1 and dividing both sides by−2 gives

∏ 2 n
k= 1 (−^1 −ζ
k)=1, so
∏ 2 n
k= 1 (^1 +ζ

k)=1. HenceS (^2) = 2 − 2 n, and soS=± 2 −n. We need to determine the sign.
For 1≤k≤n, coskα <0 whenπ 2 <kα<π. The values ofkfor which this
happens aren+ 21 throughn. The number of suchkis odd ifn≡1or2(mod 4), and
even ifn≡0or3(mod 4). Hence

S=

{

+ 2 −n ifn≡1or2(mod 4),

− 2 −n ifn≡0or3(mod 4).

Takingn= 999 ≡ 3 (mod 4), we obtain the answer to the problem,− 2 −^999.
(proposed by J. Propp for the USA Mathematical Olympiad, 1999)

673.Define the complex numbersp=xeiA,q =yeiB, andr =zeiCand consider
f (n)=pn+qn+rn. ThenF (n)=Im(f (n)). We claim by induction thatf (n)is real
for alln, which would imply thatF (n)=0. We are given thatf( 1 )andf( 2 )are real,
andf( 0 )=3 is real as well.
Now let us assume thatf(k)is real for allk≤nfor somen≥3, and let us prove
thatf(n+ 1 )is also real. Note thata=p+q+r=f( 1 ),b=pq+qr+rp=
1
2 (f (^1 )

(^2) −f( 2 )), andc=pqr=xyzei(A+B+C)are all real. The numbersp, q, rare
the zeros of the cubic polynomialP(t)=t^3 −at^2 +bt−c, which has real coefficients.
Using this fact, we obtain
f(n+ 1 )=pn+^1 +qn+^1 +rn+^1
=a(pn+qn+rn)−b(pn−^1 +qn−^1 +rn−^1 )+c(pn−^2 +qn−^2 +rn−^2 )
=af (n)−bf ( n− 1 )+cf ( n− 2 ).
Sincef (n),f(n− 1 )andf(n− 2 )are real by the induction hypothesis, it follows that
f(n+ 1 )is real, and we are done.