Maths Olympiad Prep

Library / /67 of 115

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

Determine the maximum number of three-term arithmetic progressions which can be chosen from a sequence of nn real numbers a1<a2<<an.a_1<a_2<\cdots<a_n.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us define the problem: We need to determine the maximum number of three-term arithmetic progressions (APs) that can be chosen from a sequence of n n real numbers a1<a2<<an a_1 < a_2 < \cdots < a_n .

Let's explore how to construct such APs from the sequence. An arithmetic progression of three terms (ai,aj,ak) (a_i, a_j, a_k) must satisfy the condition aj=ai+ak2 a_j = \frac{a_i + a_k}{2} , which implies 2aj=ai+ak 2a_j = a_i + a_k .

Given the ordered sequence a1<a2<<an a_1<a_2<\cdots<a_n , consider choosing two numbers, say ai a_i and ak a_k , where i<j<k i < j < k . The middle term aj a_j must be chosen such that it satisfies the progression rule:

2aj=ai+ak 2a_j = a_i + a_k

This implies that for each pair (ai,ak) (a_i, a_k) , the middle term aj a_j needs to maintain the order ai<aj<ak a_i < a_j < a_k . Thus, the choice of middle term is crucial to forming valid APs.

The number of valid values for aj a_j given fixed ai a_i and ak a_k is determined by the number of indices j j that satisfy i<j<k i < j < k .

To maximize the number of such progressions, observe that if the sequence a1,a2,,an a_1, a_2, \ldots, a_n is divided such that each possible middle term aj a_j can maximize the possible pairs (ai,ak) (a_i, a_k) around it, then the most progressions will occur.

It can be shown that placing the middle term aj a_j centrally in the division naturally permits forming progressions around it effectively. As the problem reduces to selecting central middle terms optimally, the sequence can best be divided by grouping intervals of roughly half the sequence length:

1. Choose j j in the middle n/2\approx \lfloor n/2 \rfloor.
2. Use each aj a_j centrally where possible for the rest of the sequence.

Thus, the number of such progressions is given by:

n/2(n(1+n/2)) \lfloor n/2 \rfloor (n - (1 + \lfloor n/2 \rfloor))

This expression accounts for selecting the middle term aj a_j for as many maximum index pairs (i,k) (i, k) permissible for an arithmetic progression around aj a_j .

Therefore, the maximum number of three-term arithmetic progressions which can be chosen from this sequence is:

n/2(n(1+n/2)) \boxed{\lfloor n/2 \rfloor (n - (1 + \lfloor n/2 \rfloor))}
```

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.