Difference between revisions of "2001 IMO Shortlist Problems/C1"
(→Solution) |
(→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
+ | ===Solution 1=== | ||
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: | 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: | ||
Line 13: | Line 14: | ||
QED | 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> |
Latest revision as of 12:45, 27 November 2017
Contents
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
Solution 1
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
Solution 2
We claim that is the maximum. First, we show that
is achievable. Consider the sequence where
for
,
for
, and
for
. Any subsequence satisfying the condition must be equal to
; there are 667 ways to select each element to fill that, and every possible selection has indexes in increasing order, resulting in
subsequences.
Now we show no higher is allowed. Let
, for
. We see that the elements of any subsequence
that satisfies the condition must leave different residues mod 3, which means the indexes must be in different
. Thus, the number of ways to choose a suitable subsequence is at most the number of ways of selecting one element out of each
(and ordering them at most one way -- strictly increasing), which is
. By AM-GM,