Maths Olympiad Prep

Library / /68 of 135

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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: f(n) = f(n-2) + n-2 f(n) = f(n-4) + (n-2) + (n-4) f(n) = i=1 n/2 n - 2i f(n even ) = n 2 - 2n 4\text{f(n) = f(n-2) + n-2 f(n) = f(n-4) + (n-2) + (n-4) f(n) = i=1 n/2 n - 2i f(n even ) = n 2 - 2n 4}
Now obtain the closed form when nn is odd by using the previous result for when nn is even: f(n) = f(n-1) + n-1 2 f(n) = (n-1) 2 - 2(n-1) 4 + n-1 2 f(n odd ) = (n-1) 2 4\text{f(n) = f(n-1) + n-1 2 f(n) = (n-1) 2 - 2(n-1) 4 + n-1 2 f(n odd ) = (n-1) 2 4}
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: f(n even ) = n 2 - 2n 2 f(n odd ) = (n-1) 2 2 f(n) = (n-1) 2 2\text{f(n even ) = n 2 - 2n 2 f(n odd ) = (n-1) 2 2 f(n) = (n-1) 2 2}
~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 reproduced verbatim; metadata (topic, difficulty) added by this project.