1980 USAMO Problems/Problem 2
Problem
Find the maximum possible number of three term arithmetic progressions in a monotone sequence of distinct reals.
Solution
Consider the first few cases for with the entire
numbers forming an arithmetic sequence
If
, there will be one ascending triplet (123). Let's only consider the ascending order for now.
If
, the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total.
If
, 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
is even, the nth number will give
more triplets in addition to all the prior triplets from the first
numbers.
If
is odd, the
th number will give
more triplets.
Let
denote the total number of triplets for
numbers. The above two statements are summarized as follows:
If
is even,
If
is odd,
Let's obtain the closed form for when is even:
Now obtain the closed form when is odd by using the previous result for when
is even
- 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:
~Lopkiloinm
See Also
1980 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.