Art of Problem Solving
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

1980 USAMO Problems/Problem 2: Difference between revisions

← Older edit
Oinava (talk | contribs)
editor
538 edits
Cooljoseph (talk | contribs)
editor
40 edits
Added Solution 2
 
(6 intermediate revisions by 2 users not shown)
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:
<cmath>f(n) = f(n-2) + n-2</cmath>
<cmath>\begin{align*}
<cmath>f(n) = f(n-4) + (n-2) + (n-4)</cmath>
f(n) &= f(n-2) + n-2\\
<cmath>f(n) = \sum_{i=1}^{n/2} n - 2i</cmath>
f(n) &= f(n-4) + (n-2) + (n-4)\\
<cmath>\boxed{f(n   \text{odd}) = frac{n^2 - 2n}{4}}</cmath>
f(n) &= \sum_{i=1}^{n/2} n - 2i\\
\Aboxed{f(n\ \text{even}) &= \frac{n^2 - 2n}4}
\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>f(n) = f(n-1) + \frac{n-1}{2}</cmath>
<cmath>\begin{align*}
<cmath>f(n) = \frac{{(n-1)}^2 - 2(n-1)}{4} + \frac{n-1}{2}</cmath>
f(n) &= f(n-1) + \frac{n-1}2\\
\boxed{ f(n \text{even) = \frac{{(n-1)}^2}{4}}<cmath>
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*}</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}}<math></math>
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
~Lopkiloinm (corrected by integralarefun)
 
== Solution 2 ==
Unlike in the previous solution, I am interpreting "arithmetic progressions" to be in the same direction as the monotone sequence of real numbers. So, for example, if the sequence of reals is <math>1 < 4 < 5 < 6</math>, then <math>(4, 5, 6)</math> counts but <math>(6, 5, 4)</math> doesn't.
 
The first solution proves that there is a sequence with <math>\lfloor (n - 1)^2 / 4 \rfloor</math> such arithmetic progressions. In this solution, I prove that this is in fact the upper bound.
 
Count the arithmetic progressions by their center values. Let <math>x_k</math> be the <math>k</math>th greatest number. The number <math>x_k</math> is the center of at most <math>\min(k - 1, n - k)</math> arithmetic progressions, because any such progression includes a number less than <math>x_k</math> and a number greater than <math>x_k</math>. There are <math>k - 1</math> numbers less than <math>x_k</math> and <math>n - k</math> numbers greater than <math>x_k</math>, and none of these can be in two separate arithmetic progressions with the same middle term <math>x_k</math>.
 
Thus, the total number of arithmetic progressions is at most
<cmath>\sum_{k = 1}^n \min(k - 1, n - k).</cmath>
This equals
<cmath>1 + 2 + \cdots + \frac{n - 3}{2} + \frac{n - 1}{2} + \frac{n - 3}{2} + \cdots + 2 + 1 = \frac{(n - 1)^2}{4}</cmath>
if <math>n</math> is odd, and
<cmath>1 + 2 + \cdots + \frac{n-2}{2} + \frac n2 + \frac n2 + \frac{n-2}{2} + \cdots + 2 + 1 = \frac{(n - 1)^2 - 1}{4}</cmath>
if <math>n</math> is even. This can be summarized as
<cmath>\left\lfloor \frac{(n - 1)^2}{4} \right\rfloor.</cmath>


== See Also ==
== See Also ==

Latest revision as of 02:39, 18 October 2025

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)

Solution 2

Unlike in the previous solution, I am interpreting "arithmetic progressions" to be in the same direction as the monotone sequence of real numbers. So, for example, if the sequence of reals is $1 < 4 < 5 < 6$, then $(4, 5, 6)$ counts but $(6, 5, 4)$ doesn't.

The first solution proves that there is a sequence with $\lfloor (n - 1)^2 / 4 \rfloor$ such arithmetic progressions. In this solution, I prove that this is in fact the upper bound.

Count the arithmetic progressions by their center values. Let $x_k$ be the $k$th greatest number. The number $x_k$ is the center of at most $\min(k - 1, n - k)$ arithmetic progressions, because any such progression includes a number less than $x_k$ and a number greater than $x_k$. There are $k - 1$ numbers less than $x_k$ and $n - k$ numbers greater than $x_k$, and none of these can be in two separate arithmetic progressions with the same middle term $x_k$.

Thus, the total number of arithmetic progressions is at most \[\sum_{k = 1}^n \min(k - 1, n - k).\] This equals \[1 + 2 + \cdots + \frac{n - 3}{2} + \frac{n - 1}{2} + \frac{n - 3}{2} + \cdots + 2 + 1 = \frac{(n - 1)^2}{4}\] if $n$ is odd, and \[1 + 2 + \cdots + \frac{n-2}{2} + \frac n2 + \frac n2 + \frac{n-2}{2} + \cdots + 2 + 1 = \frac{(n - 1)^2 - 1}{4}\] if $n$ is even. This can be summarized as \[\left\lfloor \frac{(n - 1)^2}{4} \right\rfloor.\]

See Also

1980 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

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