2001 IMO Shortlist Problems/C1

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

Page

Toolbox

Search

2001 IMO Shortlist Problems/C1

Problem

Solution