Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1980 USAMO Problems/Problem 2"

(→‎Solution)
(→‎Solution)
Line 4: Line 4:
 
== 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>
+
Consider the first few cases for <math>n</math> with the entire <math>n</math> 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 <math>n = 3</math>, 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 <math>n = 4</math>, 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).
+
If <math>n = 5</math>, 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.  
+
Repeating a few more times, we can quickly see that if <math>n</math> 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 <math>n-1</math> numbers.  
−
If <cmath>n</cmath> is odd, the <cmath>n</cmath>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 f(n) denote the total number of triplets for <cmath>n</cmath> 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:  
−
<cmath>f(n) = f(n-1) + \frac{n}{2} - 1</cmath> if <cmath>n</cmath> is even,
+
If <math>n</math> is even, <cmath>f(n) = f(n-1) + \frac{n}{2} - 1</cmath>
−
<cmath>f(n) = f(n-1) + \frac{n-1}{2}</cmath> if <cmath>n</cmath> is odd.
+
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 <cmath>n</cmath> is even:  
+
Let's obtain the closed form for when <math>n</math> is even:  
 
<cmath>f(n) = f(n-2) + n-2</cmath>
 
<cmath>f(n) = f(n-2) + n-2</cmath>
 
<cmath>f(n) = f(n-4) + (n-2) + (n-4)</cmath>
 
<cmath>f(n) = f(n-4) + (n-2) + (n-4)</cmath>
Line 20: Line 20:
 
<cmath>f(n) = \frac{n^2 - 2n}{4}</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
+
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} = \frac{{(n-1)}^2}{4}</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:
 
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
+
If <math>n</math> is even, <cmath>\boxed{f(n) = \frac{n^2 - 2n}{2}}</cmath>
−
<cmath>f(n) = \frac{{(n-1)}^2}{4}</cmath> if <cmath>n</cmath> is odd. ~Lopkiloinm
+
If <math>n</math> is odd, <cmath>\boxed{f(n) = \frac{{(n-1)}^2}{2}}</cmath> ~Lopkiloinm
  
 
== See Also ==
 
== See Also ==

Revision as of 00:55, 13 July 2020

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: If $n$ is even, \[f(n) = f(n-1) + \frac{n}{2} - 1\] If $n$ is odd, \[f(n) = f(n-1) + \frac{n-1}{2}\]

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: If $n$ is even, \[\boxed{f(n) = \frac{n^2 - 2n}{2}}\] If $n$ is odd, \[\boxed{f(n) = \frac{{(n-1)}^2}{2}}\] ~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1980_USAMO_Problems/Problem_2&oldid=128192"