Advanced book on Mathematics Olympiad

Algebra 447

the trianglePQRwhosex- andy-coordinates are both negative, and if thez-coordinate
ofTis positive, chooseSto have thex- andy-coordinates positive. Then the coordinates
ofSare all negative, or all positive, and again we are done.
(short list of the 44th International Mathematical Olympiad, 2003, proposed by
the USA)

265.Letλbe the positive eigenvalue andv=(v 1 ,v 2 ,...,vn)the corresponding eigen-
vector with positive entries of the transpose of the coefficient matrix. The function
y(t)=v 1 x 1 (t)+v 2 x 2 (t)+···+vnxn(t)satisfies

dy

dt

=

∑

i,j

viaijxj=

∑

j

λvjxj=λy.

Therefore,y(t)=eλty 0 , for some vectory 0. Because

lim

t→∞

y(t)=

∑

i

vilim

t→∞

xi(t)= 0 ,

and limt→∞eλt=∞, it follows thaty 0 is the zero vector. Hence

y(t)=v 1 x 1 (t)+v 2 x 2 (t)+···+vnxn(t)= 0 ,

which shows that the functionsx 1 ,x 2 ,...,xnare necessarily linearly dependent.
(56th W.L. Putnam Mathematical Competition, 1995)

266.We try some particular cases. Forn=2, we obtainc=1 and the sequence 1,1, or
n=3,c=2 and the sequence 1, 2 ,1, and forn=4,c=3 and the sequence 1, 3 , 3 ,1.
We formulate the hypothesis thatc=n−1 andxk=

(n− 1

k− 1

)

.

The conditionxn+ 1 =0 makes the recurrence relation from the statement into a linear
system in the unknowns(x 1 ,x 2 ,...,xn). More precisely, the solution is an eigenvector
of the matrixA=(aij)ijdefined by

aij=

⎧

⎪⎨

⎪⎩

i ifj=i+ 1 ,

n−j ifj=i− 1 ,

0 otherwise.

This matrix has nonnegative entries, so the Perron–Frobenius Theorem as stated here
does not really apply. But let us first observe thatAhas an eigenvector with positive
coordinates, namelyxk=

(n− 1

k− 1

)

,k= 1 , 2 ,...,n, whose eigenvalue isn−1. This follows
by rewriting the combinatorial identity
(
n− 1
k

)

=

(

n− 2

k

)

+

(

n− 2

k− 1

)