Difference between revisions of "1980 USAMO Problems/Problem 2"
m (→Solution) |
m (→Solution) |
||
| Line 18: | Line 18: | ||
<cmath>f(n) = f(n-4) + (n-2) + (n-4)</cmath> | <cmath>f(n) = f(n-4) + (n-2) + (n-4)</cmath> | ||
<cmath>f(n) = \sum_{i=1}^{n/2} n - 2i</cmath> | <cmath>f(n) = \sum_{i=1}^{n/2} n - 2i</cmath> | ||
| − | <cmath>\boxed{f(n \text{odd}) = frac{n^2 - 2n}{4}}</cmath> | + | <cmath>\boxed{f(n \text{ odd}) = frac{n^2 - 2n}{4}}</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}{2}</cmath> | <cmath>f(n) = f(n-1) + \frac{n-1}{2}</cmath> | ||
<cmath>f(n) = \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2}</cmath> | <cmath>f(n) = \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2}</cmath> | ||
| − | <cmath>\boxed{ f(n \text{even) = \frac{{(n-1)}^2}{4}}</cmath> | + | <cmath>\boxed{ f(n \text{ even}) = \frac{{(n-1)}^2}{4}}</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>\boxed{f(n \text{even}) = \frac{n^2 - 2n}{2}}</cmath> | + | <cmath>\boxed{f(n \text{ even}) = \frac{n^2 - 2n}{2}}</cmath> |
| − | <cmath>\boxed{f(n \text{odd}) = \frac{{(n-1)}^2}{2}}</cmath> | + | <cmath>\boxed{f(n \text{ odd}) = \frac{{(n-1)}^2}{2}}</cmath> |
~Lopkiloinm | ~Lopkiloinm | ||
Revision as of 09:50, 26 March 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/0/1/d/01d761c5f729a726f3086d13acffddee108056a3.png)
If is odd, ![\[f(n) = f(n-1) + \frac{n-1}{2}\]](http://latex.artofproblemsolving.com/0/6/7/06760ca4598cd8541cbec20789ad185a56692c8f.png)
Let's obtain the closed form for when is even:
![\[f(n) = f(n-2) + n-2\]](http://latex.artofproblemsolving.com/6/7/f/67feb5431f2c2745d698dcede538d049e80bf34f.png)
![\[f(n) = f(n-4) + (n-2) + (n-4)\]](http://latex.artofproblemsolving.com/7/6/8/768d4bffcaac2edbce6967bb8ec2f222575f3979.png)
![\[f(n) = \sum_{i=1}^{n/2} n - 2i\]](http://latex.artofproblemsolving.com/a/c/6/ac60cf94e01a620b03c889893e03d317ee33cdc2.png)
![\[\boxed{f(n \text{ odd}) = frac{n^2 - 2n}{4}}\]](http://latex.artofproblemsolving.com/5/e/e/5eefbd37ef637a898505ea00bac5dfb2743baa64.png)
Now obtain the closed form when is odd by using the previous result for when is even
![\[f(n) = \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2}\]](http://latex.artofproblemsolving.com/4/e/f/4efe1b7415da9c1dc541f58f54b6e139fd7c212f.png)
![\[\boxed{ f(n \text{ even}) = \frac{{(n-1)}^2}{4}}\]](http://latex.artofproblemsolving.com/3/3/a/33a737075127657556926ac55298ad6f9957d048.png)
- 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:
![\[\boxed{f(n \text{ even}) = \frac{n^2 - 2n}{2}}\]](http://latex.artofproblemsolving.com/1/8/2/18250a11d0087e440f03e5a44f9260da68cad63d.png)
![\[\boxed{f(n \text{ odd}) = \frac{{(n-1)}^2}{2}}\]](http://latex.artofproblemsolving.com/6/8/6/68664d10a8dadeb0b18c5896575b8d0e91120395.png)
~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. 
