Call a set of 3 distinct elements which are in arithmetic progression a trio. What is the largest number of trios that can be subsets of a set of n distinct real numbers?
Answer
(m-1)m for n = 2m
m2 for n = 2m+1
Solution
Let X be one of the elements. What is the largest number of trios that can have X as middle element? Obviously, at most max(b,a), where b is the number of elements smaller than X and a is the number larger. Thus if n = 2m, the no. of trios is at most 0 + 1 + 2 + ... + m-1 + m-1 + m-2 + ... + 1 + 0 = (m-1)m. If n = 2m+1, then the no. is at most 0 + 1 + 2 + ... + m-1 + m + m-1 + ... + 1 + 0 = m2.
These maxima can be achieved by taking the numbers 1, 2, 3, ... , n.
© John Scholes
jscholes@kalva.demon.co.uk
21 January 2004