Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Para simplificar la notación, escribamos $S=\sum_{n=1}^{2003}\epsilon_nx_n$, donde $\epsilon_n$ es el signo correspondiente a $x_n$, es decir $\epsilon_n=1$ ó $\epsilon_n=-1$. Supongamos además que estamos trabajando con la sucesión $\{x_n\}$ que maximiza $S$ y probemos que $x_n=2^n$ para todo $n$ independientemente del valor de los $\epsilon_n$ (observemos que esto es equivalente a demostrar que $x_n=2x_{n-1}$ para todo $n\in\{1,\ldots,2003\}$).

• Veamos en primer lugar que no pueden haber términos nulos. Si $x_k=0$, entonces $x_n=0$ para todo $n\geq k$, luego podemos suponer que $x_k$ es el primer término nulo. Si consideramos la sucesión \[\overline{x}_n=\begin{cases}x_n,& \text{si }0\leq n\lt k,\\ 2\overline{x}_{n-1},&\text{si }k\leq n\leq 2003,\end{cases}\] (es decir, sustituimos todos los términos nulos por los máximos posibles) entonces \[S(\overline x)-S(x)=x_{k-1}\left(2^{2004-k}+\sum_{n=k}^{2002}\epsilon_n2^{n-k+1}\right)\geq x_{k-1}\left(2^{2004-k}-\sum_{n=k}^{2002}2^{n-k+1}\right)=2x_{k-1}>0,\] lo que nos dice que la sucesión $\overline x$ da un valor mayor para $S$, contradiciendo que habíamos supuesto que $x$ maximizaba el valor de $S$. En la desigualdad anterior, hemos usado que el valor mínimo se obtiene cuando todos los $\epsilon_n$ son negativos.
• Supongamos ahora que todos los $x_n$ son positivos pero que existe $k$ tal que $x_k\lt 2x_{k-1}$. Nuestro objetivo es llegar también a una contradicción.
  • Si $\epsilon_k=1$, entonces claramente la sucesión que resulta al sustituir $x_k$ por $2x_{k-1}$ mejora el valor de $S$, luego tenemos la contradicción buscada.
  • Si $\epsilon_k=-1$, entonces consideremos el primer $p\gt k$ tal que $\epsilon_p=1$ (que siempre existe ya que $\epsilon_{2003}=1$). Dado $\lambda=\frac{2x_{k-1}}{x_k}\gt 1$, podemos considerar la nueva sucesión \[\overline{x}_n=\begin{cases}2\overline{x}_{n-1},& \text{si }k\leq n\leq p,\\ x_n,&\text{para el resto de valores de }n.\end{cases}\] Entonces, podemos calcular \begin{eqnarray*} S(\overline x)-S(x)&=&2^{p-k+1}x_{k-1}-x_p-\sum_{n=k}^{p-1}(2^{n-k+1}x_{k-1}-x_n)=2x_{k-1}+\sum_{n=k}^{p-1}x_n-x_p\\ &\gt& 2x_k+\sum_{n=k+1}^{p-1}x_n-x_p\geq 2x_{k+1}+\sum_{n=k+2}^{p-1}x_n-x_p\geq\ldots\geq 2x_{p-1}-x_p\geq 0. \end{eqnarray*} En las últimas desigualdades hemos usado que $2x_{k-1}>x_k$ y $2x_{n-1}\geq x_n$ para el resto de valores de $n$. Esta desigualdad estricta nos dice que $\overline x$ mejora el valor de $S$ y volvemos a tener una contradicción.

Nota. En realidad, el propio problema nos da una pista fundamental para saber que la sucesión que maximiza ha de ser $x_n=2^n$ para todo $n$. Como la solución no depende de la elección de los signos $\epsilon_n$, también tiene que valer para todos positivos y ahí es claro que $S$ es máximo cuando todos los $x_n$ son lo más grandes posibles, esto es, $x_n=2x_{n-1}$ para todo $n$.

Solución. Este es un problema de programación lineal, ya que tenemos que maximizar una combinación lineal de los valores de $x_1,x_2,\ldots,x_{2003}$ con ciertas desigualdades lineales $0\leq x_k\leq 2x_{k-1}$. Los valores que maximizan $S$ serán uno de los vértices de la región de $\mathbb{R}^{2003}$ determinada por estas desigualdades (observemos que la región está acotada, luego la existencia de solución está garantizada). Usando que, en cuanto una variable es cero las sucesivas han de ser cero también, es fácil ver que dicha región tiene 2004 vértices, dados por \begin{eqnarray*} p_0&=&(0,0,0,0\ldots,0),\\ p_1&=&(2,0,0,0\ldots,0),\\ p_2&=&(2,4,0,0\ldots,0),\\ p_3&=&(2,4,8,0\ldots,0),\\ &\vdots&\\ p_{2003}&=&(2,4,8,16,\ldots,2^{2003}). \end{eqnarray*} Ahora será suficiente ver que $S(p_{2003})> S(p_k)$ para todo $k\in\{0,\ldots,2002\}$ independientemente del valor de los signos que definen a $S$. Si escribimos $S=x_{2003}+\sum_{n=1}^{2002}\epsilon_nx_n$, siendo $\epsilon_n\in\{-1,+1\}$ el coeficiente de $x_n$, obtenemos que, para todo $k\in\{0,\ldots,2002\}$, se cumple que \begin{eqnarray*} S(p_{2003})-S(p_k)&=&\left(2^{2003}+\sum_{n=1}^{2002}\epsilon_n 2^n\right)-\sum_{n=1}^k\epsilon_n2^n=2^{2003}+\sum_{n=k+1}^{2002}\varepsilon_n2^n &\geq&2^{2003}-\sum_{n=1}^{2002}2^n=2\gt 0, \end{eqnarray*} como queríamos demostrar.

Nota. Esta solución no es elemental, aunque es una aproximación válida y sencilla una vez se conoce la técnica de programación lineal. El mismo método sirve para probar el resultado cuando se cambia 2003 por cualquier otro entero positivo.