16th Iberoamerican 2001 Problem B1 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?
(m-1)m for n = 2m m 2 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 = m 2 . These maxima can be achieved by taking the numbers 1, 2, 3, ... , n. 16th Ibero 2001 © John Scholes jscholes@kalva.demon.co.uk 21 January 2004