Difference between revisions of "2001 IMO Shortlist Problems/C1"

Latest revision as of 11:45, 27 November 2017

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

Solution 1

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

Solution 2

We claim that $m=667^3$ is the maximum. First, we show that $667^3$ is achievable. Consider the sequence where $a_i=1$ for $1\le i\le 667$ , $a_i=2$ for $668\le i\le 1334$ , and $a_i=3$ for $1335\le i\le 2001$ . Any subsequence satisfying the condition must be equal to $(1,2,3)$ ; there are 667 ways to select each element to fill that, and every possible selection has indexes in increasing order, resulting in $667^3$ subsequences.

Now we show no higher $m$ is allowed. Let $A_i=\{k\in A\mid a_k\equiv i\pmod{3}\}$ , for $i=0,1,2$ . We see that the elements of any subsequence $(a_i,a_j,a_k)$ that satisfies the condition must leave different residues mod 3, which means the indexes must be in different $A_i$ . Thus, the number of ways to choose a suitable subsequence is at most the number of ways of selecting one element out of each $A_i$ (and ordering them at most one way -- strictly increasing), which is $|A_0|\cdot |A_1|\cdot |A_2|$ . By AM-GM, $m\le |A_0|\cdot |A_1|\cdot |A_2|\le \left(\frac{|A_0|+|A_1|+|A_2|}{3}\right)^3=\left(\frac{2001}{3}\right)^3=667^3.$

$\blacksquare$

@@ Line 1: / Line 1: @@
 ==Problem==
-''Let <math>A = (a_1, a_2, \ldots, a_{2001})</math> be a sequence of positive integers. Let <math>m</math> be 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>. Considering all such sequences <math>A</math> find the greatest value of <math>m</math>''
+''Let <math>A = (a_1, a_2, \ldots, a_{2001})</math> be a sequence of positive integers. Let <math>m</math> be 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>. Considering all such sequences <math>A</math> find the greatest value of <math>m</math>.''
 ==Solution==
+===Solution 1===
-''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
+=== Solution 2 ===
+We claim that <math>m=667^3</math> is the maximum. First, we show that <math>667^3</math> is achievable. Consider the sequence where <math>a_i=1</math> for <math>1\le i\le 667</math>, <math>a_i=2</math> for <math>668\le i\le 1334</math>, and <math>a_i=3</math> for <math>1335\le i\le 2001</math>. Any subsequence satisfying the condition must be equal to <math>(1,2,3)</math>; there are 667 ways to select each element to fill that, and every possible selection has indexes in increasing order, resulting in <math>667^3</math> subsequences.
+Now we show no higher <math>m</math> is allowed. Let <math>A_i=\{k\in A\mid a_k\equiv i\pmod{3}\}</math>, for <math>i=0,1,2</math>. We see that the elements of any subsequence <math>(a_i,a_j,a_k)</math> that satisfies the condition must leave different residues mod 3, which means the indexes must be in different <math>A_i</math>. Thus, the number of ways to choose a suitable subsequence is at most the number of ways of selecting one element out of each <math>A_i</math> (and ordering them at most one way -- strictly increasing), which is <math>|A_0|\cdot |A_1|\cdot |A_2|</math>. By AM-GM, <cmath>m\le |A_0|\cdot |A_1|\cdot |A_2|\le \left(\frac{|A_0|+|A_1|+|A_2|}{3}\right)^3=\left(\frac{2001}{3}\right)^3=667^3.</cmath>
+<math>\blacksquare</math>

Page

Toolbox

Search