The largest possible number of inversions in a sequence of positive integers whose sum is $2014$

Question

In a sequence of positive integers an inversion is a pair of positions such that the element in the position to the left is greater than the element in the position to the right. For instance the sequence $2,5,3,1,3$ has five inversions - between the first and fourth positions, the second and all later positions, and between the third and fourth positions. What is the largest possible number of inversions in a sequence of positive integers whose sum is $2014$?

I tried this question and I came under one construction.

$62,61,\dots,3,2,1\dots 1(61~~1's)$

The sum is $62+\cdots +1+ 61=2014.$

And we get $122+121+\dots 62=61\times 61+(1+2+\dots +61)=3721+1891=5612$ inversions.

Then I also got one more construction by expanding "62."

So we get $61,60,\dots ,2,1( 123~1's)$

Now we get $182+181+\dots 123=122\times 60+60\times 61/2=9150$ inversions.

Then we can again continue expanding the numbers to 1's.

I don't think this is a nice way. Any solution?

Answer 1

We can work only with the multiset since it should be ordered decreasing.

We show that if a multiset contains max element $a>2$ we can replace $a$ with $a-1$ and $1$ and not decrease the number of inversions.

Every inversion $a,x$ still remains ( it gets converted into an inversion $a-1,x$ except for the inversions $a,a-1$, however the inversions $a,a-1$ are "covered" by the inversions $a-1,1$ so the number of inversions does not decrease.

Hence we can work only with sequences that only have $1$ and $2$, and then if $t$ is the number of twos we have to maximize $t(2014-2t)$ which can be done in various ways, for example analyzing the derivative. We find the best value is $t = 503,504$ and yields $507024$.