AoPS - Problem

Source: Spanish Communities

Tags: induction, algebra unsolved, algebra

carlosbr

09.04.2006 02:51

Pablo copied from the blackboard the problem: Consider all the sequences of $2004$ real numbers $(x_0,x_1,x_2,\dots, x_{2003})$ such that: $x_0=1, 0\le x_1\le 2x_0,0\le x_2\le 2x_1\ldots ,0\le x_{2003}\le 2x_{2002}$. From all these sequences, determine the sequence which minimizes $S=\cdots$ As Pablo was copying the expression, it was erased from the board. The only thing that he could remember was that $S$ was of the form $S=\pm x_1\pm x_2\pm\cdots\pm x_{2002}+x_{2003}$. Show that, even when Pablo does not have the complete statement, he can determine the solution of the problem.

I am not very sure about this. Never used the condition $0\leq{x_i}$. We can prove the general case, for any integer $n$, $S=\pm{}x_1\pm{}x_2\cdots\pm{}x_{n-1}+x_n$ is maximized when $x_i=2^i$. Use induction on $n$. If $n=1$, then the case is obvious. For $n=k$: If the sign before $x_{n-1}$ is positive, then $S-x_n$ is maximized by assumption, so will be $x_n$ if $x_i=2^i$. If the sign before $x_{n-1}$ is negative, then $-x_{n-1}+x_n\leq-x_{n-1}+2x_{n-1}=x_{n-1}$, with equality if $x_n=2x_{n-1}$. So $S\leq\pm{}x_1\pm{}x_2\cdots\pm{}x_{n-2}+x_{n-1}$, which is maximized if $x_i+2^i$. Altogether, $S$ is maximized if $x_i=2^i$ for $1\leq{i}\leq{n-1}$ and $x_n=2x_{n-1}$.