13th Chinese 1998 Problem B3 The reals x 1 , x 2 , ... , x n satisfy (x 1 2 + ... + x n 2 ) + (x 1 x 2 + x 2 x 3 + ... + x n-1 x n ) = 1. What is the maximum possible value of | x k |? Solution
: √( 2k(n-k+1)/(n+1) ). We complete the square, starting at the ends and moving towards the middle. For example suppose n = 3 and we are interested in x 2 . We have: x 1 2 + x 2 2 + x 3 2 + x 1 x 2 + x 2 x 3 = (x 1 + 1/2 x 2 ) 2 + 1/2 x 2 2 + (1/2 x 2 + x 3 ) 2 , so x 2 2 ≤ 2. In general, we have (x 1 + 1/2 x 2 ) 2 + 3/4 (x 2 + 2/3 x 3 ) 2 + 4/6 (x 3 + 3/4 x 4 ) 2 + 5/8 (x 4 + 4/5 x 5 ) 2 + ... + k/(2k-2) (x k-1 + (k-1)/k x k ) 2 - (k-1)/(2k) x k 2 = x 1 2 + x 2 2 + ... + x k-1 2 + x 1 x 2 + x 2 x 3 + ... + x k-1 x k . Similarly, (x n + 1/2 x n-1 ) 2 + 3/4 (x n-1 + 2/3 x n-2 ) 2 + 4/6 (x n-2 + 3/4 x n-3 ) 2 + ... + (n-k+1)/(2n-2k) (x k+1 + (n-k)/(n- k+1) x n-(n-k) ) 2 - (n-k)/(2n-2k+2) x k 2 = x k+1 2 + x k+2 2 + ... + x n 2 + x k x k+1 + x k+1 x k+2 + ... + x n-1 x n . Hence 1 = (x 1 2 + ... + x n 2 ) + (x 1 x 2 + x 2 x 3 + ... + x n-1 x n ) = (1 - (k-1)/(2k) - (n-k)/(2n-2k+2) ) x k 2 + a collection of other squares = (n+1)/( 2k(n+1-k) ) + a collection of other squares. Clearly, the maximum possible value of x k occurs if the other squares are all zero, which is possible by a suitable choice of other x i . Hence the maximum possible value of x k is the square root of ( 2k(n+1-k) )/(n+1). 13th Chinese 1998 © John Scholes jscholes@kalva.demon.co.uk 6 July 2002