# Positive integer sequence with sum $m$ can have at most $\left\lfloor\dfrac{m^2}{8}\right\rfloor$ increasing pairs

Let $$a_1,\cdots,a_n$$ be a sequence of positive integers such that

$$\bullet$$ $$a_1+\cdots+a_n=m$$;

$$\bullet$$ The number of pairs $$(i,j)$$ such that $$i and $$a_i is $$k$$.

Must we have $$k\le \dfrac{m^2}{8}?$$

The relation $$k\le \dfrac{m^2}{8}$$ is based on the following two observations:

Observation 1. If $$a_1,\cdots,a_n$$ consists of only $$1$$'s and $$2$$'s, then we have $$k\le \dfrac{m^2}{8}$$, and the result is optimal.

Proof. WLOG we can suppose that the last term in the sequence is $$2$$. Suppose that there are $$t$$ $$2$$'s, and the number of $$1$$'s to the left of each $$2$$ is $$b_1,\cdots,b_t$$, then $$b_1\le \cdots\le b_t,\quad m=b_t+2t,\quad k=b_1+\cdots+b_t.$$ We then have $$k\le tb_t\le\dfrac{(b_t+2t)^2}{8}=\dfrac{m^2}{8}$$. Moreover, it is possible that $$k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$$: Let $$t$$ be the integer closest to $$\dfrac{m}{4}$$ (choose either one in case of a tie), and $$b_1=\cdots=b_t = m-2t,$$ which means that we pick the sequence consisting of $$m-2t$$ $$1$$'s followed by $$t$$ $$2$$'s. Then we have $$k=t(m-2t)$$, and we see that \begin{align*} m\equiv 0\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m}{4}\Rightarrow k=\dfrac{m^2}{8};\\ m\equiv 1\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m-1}{4}\Rightarrow k=\dfrac{m^2-1}{8};\\ m\equiv 2\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m-2}{4}\text{ or }\dfrac{m+2}{4}\Rightarrow k=\dfrac{m^2-4}{8};\\ m\equiv 3\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m+1}{4}\Rightarrow k=\dfrac{m^2-1}{8}, \end{align*} so $$k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$$ in this case.

Note 1.1. We can see that $$k=0,\cdots,\left\lfloor\dfrac{m^2}{8}\right\rfloor$$ are all possible because a nonincreasing sequence corresponds to $$k=0$$, and swapping two adjacent entries in a sequence would leave $$m$$ unchanged, but $$k$$ changed by $$0$$ or $$\pm 1$$.

Note 1.2. The construction above gives the only optimal solutions. Indeed, if $$k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$$, then $$t(m-2t)=tb_t\ge k=\left\lfloor\dfrac{m^2}{8}\right\rfloor\Rightarrow \left|t-\dfrac{m}{4}\right|\le\dfrac{1}{2}, k=tb_t\text{ (hence }b_1=\cdots=b_t).$$

Observation 2. If $$a_1,\cdots,a_n$$ is nondecreasing, then $$k\le\dfrac{m^2}{8}$$, and the result is also optimal.

Proof. Suppose that each of $$1,2,\cdots$$ occurs $$c_1,c_2,\cdots$$ times in the sequence, where $$c_i\neq 0$$ for finitely many $$i$$, then $$m=c_1+2c_2+\cdots,\quad k=\sum_{i so we have $$m^2 - 8k = (c_1 - 2c_2 - c_3)^2 + 8c_3^2 + \sum^{\infty}_{i=4}i^2c_i^2+\sum_{\max\{i,j\}\ge 4,i\neq j}(ij-4)c_ic_j\ge 0.$$ The result $$k\le\dfrac{m^2}{8}$$ for nondecreasing sequences is also optimal as shown by the $$1-2$$ sequences above.

Note 2.1. If the equality holds, then we must have $$c_3=c_4=\cdots=0$$, otherwise we would have $$m^2-8k\ge 8c_i^2\ge 8$$.

I don't have any idea for the general case. I guess that if $$k$$ attains its maximum with $$m$$ fixed, then $$a_1,\cdots,a_n$$ must consist of only $$1$$'s and $$2$$'s, but I don't know how to prove it. Any help appreciated.

Edit. This question turns out to be trivial. For a general sequence, we apply the process of bubble sort. At each step either we do nothing, either we create a new increasing pair, so $$k$$ reaches its maximum when and only when the sequence is nondecreasing, and the result $$k\le\dfrac{m^2}{8}$$ follows from Observation 2 above.

• I'm a bit confused about what exactly you're asking. Are you only interested in the last point in bold? Commented Apr 5 at 13:49
• For your note 1.1, you seem to be requiring $i < j$ with $a_i < a_j$. However, that is not stated in your conditions. Commented Apr 5 at 14:07
• Given that, it seems to me that you have all of the elements of the proof (and my proof follows along your lines, with a slightly different approach to Observation 2). If you can clarify what your confusion is about, we might be able to help clean it up. Commented Apr 5 at 14:17
• It seems to work for $n=3$. Commented Apr 5 at 14:27
• @CalvinLin Yes, my bad. This question turns out to be trivial. Thanks for working on it anyway! Commented Apr 5 at 16:06

As I pointed out in the comments,

• the order of the sequence $$a_i$$ doesn't matter. Any rearrangement of them will lead to the same number of (unordered) pairs $$(a_i, a_j)$$
• I believe that OP has all of the elements required for the proof. As such, this solution can be considered a restatement/refinement of what they presented.

Let's rephrase the question slightly (which OP did in observation 2), which will make this much easier to approach:

Given $$a_i$$ a squence of positive integers that sum to $$m$$, let there be $$b_1$$ 1's, $$b_2$$ 2's, etc up to $$b_n$$ n's (the max of the positive integers), so $$\sum i b_i = m$$.
Show that $$\sum_{i\neq j} b_i b_ j \leq \frac{m^2 }{ 8}$$.

Consider a sequence of $$b_i$$ that maximizes $$\sum b_i b_j$$.
Show that it must have the following properties.

1. There are at least 2 non-zero values.
2. $$b_i$$ is a non-increasing sequence.
3. $$b_3 = b_4 = \ldots = b_n = 0$$.

In particular, if $$b_3 \neq 0$$, show that $$b_1^* = b_1 + b_3, b_2^* = b_2 + b_3, b_3^* = 0, b_i ^* = b_i$$ would increase the summation.

1. $$b_1 b_2 \leq \frac{m^2}{8}$$.

Hence the desired result is true.