Difference between revisions of "1980 USAMO Problems/Problem 2"
m (→Solution) |
(→Solution: I didn't know AoPS supported `\Aboxed`!) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 11: | Line 11: | ||
If <math>n</math> is odd, the <math>n</math>th number will give <cmath>\frac{n-1}{2}</cmath> more triplets. | If <math>n</math> is odd, the <math>n</math>th number will give <cmath>\frac{n-1}{2}</cmath> more triplets. | ||
Let <math>f(n)</math> denote the total number of triplets for <math>n</math> numbers. The above two statements are summarized as follows: | Let <math>f(n)</math> denote the total number of triplets for <math>n</math> numbers. The above two statements are summarized as follows: | ||
| − | If <math>n</math> is even, <cmath>f(n) = f(n-1) + \frac{n} | + | If <math>n</math> is even, <cmath>f(n) = f(n-1) + \frac{n}2 - 1</cmath> |
| − | If <math>n</math> is odd, <cmath>f(n) = f(n-1) + \frac{n-1} | + | If <math>n</math> is odd, <cmath>f(n) = f(n-1) + \frac{n-1}2</cmath> |
| − | Let's obtain the closed form for when <math>n</math> is even: | + | Let's obtain the closed form for when <math>n</math> is even: |
| − | <cmath>f(n) = f(n-2) + n-2 | + | <cmath>\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*}</cmath> | ||
| − | Now obtain the closed form when <math>n</math> is odd by using the previous result for when <math>n</math> is even | + | Now obtain the closed form when <math>n</math> is odd by using the previous result for when <math>n</math> is even: |
| − | <cmath>f(n) = f(n-1) + \frac{n-1} | + | <cmath>\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*}</cmath> | ||
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. | 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: | Double the expression to account for the descending versions of each triple, to obtain: | ||
| − | <cmath>\ | + | <cmath>\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*}</cmath> | ||
| − | ~Lopkiloinm | + | ~Lopkiloinm (corrected by integralarefun) |
== See Also == | == See Also == | ||
Latest revision as of 18:04, 9 August 2023
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 ![\[(1, 2, 3, \ldots, n)\]](http://latex.artofproblemsolving.com/7/9/8/798966f1e72a24eebf5771150f20ad02897ea691.png)
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 ![\[\frac{n}{2} - 1\]](http://latex.artofproblemsolving.com/9/4/e/94e9e3faa2cd92adccc8deced5fb59574714d0f9.png)
more triplets in addition to all the prior triplets from the first 
numbers.
If is odd, the th number will give ![\[\frac{n-1}{2}\]](http://latex.artofproblemsolving.com/5/9/5/595d3b6e6b92f60df36c8bc5158d3e196fa48f5b.png)
more triplets.
Let 
denote the total number of triplets for numbers. The above two statements are summarized as follows:
If is even, ![\[f(n) = f(n-1) + \frac{n}2 - 1\]](http://latex.artofproblemsolving.com/6/1/3/61358e9c24aa9a4edb6a684d35fbbd55606fce76.png)
If is odd, ![\[f(n) = f(n-1) + \frac{n-1}2\]](http://latex.artofproblemsolving.com/a/a/a/aaaee09e7c4f32d2314afc7c5f7efd099ddfb9bb.png)
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 (corrected by integralarefun)
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. 
