El mayor número posible de inversiones en una secuencia de enteros positivos cuya suma es $2014$

Question

En una secuencia de enteros positivos, una inversión es un par de posiciones tal que el elemento en la posición izquierda es mayor que el elemento en la posición derecha. Por ejemplo, la secuencia $2,5,3,1,3$ tiene cinco inversiones - entre la primera y cuarta posición, la segunda y todas las posiciones posteriores, y entre la tercera y cuarta posición. ¿Cuál es el mayor número posible de inversiones en una secuencia de enteros positivos cuya suma es $2014$?

Intenté esta pregunta y llegué a una construcción.

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

La suma es $62+\cdots +1+ 61=2014$.

Y obtenemos $122+121+\dots 62=61\times 61+(1+2+\dots +61)=3721+1891=5612$ inversiones.

Luego también encontré otra construcción al expandir el "62".

Entonces obtenemos $61,60,\dots ,2,1( 123~1's)$

Ahora obtenemos $182+181+\dots 123=122\times 60+60\times 61/2=9150$ inversiones.

Luego podemos seguir expandiendo los números a 1's.

No creo que esta sea una forma agradable. ¿Alguna solución?

Answer 1

Solo podemos trabajar con el multiconjunto ya que debe estar ordenado decrecientemente.

Mostramos que si un multiconjunto contiene un elemento máximo $a>2$ podemos reemplazar $a$ con $a-1$ y $1$ sin disminuir el número de inversiones.

Cada inversión $a,x$ todavía permanece (se convierte en una inversión $a-1,x$ excepto por las inversiones $a,a-1$, sin embargo las inversiones $a,a-1$ están "cubiertas" por las inversiones $a-1,1$ así que el número de inversiones no disminuye.

Por lo tanto, solo podemos trabajar con secuencias que solo tienen $1$ y $2$, y luego si $t$ es el número de doses que tenemos que maximizar $t(2014-2t)$ lo cual se puede hacer de varias maneras, por ejemplo analizando la derivada. Encontramos que el mejor valor es $t = 503,504$ que da como resultado $507024$.