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 \leq i < j < k \leq 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\).
Okay, so my first thought is that surely it is beneficial for everything to be in inreasing order. Indeed, considering the smallest element, it can only contribute more if placed at the very start, and similarly we can continue this process and arrange everything in order. Now we basically have something of an algebra problem (which is the best kind of reduction for a combinatorics problem), and it is optimal to assume that we've divided everything into slots of numbers with two consecutive slots having consecutive numbers. So \(b_1 + b_2 + \dots + b_r = 2001\) and the total number that we want to maximize is \[b_1 b_2 b_3 + b_2 b_3 b_4 + \dots + b_{r-2} b_{r-1} b_r\] So the natural thing to do here is smooth, but we don't know what the equality case we want to achieve is, which is quite unfortunate. Actually, I just realized that the thing I want to figure out first is what value of \(r\) is optimal. It is likely true that after choosing a particular \(r\), the split of \(2001\) is equal among slots, so I'll just run some calculations. Indeed, it seems that \(r = 3\) is optimal, so we should work towards sending \(b_i \to 0\) where \(i > 3\).
Because \(r\) is a large number, let me take \(r = 4\) first and try to smooth \(b_4\) out of existence. \[b_1 b_2 b_3 + b_2 b_3 b_4\] Okay wait this is a pretty bad small case because we can just do \(b_4 \to 0\) and \(b_1 \to b_1 + b_4\) and the sum remains invariant. Let's look at \(r = 5\) then, \[b_1 b_2 b_3 + b_2 b_3 b_4 + b_3 b_4 b_5\] We can just do the same thing here. Oh wait, I see it now - basically we smooth \(b_r\) out of existence by giving it to \(b_{r-3}\) and keeping the sum invariant, and this reduces the \(r\) case to the \(r - 1\) case, up till we reach \(r = 3\). Now all we want to do is maximize \(b_1b_2 b_3\) for \(b_1 + b_2 + b_3 = 2001\) but this is just \((2001/3)^3\).