Difference between revisions of "1980 USAMO Problems/Problem 2"
(→Solution: flip-flop correction) |
(→Solution: I didn't know AoPS supported `\Aboxed`!) |
||
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: | ||
Line 19: | Line 19: | ||
f(n) &= f(n-4) + (n-2) + (n-4)\\ | f(n) &= f(n-4) + (n-2) + (n-4)\\ | ||
f(n) &= \sum_{i=1}^{n/2} n - 2i\\ | f(n) &= \sum_{i=1}^{n/2} n - 2i\\ | ||
− | f(n\ \text{even}) &= \frac{n^2 - 2n} | + | \Aboxed{f(n\ \text{even}) &= \frac{n^2 - 2n}4} |
\end{align*}</cmath> | \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>\begin{align*} | <cmath>\begin{align*} | ||
− | f(n) &= f(n-1) + \frac{n-1} | + | f(n) &= f(n-1) + \frac{n-1}2\\ |
− | f(n) &= \frac{{(n-1)}^2 - 2(n-1)} | + | f(n) &= \frac{{(n-1)}^2 - 2(n-1)}4 + \frac{n-1}2\\ |
− | f(n\ \text{odd}) &= \frac{{(n-1)}^2} | + | \Aboxed{f(n\ \text{odd}) &= \frac{{(n-1)}^2}4} |
\end{align*}</cmath> | \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 (corrected by integralarefun) | ~Lopkiloinm (corrected by integralarefun) |
Latest revision as of 19: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
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 (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.