Un interesante problema matemático de concurso: encontrar el valor máximo de $f(a_1,a_2,...,a_n)$

Question

Supongamos que la secuencia $a_1,a_2,...,a_n$ es una permutación de la secuencia $1+2^1,2+2^2,...,n+2^n$ . Encuentre el valor máximo de $f(a_1,a_2,...,a_n)=\vert a_1-a_2\vert+\vert a_2-a_3\vert+\cdots+\vert a_{n-1}-a_n\vert$ .

Este es un interesante problema encontrado en un concurso de matemáticas. En mi época de estudiante de bachillerato me gustaban los concursos de matemáticas. Sé que puedo resolverlo encontrando la posible fórmula regular cuando $n=2,3,4,...$ Pero el método no siempre es efectivo, así que espero que alguien pueda darme alguna pista.

Por cierto, como estudiante especializado en matemáticas ahora, si existe un método avanzado detrás, puede alguien compartirlo conmigo o al menos decirme con qué puede estar relacionado. Gracias por su respuesta.

Answer 1

Usted está pidiendo maximizar

$$\begin{equation}\begin{aligned} f(a_1,a_2,...,a_n) & = \vert a_1-a_2\vert+\vert a_2-a_3\vert+...+\vert a_{n-1}-a_n\vert \\ & = \sum_{i=1}^{n-1}\vert a_{i} - a_{i+1} \vert \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

Si $a_i \ge a_{i+1}$ entonces $\vert a_i - a_{i+1} \vert = a_i - a_{i+1}$ , si no $\vert a_{i} - a_{i+1} \vert = a_{i+1} - a_{i}$ . En cualquier caso, cuando se eliminan los signos de valor absoluto para obtener el valor equivalente correspondiente, se suma un término de la secuencia y se resta otro. Así, sobre el $n - 1$ en términos de valor absoluto, tendría $n - 1$ términos de la secuencia que se añade y $n - 1$ términos de la secuencia que se resta.

Tenga en cuenta que $a_1$ y $a_n$ se utilizan sólo una vez cada uno. También, $a_i$ , para $i \le 2 \le n - 1$ se utilizan dos veces. El valor máximo posible de \eqref {eq1A} se produciría si todos los $n - 1$ Los términos de la secuencia que se añadieron fueron los más grandes y con el $n - 1$ términos de la secuencia que se restan son los más pequeños, y con el caso especial de la $2$ términos de $a_1$ y $a_n$ ya que se utilizan una sola vez, siendo el $2$ términos más grandes entre los que se restan.

Esto se puede hacer. En particular, como se ha dicho anteriormente, hacer que el $2$ "medio" (con unos a cada lado si $n$ es par) estén al principio y al final de la secuencia. Luego en los índices Impares desde el principio, es decir $3,5,7,\ldots$ y los índices pares hacia atrás desde el final, es decir, $n-2,n-4,n-6,\ldots$ , se alterna la colocación de los restantes valores más pequeños desde el más pequeño hacia arriba. Además, en los índices pares desde el principio, es decir, $2,4,6,\ldots$ y los índices Impares de vuelta desde el final, es decir, $n-1,n-3,n-5,\ldots$ , se alterna la colocación de los valores más grandes de mayor a menor.

La "mitad" superior de los valores siempre estará al lado de un valor de la "mitad" inferior de los valores a cada lado de ellos en la expresión en \eqref {eq1A} y, por tanto, los valores de la mitad superior serán los que se sumen y los de la mitad inferior serán los que se resten. Utilizo "la mitad" entre comillas porque el $2$ los que están cerca del medio se manejan especialmente y hay un pequeño problema con impar frente a los valores pares de $n$ a tratar.

Como dices que te gustaban los concursos de matemáticas cuando eras estudiante de bachillerato y ahora te has especializado en matemáticas, confío en que puedas terminar el resto por ti mismo.

Answer 2

Inspirado por la respuesta de John Omielan, aquí está mi intento.

Nuestro objetivo es encontrar el valor máximo de \begin{equation}\begin{aligned} f(a_1,a_2,...,a_n) & = \vert a_1-a_2\vert+\vert a_2-a_3\vert+...+\vert a_{n-1}-a_n\vert \\ & = \sum_{i=1}^{n-1}\vert a_{i} - a_{i+1} \vert \end{aligned}\end{equation}

Podemos considerar $f(a_1,a_2,...,a_n)$ como la foumula con coeficientes $$f(a_1,a_2,...,a_n)=x_1a_1+x_2a_2+...+x_na_n$$

Una observación importante es que la suma de los coeficientes $x_1+x_2+...+x_n$ tiene que ser $0$ Por otro lado, $a_1$ y $a_n$ aparecen sólo una vez y los otros términos $a_i,(0\leqslant i \leqslant n-1)$ aparecen dos veces, por lo que obtenemos $x_1,x_n \in \{-1,1\}$ y $x_i\in\{-2,0,2\}$ , $(0\leqslant i \leqslant n-1)$ .

Ahora el problema parece aclararse. Es hora de discutir $n$ es par o impar ahora.Primero dejamos que $b_i=i+2^i,1\leqslant i \leqslant n$

$(1)$ Cuando $n$ está en paz:

Los coeficientes $2$ aparece ${n\over 2}$ veces, los coeficientes $-2$ aparece ${n\over 2}$ veces tampoco. Y los coeficientes $1$ y $-1$ ambos aparecen una vez.

Supongamos que $n=2k,k\geqslant 2$

\begin{align} f(a_1,a_2,...,a_n)&=2(b_{2k}+...+b_{k+2})+b_{k+1}-b_k-2(b_{k-1}+...+b_1)\\ &=2[(2k)+...+(k+1)-k-...-1]+k-(k+1)\\ &+2[2^{2k}+...+2^{2k-1}-2^k-...-2]+2^k-2^{k+1}\\ &=2k^2-1+2^{2k+2}-2^{k+3}-2^k+4\\ &=\frac 12 n^2+4\cdot 2^{n}-9\cdot 2^{\frac n2}+3 \end{align}

$(2)$ Cuando $n$ es impar: La situación es un poco diferente, pero en realidad ambos $[1]$ y $[2]$ son los mismos.

$[1]$ Los coeficientes $2$ puede aparecer ${n-1\over 2}$ veces, mientras que $-2$ aparece ${n-3\over 2}$ tiempos, $1$ aparecen dos veces y no $-1$ .

$[2]$ Los coeficientes $2$ aparece ${n-3\over 2}$ veces, mientras que $-2$ aparece ${n-1\over 2}$ tiempos, $-1$ aparecen dos veces y no $1$ .

Supongamos que $n=2k+1,k\geqslant 1$

\begin{align} f(a_1,a_2,...,a_n)&=2(b_{2k+1}+...+b_{k+2})-b_{k+1}-b_k-2(b_{k-1}+...+b_1)\\ &=2[(2k+1)+...+(k+2)-(k+1)-k-...-1]+(k+1)+k\\ &+2[2^{2k+1}+...+2^{k+2}-2^{k+1}-...-2]+2^k+2^{k+1}\\ &=2k^2+2k-1+2^{2k+3}-13\cdot 2^{k+1}+4\\ &=\frac 12 n^2+4\cdot2^{n}-13\cdot 2^{n-1 \over 2}+\frac52 \end{align}

Así que encontramos el valor máximo de la misma.