1980 USAMO Problems/Problem 2

Problem

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

Solution

Consider the first few cases for $n$ with the entire $n$ numbers forming an arithmetic sequence $(1, 2, 3, \ldots, n)$ If $n = 3$ , there will be one ascending triplet (123). Let's only consider the ascending order for now. If $n = 4$ , the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total. If $n = 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 $n$ is even, the nth number will give $\frac{n}{2} - 1$ more triplets in addition to all the prior triplets from the first $n-1$ numbers. If $n$ is odd, the $n$ th number will give $\frac{n-1}{2}$ more triplets. Let f(n) denote the total number of triplets for $n$ numbers. The above two statements are summarized as follows: $f(n) = f(n-1) + \frac{n}{2} - 1$ if $n$ is even, $f(n) = f(n-1) + \frac{n-1}{2}$ if $n$ is odd.

Let's obtain the closed form for when $n$ is even: $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$ $f(n) = \frac{n^2 - 2n}{4}$

Now obtain the closed form when $n$ is odd by using the previous result for when $n$ is even $f(n) = f(n-1) + \frac{n-1}{2}$ $f(n) = \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2} = \frac{{(n-1)}^2}{4}$

We need to double the expression to account for the descending versions of each triple, to obtain: $f(n) = \frac{n^2 - 2n}{2}$ if $n$ is even and $f(n) = \frac{{(n-1)}^2}{4}$ if $n$ is odd. ~Lopkiloinm

1980 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1980 USAMO Problems/Problem 2

Problem

Solution

See Also