Find the maximum possible number of three term arithmetic progressions in a monotone sequence of n distinct reals.
Solution
Answer: m2 for n = 2m+1, m(m-1) for n = 2m.
Let the reals be a1, ... , an. Suppose n = 2m+1 and the middle term is ak. If k < m+1, then we are constrained by the shortage of first terms. If k > m+1 we are constrained by the shortage of third terms. Thus if k = 1, ak cannot be the middle term. If k = 2, there is only one candidate for the first term. If k = 3, there are two candidates for the middle terms and so on. Thus the total number of possible progressions certainly cannot exceed: 1 + 2 + ... + m + m-1 + m-2 + ... + 1 = m(m+1)/2 + m(m-1)/2 = m2. But this bound is achieved by the sequence 1, 2, 3, ... , n.
Similarly, if n = 2m, then the upper bound is 1 + 2 + ... + m-1 + m-1 + ... + 1 = m(m-1). Again, this is achieved by the sequence 1, 2, ... , n.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002