Maths Olympiad Prep

Library / /54 of 115

Algebra Difficulty 7.3 National olympiad, round 2 Find the answer

Find the maximum possible number of three term arithmetic progressions in a monotone sequence of nn distinct reals.

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

Solution

Consider the first few cases for nn with the entire nn numbers forming an arithmetic sequence (1,2,3,,n)(1, 2, 3, \ldots, n) If n=3n = 3 , there will be one ascending triplet (123). Let's only consider the ascending order for now.
If n=4n = 4 , the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total.
If n=5n = 5 , the first 4 numbers give 2 triplets, and the 5th number gives 2 more triplets (135 and 345).
Repeating a few more times, we can quickly see that if nn is even, the nth number will give n21\frac{n}{2} - 1 more triplets in addition to all the prior triplets from the first n1n-1 numbers.
If nn is odd, the nn th number will give n12\frac{n-1}{2} more triplets.
Let f(n)f(n) denote the total number of triplets for nn numbers. The above two statements are summarized as follows:
If nn is even, f(n)=f(n1)+n21f(n) = f(n-1) + \frac{n}2 - 1 If nn is odd, f(n)=f(n1)+n12f(n) = f(n-1) + \frac{n-1}2
Let's obtain the closed form for when nn is even: \begin{align*} f(n) &= f(n-2) + n-2\\ f(n) &= f(n-4) + (n-2) + (n-4)\\ f(n) &= \sum_{i=1}^{n/2} n - 2i\\ \Aboxed{f(n\ \text{even}) &= \frac{n^2 - 2n}4} \end{align*}
Now obtain the closed form when nn is odd by using the previous result for when nn is even: \begin{align*} f(n) &= f(n-1) + \frac{n-1}2\\ f(n) &= \frac{{(n-1)}^2 - 2(n-1)}4 + \frac{n-1}2\\ \Aboxed{f(n\ \text{odd}) &= \frac{{(n-1)}^2}4} \end{align*}
Note the ambiguous wording in the question! If the "arithmetic progression" is allowed to be a disordered subsequence, then every progression counts twice, both as an ascending progression and as a descending progression.
Double the expression to account for the descending versions of each triple, to obtain: \begin{align*} f(n\ \text{even}) &= \frac{n^2 - 2n}2\\ f(n\ \text{odd}) &= \frac{{(n-1)}^2}2\\ \Aboxed{f(n) &= \biggl\lfloor\frac{(n-1)^2}2\biggr\rfloor} \end{align*}
~Lopkiloinm (corrected by integralarefun)

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.