42nd IMO shortlist 2001/C1 solution

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

Answer: 667³.

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₁, a₂, ... , a₂₀₀₁. We show first that there is a maximal sequence with a₁ ≤ a₂ ≤ ... ≤ a₂₀₀₁. 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₁ ≤ a₂ ≤ ... ≤ a₂₀₀₁.

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₀ terms k, followed by b₁ terms k+1, followed by b₂ 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₀b₁b₂ + b₁b₂b₃ + b₂b₃b₄ + ... + b_n-2b_n-1b_n. But if n ≥ 2, then changing from b₀, b₁, ... , b_n to b₁, b₂, (b₀ + b₃, b₄, ... b_n increases N by b₀b₂b₄ + b₀b₄b₅ (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