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 "2001 IMO Shortlist Problems/C1"

(→‎Problem)
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
−
''This problem needs a solution. If you have a solution for it, please help us out by <span class="plainlinks">[{{fullurl:{{FULLPAGENAME}}|action=edit}} adding it]</span>.''
+
Consider what happens if <math>A</math> is ordered from least to greatest. Then, all the original subsequences will still be subsequences because, since <math>a_k > a_j > a_i</math>, the order they appear in is <math>a_i, a_j, a_k</math>, so it is still a subsequence. So, if A attains the maximal value, so does it unstrictly increasing version. Therefore, we can look at an A such that it is unstrictly increasing and attains the maximal number of such subsequences. Let's divide it into n blocks, such two elements of the sequence have the same value if and only if they belong to the same block. We can do this because it is unstrictly increasing. For example, if the sequence consists of 1000 ones, then 500 twos, then 501 threes, the blocks would be the 1000 ones, the 500 twos, and the 501 threes. Let the number of elements in the ith block be <math>b_i</math> and there be n blocks. Cases:
−
<noinclude>[[Category:Problems with no solution|*]]</noinclude><includeonly>[[Category:Problems with no solution]]</includeonly>
+
 
−
[[Category:Problems with no solution]]
+
<math>n < 3</math>: Then there are no subsequences, because there are only two possible values for each element, and the subsequence must have three elements with distinct values, but by pigeonhole, two of them will have the same value.
 +
 
 +
<math>n > 3</math>: Note that the number of subsequences is <math>b_1b_2b_3 + b_2b_3b_4 + \ldots + b_{n-2}b_{n-1}b_n</math>. WLOG, <math>b_1b_2 \ge b_{n-2}b_{n-1}</math>. Let us say that all the elements in the first block have value m. If we change all of the elements in the n th block to elements with value m, then the first block would have <math>b_1 + b_n</math> elements, and there would only be n - 1 blocks. Note that the number of 3-element subsequences <math>(a_i, a_j, a_k)</math> with <math>1 \le i < j < k \le 2001</math> such that <math>a_j = a_i + 1</math> and <math>a_k = a_j + 1</math> would increase by <math>b_n(b_2b_3 - b_{n-2}b_{n-3}) \ge 0</math>. We repeatedly do this until there are 3 blocks, and at that time there will be at least as many subsequences as there were originally.
 +
 
 +
<math>n = 3</math>: So we have three nonegative integers x, y, z such that <math>x + y + z = 2001</math> and we want to maximize xyz. By AM-GM, xyz is maximal when x = y = z = 667, so m = <math>667^3</math>.
 +
 
 +
QED
 +
 
 +
[[User:Pythag011|Pythag011]] 21:00, 17 August 2008 (UTC)

Revision as of 16:00, 17 August 2008

Problem

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i, a_j, a_k)$ with $1 \le i < j < k \le 2001$ such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$ find the greatest value of $m$.

Solution

Consider what happens if $A$ is ordered from least to greatest. Then, all the original subsequences will still be subsequences because, since $a_k > a_j > a_i$, the order they appear in is $a_i, a_j, a_k$, so it is still a subsequence. So, if A attains the maximal value, so does it unstrictly increasing version. Therefore, we can look at an A such that it is unstrictly increasing and attains the maximal number of such subsequences. Let's divide it into n blocks, such two elements of the sequence have the same value if and only if they belong to the same block. We can do this because it is unstrictly increasing. For example, if the sequence consists of 1000 ones, then 500 twos, then 501 threes, the blocks would be the 1000 ones, the 500 twos, and the 501 threes. Let the number of elements in the ith block be $b_i$ and there be n blocks. Cases:

$n < 3$: Then there are no subsequences, because there are only two possible values for each element, and the subsequence must have three elements with distinct values, but by pigeonhole, two of them will have the same value.

$n > 3$: Note that the number of subsequences is $b_1b_2b_3 + b_2b_3b_4 + \ldots + b_{n-2}b_{n-1}b_n$. WLOG, $b_1b_2 \ge b_{n-2}b_{n-1}$. Let us say that all the elements in the first block have value m. If we change all of the elements in the n th block to elements with value m, then the first block would have $b_1 + b_n$ elements, and there would only be n - 1 blocks. Note that the number of 3-element subsequences $(a_i, a_j, a_k)$ with $1 \le i < j < k \le 2001$ such that $a_j = a_i + 1$ and $a_k = a_j + 1$ would increase by $b_n(b_2b_3 - b_{n-2}b_{n-3}) \ge 0$. We repeatedly do this until there are 3 blocks, and at that time there will be at least as many subsequences as there were originally.

$n = 3$: So we have three nonegative integers x, y, z such that $x + y + z = 2001$ and we want to maximize xyz. By AM-GM, xyz is maximal when x = y = z = 667, so m = $667^3$.

QED

Pythag011 21:00, 17 August 2008 (UTC)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/C1&oldid=27462"