Suma de la diferencia de los números en un arreglo de los números $0,1,2,\cdots, n$

Question

Se me ha ocurrido un problema aparentemente interesante (¿fácil?) y he pensado que estaría bien pediros vuestra opinión al respecto.

Supongamos que vamos a ordenar los números $0$ a $n$ en una fila de tal manera que la suma de la diferencia entre los números adyacentes sea máxima. ¿Cómo podríamos conseguirlo? ¿Cómo podríamos determinar la suma máxima de la diferencia? ¿Y el mínimo?

Como ejemplo, tomemos los números $0,1,2,3,4$ . Veamos algunos arreglos:

$0,1,2,3,4$ la diferencia entre los números adyacentes son $1,1,1,1$ por lo que la suma es $4$

$1,3,4,0,2$ la diferencia entre los números adyacentes son $2,1,4,2$ por lo que la suma es $9$

$1,4,0,3,2$ la diferencia entre los números adyacentes son $3,4,3,1$ por lo que la suma es $11$

$3,0,4,1,2$ la diferencia entre los números adyacentes son $3,4,3,1$ por lo que la suma es $11$

Me imaginé que el acuerdo que nos dará la suma mínima es el acuerdo $1,2,3,...,n$ porque toda la diferencia sería simplemente $1$ y su suma es $n-1$ .

Creo que la suma máxima se puede alcanzar disponiendo los números de la siguiente manera:

Coloque el número $n$ entre $0$ y $1$ . A continuación, coloque $n-1$ al lado de $0$ y $n-2$ junto a $1$ y así sucesivamente.

Una pregunta adicional, si ya conocemos el mínimo y el máximo ¿sería posible obtener siempre un arreglo que dé una suma para todos los valores entre el mínimo y el máximo? Lo he intentado con $0,1,2,3$ y pude encontrar arreglos para todos los valores entre $3$ y $7$ .

Tal vez este problema se haya planteado antes pero no lo encuentro en la red. ¿Alguna idea? Gracias.

Answer 1

Tengo una idea de cómo obtener un límite superior que parece ser bueno. Tenemos que estimar desde arriba la suma $S=\sum_{i=1}^n |a_i-a_{i-1}|$ donde la secuencia $a_0,\dots, a_n$ es una permutación de la secuencia $0,1,\dots,n$ . Cuando abrimos los módulos en la expresión para $S$ obtenemos $S=\sum_{i=0}^n\varepsilon_i a_i$ , donde $\sum_{i=0}^n\varepsilon_i=0$ y $\varepsilon_i\in\{-1,1\}$ para $i=0$ o $i=n$ y $\varepsilon_i\in\{-2,0,2\}$ para $1\le i\le n-1$ . Supongamos que $n=2k+1$ es impar. Ahora parece ser cierto y fácilmente demostrable que $S$ tienen el máximo $(n-1)^2/2-1$ cuando el $\varepsilon$ -coeficientes en los números $0,1,\dots,k-1$ son "-2", en $k+2,k+3,\dots,n$ son "2", en $k$ es "-1" y en $k+1$ es "1". El caso cuando $n$ es incluso puede ser considerado de manera similar.