10th Chinese 1995 Problem B2 a 1 , a 2 , ... , a 10 are distinct positive integers with sum 1995. What is the smallest possible value of a 1 a 2 + a 2 a 3 + ... + a 9 a 10 + a 10 + a 1 ?
4075, achieved by 1950, 1, 9, 2, 8, 3, 7, 4, 6, 5. Solution If a 1  a 10 , then reversing the order of a 1 , a 2 , ... , a 10 leaves the sum unchanged. So we can assume that a 1 is the largest. Now suppose a 2 > a i for 2  a 10 , then reversing the order of a 2 , a 3 , ... , a 10 reduces the sum by (a 2 - a 10 )(a 1 - 1) >= 0. So we can assume that a 2 is the smallest. The smallest possible sum for 9 distinct positive integers is 1 + 2 + ... + 9 = 45. So the largest possible value for a 1 is 1950. If a 1  0. If k is 10 we reduce the sum by a 9 - a 2 > 0. If 2  0. So we must have a 1 = 1950. Thus a 2 , ... , a 10 is a permutation of 1, 2, ... , 9 and hence a 2 = 1. If a 3  a 10 , then reversing the order of a 4 , ... , a 10 reduces the sum by 8(a 4 - a 10 ). If a 4 > a i for 4  0. So a 4 = 2. Exactly similar arguments show that we 1950, 1, 9, 2, 8, 3, 7, 4, 6, 5 is a minimal solution (but not necessarily the only one). It is easy to check that it gives 4075. 10th Chinese 1995 © John Scholes jscholes@kalva.demon.co.uk 5 Jan 2003