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.