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}{2} - 1</cmath>
+
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}{2}</cmath>  
+
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}{4}
+
\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}{2}\
+
f(n) &= f(n-1) + \frac{n-1}2\
f(n) &= \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2}\
+
f(n) &= \frac{{(n-1)}^2 - 2(n-1)}4 + \frac{n-1}2\
f(n\ \text{odd}) &= \frac{{(n-1)}^2}{4}
+
\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>\boxed{f(n\ \text{even}) = \frac{n^2 - 2n}{2}}</cmath>
+
<cmath>\begin{align*}
<cmath>\boxed{f(n\ \text{odd}) = \frac{{(n-1)}^2}{2}}</cmath>
+
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 18:04, 9 August 2023

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: \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*}

Now obtain the closed form when $n$ is odd by using the previous result for when $n$ is even: \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*}

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: \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*}

~Lopkiloinm (corrected by integralarefun)

See Also

1980 USAMO (ProblemsResources)
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