42nd IMO 2001 shortlist Problem C1 What is the largest number of subsequences of the form n, n+1, n+2 that a sequence of 2001 positive integers can have? For example, the sequence 1, 2, 2, 3, 3, of 5 terms has 4 such subsequences. Solution
: 667 3 . We show that 1, ... , 1, 2, ... , 2, 3, ... , 3 (with 667 1s, 667 2s and 667 3s) is maximal. There are several stages. Let the sequence be a 1 , a 2 , ... , a 2001 . We show first that there is a maximal sequence with a 1 ≤ a 2 ≤ ... ≤ a 2001 . For suppose there is a maximal sequence with a i > a i+1 . Swapping these two terms cannot decrease the number of subsequences n, n+1, n+2. By a series of such swaps we get another maximal sequence with a 1 ≤ a 2 ≤ ... ≤ a 2001 . Next we show that there is a maximal sequence with a i = a i+1 or a i+1 + 1 for each i. For suppose a maximal sequence has a i ≥ a i+1 + d+1. Then by adding d to a i and all earlier terms we do not decrease the number of subsequences n, n+1, n+2. So by a series of such changes we can get another maximal sequence with a i = a i+1 or a i+1 + 1 for each i. Thus there is a maximal sequence with b 0 terms k, followed by b 1 terms k+1, followed by b 2 terms k+2 and so on up to b h terms k+h. The number of sequences n, n+1, n+2 is evidently N = b 0 b 1 b 2 + b 1 b 2 b 3 + b 2 b 3 b 4 + ... + b n-2 b n-1 b n . But if n ≥ 2, then changing from b 0 , b 1 , ... , b n to b 1 , b 2 , (b 0 + b 3 , b 4 , ... b n increases N by b 0 b 2 b 4 + b 0 b 4 b 5 (or leaves it unchanged if n = 3). So we may take n = 2. (Obviously a maximal sequence cannot have n < 2, because then it has no subsequences of the required form.) Only differences matter, so we may take the first term to be 1. Thus there is a maximal sequence 1, ... , 1, 2, ... , 2, 3, ... , 3 with a 1s b 2s and c 3s, where a + b + c = 2001. Such a sequence obviously has abc subsequences of the required form. But by the arithmetic/geometric mean inequality, abc is maximised by taking a = b = c. 42nd IMO shortlist 2001 © John Scholes jscholes@kalva.demon.co.uk 14 Oct 2002 Last corrected/updated 14 Oct 02