Difference between revisions of "1980 USAMO Problems/Problem 2"
Lopkiloinm (talk | contribs) (→Solution) |
|||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | {{ | + | |
| + | Consider the first few cases for <cmath>n</cmath> with the entire <cmath>n</cmath> numbers forming an arithmetic sequence <cmath>(1, 2, 3, \ldots, n)</cmath> | ||
| + | If <cmath>n = 3</cmath>, there will be one ascending triplet (123). Let's only consider the ascending order for now. | ||
| + | If <cmath>n = 4</cmath>, the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total. | ||
| + | If <cmath>n = 5</cmath>, 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 <cmath>n</cmath> is even, the nth number will give <cmath>\frac{n}{2} - 1</cmath> more triplets in addition to all the prior triplets from the first <cmath>n-1</cmath> numbers. | ||
| + | If <cmath>n</cmath> is odd, the <cmath>n</cmath>th number will give <cmath>\frac{n-1}{2}</cmath> more triplets. | ||
| + | Let f(n) denote the total number of triplets for <cmath>n</cmath> numbers. The above two statements are summarized as follows: | ||
| + | <cmath>f(n) = f(n-1) + \frac{n}{2} - 1</cmath> if <cmath>n</cmath> is even, | ||
| + | <cmath>f(n) = f(n-1) + \frac{n-1}{2}</cmath> if <cmath>n</cmath> is odd. | ||
| + | |||
| + | Let's obtain the closed form for when <cmath>n</cmath> is even: | ||
| + | <cmath>f(n) = f(n-2) + n-2</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) = \frac{n^2 - 2n}{4}</cmath> | ||
| + | |||
| + | Now obtain the closed form when <cmath>n</cmath> is odd by using the previous result for when <cmath>n</cmath> is even | ||
| + | <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} = \frac{{(n-1)}^2}{4}</cmath> | ||
| + | |||
| + | We need to double the expression to account for the descending versions of each triple, to obtain: | ||
| + | <cmath>f(n) = \frac{n^2 - 2n}{2}</cmath> if <cmath>n</cmath> is even and | ||
| + | <cmath>f(n) = \frac{{(n-1)}^2}{4}</cmath> if <cmath>n</cmath> is odd. ~Lopkiloinm | ||
== See Also == | == See Also == | ||
Revision as of 23:44, 12 July 2020
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 ![\[n\]](http://latex.artofproblemsolving.com/5/9/c/59c0a8515f4a35b69d5e6da2b371feb9e7dd5f0a.png)
with the entire numbers forming an arithmetic sequence ![\[(1, 2, 3, \ldots, n)\]](http://latex.artofproblemsolving.com/7/9/8/798966f1e72a24eebf5771150f20ad02897ea691.png)
If ![\[n = 3\]](http://latex.artofproblemsolving.com/8/c/9/8c975adfab4d0ce5ec80e5e0096d45509ce7da9e.png)
, there will be one ascending triplet (123). Let's only consider the ascending order for now.
If ![\[n = 4\]](http://latex.artofproblemsolving.com/4/d/4/4d4f6a32c9ea72c9bef5850247bedfc923136174.png)
, the first 3 numbers give 1 triplet, the addition of the 4 gives one more, for 2 in total.
If ![\[n = 5\]](http://latex.artofproblemsolving.com/9/9/8/9987073b195bd588fd170ce3c6bf4e8bae71a6a4.png)
, 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 ![\[n-1\]](http://latex.artofproblemsolving.com/7/a/c/7acc22f378d383c22b357219b8bf7b4276f38322.png)
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 f(n) denote the total number of triplets for numbers. The above two statements are summarized as follows:
![\[f(n) = f(n-1) + \frac{n}{2} - 1\]](http://latex.artofproblemsolving.com/0/1/d/01d761c5f729a726f3086d13acffddee108056a3.png)
if is even,
![\[f(n) = f(n-1) + \frac{n-1}{2}\]](http://latex.artofproblemsolving.com/0/6/7/06760ca4598cd8541cbec20789ad185a56692c8f.png)
if is odd.
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)
![\[f(n) = \frac{n^2 - 2n}{4}\]](http://latex.artofproblemsolving.com/2/d/b/2dbbef0623990c3f6db362264ecb5b152fae5dc9.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} = \frac{{(n-1)}^2}{4}\]](http://latex.artofproblemsolving.com/2/e/7/2e71f047c7b9692525153318490ee2dc5b741039.png)
We need to double the expression to account for the descending versions of each triple, to obtain:
![\[f(n) = \frac{n^2 - 2n}{2}\]](http://latex.artofproblemsolving.com/8/a/9/8a9a1f2c27275a262e0aff416ccf8a62efc4c7de.png)
if is even and
![\[f(n) = \frac{{(n-1)}^2}{4}\]](http://latex.artofproblemsolving.com/f/5/6/f567cd806ac09cb7f361afbca69e28bf1c01d314.png)
if is odd. ~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. 
