Difference between revisions of "2001 IMO Shortlist Problems/C1"
(→Problem) |
|||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | + | 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: | |
− | < | + | |
− | [[ | + | <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 17:00, 17 August 2008
Problem
Let be a sequence of positive integers. Let
be the number of 3-element subsequences
with
such that
and
. Considering all such sequences
find the greatest value of
.
Solution
Consider what happens if is ordered from least to greatest. Then, all the original subsequences will still be subsequences because, since
, the order they appear in is
, 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
and there be n blocks. Cases:
: 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.
: Note that the number of subsequences is
. WLOG,
. 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
elements, and there would only be n - 1 blocks. Note that the number of 3-element subsequences
with
such that
and
would increase by
. 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.
: So we have three nonegative integers x, y, z such that
and we want to maximize xyz. By AM-GM, xyz is maximal when x = y = z = 667, so m =
.
QED
Pythag011 21:00, 17 August 2008 (UTC)