This was harder than I thought. Does anyone have an official solution or different solution to mine below? Condition (3) is equivalent to $a_i - a_{i-1} = \epsilon_i x_i$ for some $\epsilon_i = \pm 1$. Solving this system of inequalities is straightforward, giving us $2a_0 = -\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n$, $2a_i = \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_i x_i - \epsilon_{i+1} x_{i+1} - \ldots - \epsilon_n x_n$ for $0 < i < n$, and $2a_n = \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n$. So the problem is equivalent to showing that given any real numbers $x_1, x_2, \ldots x_n \in [0,1]$, we can choose some $\epsilon_i = \pm 1$ such that all the $2a_i$'s as above are in $[-2,2]$. I prove the following stronger result by induction (I need the stronger result for induction to go through): Prop. For any $n \geq 2$ and real numbers $x_1, x_2, \ldots, x_n \in [0,1]$, there exist $\epsilon_{i,k} = \pm 1$ for integers $i,k$ with $1 \leq i \leq n$ and $-1 \leq k \leq 1$ such that (for a fixed $k$ in the range) all of the following numbers are between in $[-2 + k, 2+k]$ $b_{0,k} = -\epsilon_{1,k} x_1 - \epsilon_{2,k} x_2 - \ldots - \epsilon_{n,k} x_n$, $b_{i,k} = \epsilon_{1,k} x_1 + \epsilon_{2,k} x_2 + \ldots + \epsilon_{i,k} x_k - \epsilon_{i+1,k} x_{i+1} - \ldots - \epsilon_{n,k} x_{n}$ for $0 < i < n$, and $b_{n,k} = \epsilon_{1,k} x_1 + \epsilon_{2,k} x_2 + \ldots + \epsilon_{n,k} x_n$. Proof. The case base case $n = 2$ is easy. For any $x_1,x_2 \in [0,1]$, we have $x_1 - x_2 \leq 1$, $-x_1 - x_2 \leq 1$, and $-x_1 + x_2 \leq 1$, so $\epsilon_{1,-1} = -1$ and $\epsilon_{2,-1} = 1$ work, $\epsilon_{1,0}$ and $\epsilon_{2,0}$ can be anything, and $\epsilon_{1,1} = 1$ and $\epsilon_{2,1} = -1$. Suppose now the Prop. is true for $n \geq 2$. Suppose now we have $n+1$ real numbers $x_1, x_2, \ldots, x_n, x_{n+1} \in [0,1]$. By the cyclic nature of the proposition (order does matter, but up to cyclic order it doesn't) assume without loss of generality that $m = x_{n+1}$ is the largest among $x_i$'s. Suppose $m = 1$. By induction hypothesis we can find $\epsilon_{i,k}$ for $0 \leq i \leq n$ satisfying the condition of the Prop. We handle $k = -1$ first. We have $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq n$, so $-2 \leq b_{i,-1} + m \leq 2$ for all $0 \leq i \leq n$. Now $b_{n,-1} - 1 = -b_{0,-1} - m = -(b_{0,-1} + 1)$, which is certainly in $[-2,2]$ because $b_{0,-1} + 1$ is. So we can choose $\epsilon_{n+1, 0} = -1$. The case $k = 1$ is done exactly the same. The case $k = 0$ is similar and is easy. So we can find $\epsilon_{n+1,k}$'s for $k = -1, 0,1$ when $x_{n+1} = 1$. Suppose now $m \in [0,1)$. Here comes the trick. I have used the induction hypothesis for all $x_i \in [0,1]$. By rescaling by $m$, one sees that in fact we could have proved the same statement (up to $n$ for induction hypothesis) where $x_i \in [0,m]$ and $b_{i,k}$ in $[(-2 + k)m, (2+k)m]$. Since all $x_i \leq x_{n+1} = m$, the same argument as previous paragraph goes through completely with trivial observation that $[(-2 + k)m, (2 + k)m]$ is contained in $[-2 + k, 2 + k]$ for $k = -1,0,1$. The original problem follows easiliy by setting $k = 0$ now.

hochs wrote: Suppose $m = 1$. By induction hypothesis we can find $\epsilon_{i,k}$ for $0 \leq i \leq n$ satisfying the condition of the Prop. We handle $k = -1$ first. We have $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq n$, so $-2 \leq b_{i,-1} + m \leq 2$ for all $0 \leq i \leq n$. Now $b_{n,-1} - 1 = -b_{0,-1} - m = -(b_{0,-1} + 1)$, which is certainly in $[-2,2]$ because $b_{0,-1} + 1$ is. So we can choose $\epsilon_{n+1, 0} = -1$. The case $k = 1$ is done exactly the same. The case $k = 0$ is similar and is easy. So we can find $\epsilon_{n+1,k}$'s for $k = -1, 0,1$ when $x_{n+1} = 1$. I'm sorry but I think this part is not right. When you are dealing with $k=-1$, you need to prove $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq {n+1}$, not $-2 \leq b_{i,-1} \leq 2$. By the way, the offical solution in Chinese is very very hard to understand...... at least I'm not able to translate it.

litongyang wrote: hochs wrote: Suppose $m = 1$. By induction hypothesis we can find $\epsilon_{i,k}$ for $0 \leq i \leq n$ satisfying the condition of the Prop. We handle $k = -1$ first. We have $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq n$, so $-2 \leq b_{i,-1} + m \leq 2$ for all $0 \leq i \leq n$. Now $b_{n,-1} - 1 = -b_{0,-1} - m = -(b_{0,-1} + 1)$, which is certainly in $[-2,2]$ because $b_{0,-1} + 1$ is. So we can choose $\epsilon_{n+1, 0} = -1$. The case $k = 1$ is done exactly the same. The case $k = 0$ is similar and is easy. So we can find $\epsilon_{n+1,k}$'s for $k = -1, 0,1$ when $x_{n+1} = 1$. I'm sorry but I think this part is not right. When you are dealing with $k=-1$, you need to prove $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq {n+1}$, not $-2 \leq b_{i,-1} \leq 2$. By the way, the offical solution in Chinese is very very hard to understand...... at least I'm not able to translate it. This is from a long time ago, so I had to remember what I had done. Here's the "fix" (I just find it strange that I wrote that above, instead of what I write below, which is correct). What I meant is that I'm using $k=-1$ for the inductive hypothesis to prove the current statement for $k = 0$. You misunderstood what I'm doing (likewise, I'm using the $n$-step inductive hypothesis of $k = 0$ to prove the current $(n+1)$-step for $k=-1$ and $k=1$). I will clarify a little more for you: Let $k = -1$ and $m = 1$ for this case (which is what you have problem with). We can then find $\epsilon_1, \epsilon_2, \ldots, \epsilon_n$ such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$, $\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n$, $\ldots$, $\epsilon_1 x_1 + \ldots + \epsilon_n x_n$ are all within $[-2,2]$ (this is by induction on $n$, remember that we have $n+1$ numbers now and using induction). Since $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$, we can assume without any loss of generality that $0 \leq -\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n \leq 2$. Then take $\epsilon_{n+1} = -1$ will do the job, i.e. $-3 \leq -1 \leq -\epsilon_1 x_1 - \ldots - \epsilon_n x_n -1\leq 1$, $-3 \leq \epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 \leq 1$, $-3 \leq \epsilon_1 x_1 + \epsilon_2 x_2 - \epsilon_3 x_3 - \ldots - \epsilon_n x_n - 1 \leq 1$, $\ldots$, $-3 \leq -1 \leq \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n +1\leq 1$. The last inequalities is true because I chose $\epsilon$'s such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$ is in $[0,2]$ (so that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$ is in $[-1,1]$!). The point is this: You need to prove the containment proposition for $[-3,1]$, $[-2,2]$, and $[-1,3]$ by induction, where you prove the $(n+1)$-step induction for $[-3,1]$ and $[-1,3]$ containment using $[-2,2]$ (which is what I just did, clarifying it for you), and using $[-3,1]$ and $[-1,3]$ for containment of $[-2,2]$.

hochs wrote: litongyang wrote: hochs wrote: Suppose $m = 1$. By induction hypothesis we can find $\epsilon_{i,k}$ for $0 \leq i \leq n$ satisfying the condition of the Prop. We handle $k = -1$ first. We have $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq n$, so $-2 \leq b_{i,-1} + m \leq 2$ for all $0 \leq i \leq n$. Now $b_{n,-1} - 1 = -b_{0,-1} - m = -(b_{0,-1} + 1)$, which is certainly in $[-2,2]$ because $b_{0,-1} + 1$ is. So we can choose $\epsilon_{n+1, 0} = -1$. The case $k = 1$ is done exactly the same. The case $k = 0$ is similar and is easy. So we can find $\epsilon_{n+1,k}$'s for $k = -1, 0,1$ when $x_{n+1} = 1$. I'm sorry but I think this part is not right. When you are dealing with $k=-1$, you need to prove $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq {n+1}$, not $-2 \leq b_{i,-1} \leq 2$. By the way, the offical solution in Chinese is very very hard to understand...... at least I'm not able to translate it. This is from a long time ago, so I had to remember what I had done. Here's the "fix" (I just find it strange that I wrote that above, instead of what I write below, which is correct). What I meant is that I'm using $k=-1$ for the inductive hypothesis to prove the current statement for $k = 0$. You misunderstood what I'm doing (likewise, I'm using the $n$-step inductive hypothesis of $k = 0$ to prove the current $(n+1)$-step for $k=-1$ and $k=1$). I will clarify a little more for you: Let $k = -1$ and $m = 1$ for this case (which is what you have problem with). We can then find $\epsilon_1, \epsilon_2, \ldots, \epsilon_n$ such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$, $\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n$, $\ldots$, $\epsilon_1 x_1 + \ldots + \epsilon_n x_n$ are all within $[-2,2]$ (this is by induction on $n$, remember that we have $n+1$ numbers now and using induction). Since $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$, we can assume without any loss of generality that $0 \leq -\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n \leq 2$. Then take $\epsilon_{n+1} = -1$ will do the job, i.e. $-3 \leq -1 \leq -\epsilon_1 x_1 - \ldots - \epsilon_n x_n -1\leq 1$, $-3 \leq \epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 \leq 1$, $-3 \leq \epsilon_1 x_1 + \epsilon_2 x_2 - \epsilon_3 x_3 - \ldots - \epsilon_n x_n - 1 \leq 1$, $\ldots$, $-3 \leq -1 \leq \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n +1\leq 1$. The last inequalities is true because I chose $\epsilon$'s such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$ is in $[0,2]$ (so that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$ is in $[-1,1]$!). The point is this: You need to prove the containment proposition for $[-3,1]$, $[-2,2]$, and $[-1,3]$ by induction, where you prove the $(n+1)$-step induction for $[-3,1]$ and $[-1,3]$ containment using $[-2,2]$ (which is what I just did, clarifying it for you), and using $[-3,1]$ and $[-1,3]$ for containment of $[-2,2]$. I have understood your idea now. Thanks for your quick reply and your explanation!

hochs wrote: By the cyclic nature of the proposition (order does matter, but up to cyclic order it doesn't) assume without loss of generality that $m = x_{n+1}$ is the largest among $x_i$'s. Wait a minate...... I think it is not WLOG here. Because it's not cyclic between $x_{n+1}$ and $x_{1}$. As in the original problem, you can clearly see this.

litongyang wrote: hochs wrote: By the cyclic nature of the proposition (order does matter, but up to cyclic order it doesn't) assume without loss of generality that $m = x_{n+1}$ is the largest among $x_i$'s. Wait a minate...... I think it is not WLOG here. Because it's not cyclic between $x_{n+1}$ and $x_{1}$. As in the original problem, you can clearly see this. It is not cyclic, but it is cyclic *order*. I may as well easily take $x_i$ for some $i$ to be the maximal element, and run the same argument! I'm just making the exposition easier here. Once you choose the signs $\epsilon$'s, then it doesn't matter if you apply it on $x_1, x_2, \ldots, x_n$ or $x_2, x_3, \ldots, x_n, x_1$, or ... It doesn't matter for *cyclic* order. Obviously it matters for order. For example if $\epsilon_1 = 1$, $\epsilon_2 = -1$, and $\epsilon_3 = 1$ for $x_1,x_2,x_3 \in [0,1]$ such that $-x_1 + x_2 - x_3$, $x_1 + x_2 - x_3$, $x_1 - x_2 - x_3$, and $x_1 - x_2 + x_3$ are all in $[-2,2]$. Now change the *cyclic* order to $x_2, x_3, x_1$. Then we still have $x_2 - x_3 + x_1$, $-x_2 - x_3 + x_1$, $-x_2 + x_3 + x_1$, and $-x_2 + x_3 - x_1 = -(x_1 + x_2 - x_3)$ all in $[-2,2]$. Obviously you need to change the $\epsilon$'s by corresponding cyclic order of the original signs as well, but it's quite obvious how to change it. For that matter, if we change the order to $x_3, x_1, x_2$ for example (with the $x_1, x_2, x_3$ and $\epsilon$'s chosen as above) we clearly see $-x_3 + x_1 - x_2$, $x_3 + x_1 - x_2$, $x_3 - x_1 - x_2 = -(x_1 + x_2 - x_3)$, and $x_3 - x_1 + x_2 = -(x_1 - x_2 - x_3)$ are all within $[-2,2]$. The point is that $[-2,2]$ is preserved under $x \mapsto -x$. Regardless of this, I can easily take $x_i$ for the maximal element, and run the same argument for the proof starting at $x_{i+1}$. I just chose $x_{n+1}$ to make the exposition more clear and more concise to get the point.

hochs wrote: litongyang wrote: hochs wrote: Suppose $m = 1$. By induction hypothesis we can find $\epsilon_{i,k}$ for $0 \leq i \leq n$ satisfying the condition of the Prop. We handle $k = -1$ first. We have $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq n$, so $-2 \leq b_{i,-1} + m \leq 2$ for all $0 \leq i \leq n$. Now $b_{n,-1} - 1 = -b_{0,-1} - m = -(b_{0,-1} + 1)$, which is certainly in $[-2,2]$ because $b_{0,-1} + 1$ is. So we can choose $\epsilon_{n+1, 0} = -1$. The case $k = 1$ is done exactly the same. The case $k = 0$ is similar and is easy. So we can find $\epsilon_{n+1,k}$'s for $k = -1, 0,1$ when $x_{n+1} = 1$. I'm sorry but I think this part is not right. When you are dealing with $k=-1$, you need to prove $-3 \leq b_{i,-1} \leq 1$ for all $0 \leq i \leq {n+1}$, not $-2 \leq b_{i,-1} \leq 2$. By the way, the offical solution in Chinese is very very hard to understand...... at least I'm not able to translate it. This is from a long time ago, so I had to remember what I had done. Here's the "fix" (I just find it strange that I wrote that above, instead of what I write below, which is correct). What I meant is that I'm using $k=-1$ for the inductive hypothesis to prove the current statement for $k = 0$. You misunderstood what I'm doing (likewise, I'm using the $n$-step inductive hypothesis of $k = 0$ to prove the current $(n+1)$-step for $k=-1$ and $k=1$). I will clarify a little more for you: Let $k = -1$ and $m = 1$ for this case (which is what you have problem with). We can then find $\epsilon_1, \epsilon_2, \ldots, \epsilon_n$ such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$, $\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n$, $\ldots$, $\epsilon_1 x_1 + \ldots + \epsilon_n x_n$ are all within $[-2,2]$ (this is by induction on $n$, remember that we have $n+1$ numbers now and using induction). Since $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$, we can assume without any loss of generality that $0 \leq -\epsilon_1 x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n \leq 2$. Then take $\epsilon_{n+1} = -1$ will do the job, i.e. $-3 \leq -1 \leq -\epsilon_1 x_1 - \ldots - \epsilon_n x_n -1\leq 1$, $-3 \leq \epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 \leq 1$, $-3 \leq \epsilon_1 x_1 + \epsilon_2 x_2 - \epsilon_3 x_3 - \ldots - \epsilon_n x_n - 1 \leq 1$, $\ldots$, $-3 \leq -1 \leq \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n +1\leq 1$. The last inequalities is true because I chose $\epsilon$'s such that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n$ is in $[0,2]$ (so that $-\epsilon_1 x_1 - \ldots - \epsilon_n x_n - 1 = -(\epsilon_1 x_1 + \ldots + \epsilon_n x_n)$ is in $[-1,1]$!). The point is this: You need to prove the containment proposition for $[-3,1]$, $[-2,2]$, and $[-1,3]$ by induction, where you prove the $(n+1)$-step induction for $[-3,1]$ and $[-1,3]$ containment using $[-2,2]$ (which is what I just did, clarifying it for you), and using $[-3,1]$ and $[-1,3]$ for containment of $[-2,2]$. I am sorry I don't think your solution is right. First you can't assume $x_{n+1}$ is the maximal one. Second you can't assume $ 0\leq-\epsilon_{1}x_{1}-\epsilon_{2}x_{2}-\ldots-\epsilon_{n}x_{n}\leq 2 $,because you must to prove the proposition for $[-2,2]$ to prove the pro for $[-3,1]$ and $[-1,3]$.What you have proved is that the proposition for $[-2,2]$ to prove the pro for $[-3,1]$ or $[-1,3]$.

It's correct, been checked several times over. There are some subtleties that I'm too lazy to write the exact details on aops, leaving the subtle details to the reader (I trust you have at least that much mathematical maturity). I already gave enough details that answer your questions. I'm not writing that again. Go look it over again. Either that or learn to read English better before you post on this again. Please read the replies I've made! I already answered your questions several times over, zhaobin (look above!) I already answered *both* your questions. The first question, look above. For the second, look above a bit more (I say this again: do the cyclic computations yourself! I already did the case for n = 3 just to give you an idea of how to do this).

But I still think your proof is wrong.

zhaobin wrote: But I still think your proof is wrong. Then you need to be more precise, instead of saying "your proof is wrong." I already answered your questions. 1) I already said it doesn't matter if you assume $x_i$ is the maximal for some $i$. You can run the similar argument! 2) I answered this in detail already. You do the exact same thing I did to prove it for $[-1,3]$!!

hochs wrote: zhaobin wrote: But I still think your proof is wrong. Then you need to be more precise, instead of saying "your proof is wrong." I have post my reason.What your have proved is that the pro is true for $[-2,2]$(for n case) then the pro is true for $[-3,1]$ or$[-1,3]$ (for n+1 case) ,But you should prove the pro is true for $[-2,2]$(for n case) then the pro is true for $[-3,1]$ and$[-1,3]$ (for n+1 case) .. I hope you can realize the difference between or and and. (Otherwise I don't know why we can assume $x_{n+1}$ is the maximal one,I can't understand your explation,sorry)

hochs wrote: zhaobin wrote: But I still think your proof is wrong. Then you need to be more precise, instead of saying "your proof is wrong." I already answered your questions. 1) I already said it doesn't matter if you assume $x_i$ is the maximal for some $i$. You can run the similar argument! 2) I answered this in detail already. You do the exact same thing I did to prove it for $[-1,3]$!! When you prove that for $[-1,3]$,I think you may assume $ -2\leq-\epsilon_{1}x_{1}-\epsilon_{2}x_{2}-\ldots-\epsilon_{n}x_{n}\leq 0 $...

zhaobin wrote: hochs wrote: zhaobin wrote: But I still think your proof is wrong. Then you need to be more precise, instead of saying "your proof is wrong." I already answered your questions. 1) I already said it doesn't matter if you assume $x_i$ is the maximal for some $i$. You can run the similar argument! 2) I answered this in detail already. You do the exact same thing I did to prove it for $[-1,3]$!! When you prove that for $[-1,3]$,I think you may assume $ -2\leq-\epsilon_{1}x_{1}-\epsilon_{2}x_{2}-\ldots-\epsilon_{n}x_{n}\leq 0 $... I said this already. Please..... please.... read T_T If $-2 \leq -\epsilon_1x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n \leq 0$, then $0 \leq \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n \leq 2$ and you can set $\epsilon_{n+1} = 1$ or $-1$ accordingly. I assumed that without a loss of generality. Again, please read the ensuing calculations I made for litongyang again. Litongyang understood what I meant, and I'm sure you can too if you just spend a little more time.. I've checked my proof with other colleagues of mine here as well.

If $ 0<-\epsilon_{1}x_{1}-\epsilon_{2}x_{2}-\ldots-\epsilon_{n}x_{n}\leq 2 $,How can you prove the prop for $[-1,3]$?Let $\epsilon_{n+1}$ =what? Can you write it explicitly?

zhaobin wrote: If $ 0<-\epsilon_{1}x_{1}-\epsilon_{2}x_{2}-\ldots-\epsilon_{n}x_{n}\leq 2 $,How can you prove the prop for $[-1,3]$?Let $\epsilon_{n+1}$ =what? Can you write it explicitly? I know *exactly* why you're confused. I was going to make you think more, but I'll bite and spend a bit more time on explaining it to you: Suppose, as you want, $0 \leq -\epsilon_1x_1 - \ldots - \epsilon_n x_n \leq 2$. Then $-2 \leq \epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n \leq 0$. Now by how $\epsilon$'s are chosen, $-2 \leq \epsilon_1 x_1 + \ldots + \epsilon_n x_n \leq 0$, $-2 \leq -(\epsilon_1x_1 - \epsilon_2 x_2 - \ldots - \epsilon_n x_n) = -\epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n \leq 2$, $-2 \leq -(\epsilon_1 x_1 + \epsilon_2 x_2 - \epsilon_3 x_3 - \ldots - \epsilon_n x_n) = -\epsilon_1 x_1 - \epsilon_2 x_2 + \ldots + \epsilon_n x_n \leq 2$, ... So that $-1 \leq \epsilon_1 x_1 + \ldots + \epsilon_n x_n + 1 \leq 1$, $-1 \leq -\epsilon_1 x_1 + \epsilon_2 x_2 + \ldots + \epsilon_n x_n + 1 \leq 3$, $-1 \leq -\epsilon_1 x_1 - \epsilon_2 x_2 + \ldots + \epsilon_n x_n + 1 \leq 3$, ... $-1 \leq -\epsilon_1 x_1 - \ldots - \epsilon_n x_n -1 \leq 1$. So you switch over to $-\epsilon$'s and choose $\epsilon_{n+1} = -1$ (please don't get confused. This is exactly what confused someone at first.)

Thank you very much.But I still have a question about to change the variables... hochs wrote: litongyang wrote: hochs wrote: By the cyclic nature of the proposition (order does matter, but up to cyclic order it doesn't) assume without loss of generality that $m = x_{n+1}$ is the largest among $x_i$'s. Wait a minate...... I think it is not WLOG here. Because it's not cyclic between $x_{n+1}$ and $x_{1}$. As in the original problem, you can clearly see this. It is not cyclic, but it is cyclic *order*. I may as well easily take $x_i$ for some $i$ to be the maximal element, and run the same argument! I'm just making the exposition easier here. Once you choose the signs $\epsilon$'s, then it doesn't matter if you apply it on $x_1, x_2, \ldots, x_n$ or $x_2, x_3, \ldots, x_n, x_1$, or ... It doesn't matter for *cyclic* order. Obviously it matters for order. For example if $\epsilon_1 = 1$, $\epsilon_2 = -1$, and $\epsilon_3 = 1$ for $x_1,x_2,x_3 \in [0,1]$ such that $-x_1 + x_2 - x_3$, $x_1 + x_2 - x_3$, $x_1 - x_2 - x_3$, and $x_1 - x_2 + x_3$ are all in $[-2,2]$. Now change the *cyclic* order to $x_2, x_3, x_1$. Then we still have $x_2 - x_3 + x_1$, $-x_2 - x_3 + x_1$, $-x_2 + x_3 + x_1$, and $-x_2 + x_3 - x_1 = -(x_1 + x_2 - x_3)$ all in $[-2,2]$. Obviously you need to change the $\epsilon$'s by corresponding cyclic order of the original signs as well, but it's quite obvious how to change it. For that matter, if we change the order to $x_3, x_1, x_2$ for example (with the $x_1, x_2, x_3$ and $\epsilon$'s chosen as above) we clearly see $-x_3 + x_1 - x_2$, $x_3 + x_1 - x_2$, $x_3 - x_1 - x_2 = -(x_1 + x_2 - x_3)$, and $x_3 - x_1 + x_2 = -(x_1 - x_2 - x_3)$ are all within $[-2,2]$. The point is that $[-2,2]$ is preserved under $x \mapsto -x$. "The point is that $[-2,2]$ is preserved under $x \mapsto -x$." But $[-3,1]$ is not preserved under $x \mapsto -x$.

You're welcome. This new question is easier to answer. That explanation you just quote is sufficient for $[-2,2]$. But really, it doesn't matter if you assume $x_i$ is the maximal for some $i$. You look at $-\epsilon_1 x_i - \epsilon_2 x_{i+1} - \ldots - \epsilon_n x_{i-1}$ and run the same argument! I understand that the proof for this problem is hard. It took me quite a long time to solve this problem, and I know why and where you are confused, exactly. So please spend some time to look it over carefully, again. I also verified my proof with other mathematicians in my university. Litongyang says the official solution is also quite complicated, so I guess there isn't any "easy" solution to this problem, at least not for now. I will re-type my solution in full detail when I have time later - for future readers.

Thank you very much.Hope you can rewrite a solution for "cyclic"

hochs wrote: But really, it doesn't matter if you assume $x_i$ is the maximal for some $i$. You look at $-\epsilon_1 x_i - \epsilon_2 x_{i+1} - \ldots - \epsilon_n x_{i-1}$ and run the same argument! I'm pretty sure that this part is not enough. First, this is true. You can inductively find $\epsilon_i$, so that $$-\epsilon_1 x_i - \epsilon_2 x_{i+1} - \ldots - \epsilon_n x_{i-1}$$$$+\epsilon_1 x_i - \epsilon_2 x_{i+1} - \ldots - \epsilon_n x_{i-1}$$$$\ldots$$$$+\epsilon_1 x_i + \epsilon_2 x_{i+1} - \ldots +\epsilon_n x_{i-1}$$are all in $[-3,1]$. However, you cannot use "cyclic" part which mean you cannot directly derive $\epsilon_i$ for $(x_1, ..., x_n)$ from the $\epsilon_i$ above. To make it clear, the "cyclic" part you wrote can be explicitly written as follows. If we have $(\epsilon_1, ...,\epsilon_n)$ for $(x_1,...,x_n)$. Then $(\epsilon_2,...\epsilon_n, -\epsilon_1)$ satisfies problem for $(x_2, ... , x_n, x_1)$. For $[-2,2]$, $\epsilon_2 x_2 +...+\epsilon_n x_n - \epsilon_1 x_1 \in [-2,2]$ is implied, but for you get only $\in [-1,3]$. So we need another way to fix this issue.

For any $a\in[0,1)$, define a sequence $(a_i)_{i=0}^n$ generated by $a$ as follows: For $1\leq i\leq n$, $a_0=a$ For $a_{i-1}\geq 0$, $a_i=a_{i-1}-x_i$ For $a_{i-1}<0$, $a_i=a_{i-1}$ Set $f(a)=a_n$. It is easy to show using induction that $|a_i|\leq 1$ for $0\leq i\leq n$. If there exists $a\in[0,1)$ such that $f(a)=-a$, consider the sequence generated by $a$: $a_0=a$, $a_1,\dots, a_n=f(a)=-a$ Clearly, this sequence satisfies the conditions $(1)$ and $(3)$ in the problem. By recursive relation, it also satisfies the condition $(2)$. It therefore suffices to show that there exists $a\in[0,1)$ s.t. $f(a)=-a$. For any $a\in[0,1)$, we say that $a$ is a chika point if at least on term in its generating sequence is $0$. Since every chika point is of the form $\sum_{i=1}^{n} t_ix_i$, where $t_i=-1,0,1$, there are finitely many chika points. Clearly, $0$ is a chika point; label all chika points in increasing order by $0=c_1<c_2<\dots<c_m<1$. We first prove that for $1<k<m-1$, $f(a)=f(c_k)+(a-c_k)$ for every $a\in[c_k, c_{k+1})$. Consider $c_k, c_{k+1}$ and their generating sequences. Assume that $q_0=c_k$, $q_1,q_2,\dots, q_n$ is the generating seuqnece of $c_k$, and $r_0=b_{k+1}, r_1, r_2, \dots, r_n$ is the generating seuqnece of $c_{k+1}$. Suppose that $r_1$ is the first term of $(r_i)_{i=0}^n$ equal to $0$. Construct a sequence $(s_i)_{i=0}^n$ as follows: $s_0=r_0, s_1=r_1, \dots, s_l=r_l=0$ $s_{l+1}=-r_{l+1}, \dots, s_n=-r_n$. It is clear that the sequence $(s_i)_{i=0}^n$ satisfies $s_0=c_{k+1}$ and for $1\leq i\leq n$, $s_i=s_{i-1}-x_i$ if $s{i-1}>0$, and $s_i=s{i-1}+x_i$ if $s_{i-1}\leq 0$. We prove by induction that $q_is_i\geq 0$ and $s_i-q_i=c_{k+1}-c_k$. This is clearly true for $i=0$. Assume that it holds for $i-1$. Then $q_{i-1}s_{i-1}\geq 0$ and $s_{i-1}-q_{i-1}=c_{k+1}-c_k>0$, which implies two cases: Case 1: $q_{i-1}\geq 0$, $s_{i-1}>0$: This means that $q_i=q_{i-1}-x_i$, $s_i=s_{i-1}-x_i$, and thus $s_i-q_i=s_{i-1}-q_{i-1}=c_{k+1}-c_k$. Case 2: $q_{i-1}<0$, $s_{i-1}\leq 0$: We have $s_i-q_i=c_{k+1}-c_k$, just like in the previous case. If $q_is_i<0$, then $q_i<0<s_i$. Set $c'=c_{k+1}-s_i=c_k-q_i\in(c_k, c_{k+1})$. Consider the generating sequence of $c'$: $u_0=c', u_1, \dots, u_n$. It is easy to show by induction that $s_j-u_j=s_0-u_0=s_i$ for any $0\leq j\leq i$ ($q_{j-1}$ and $s_{j-1}$ both add or subtract $x_j$ for $j<i$; $u_j$ lies between $q_{j-1}$ and $q_{j-1}$, so the recursive relation is the same). Then $u_i=s_i-s_i=0$, i.e. $c'$ is a chika point-- a contradiction to $c_k$, $c_{k+1}$ being two consecutive chika points. Therefore $q_is_i\geq 0$. By induction we have verified that $q_is_i\geq 0$ and $s_i-q_i=c_{k+1}-c_k$ for all $0\leq i\leq n$. Since $f(c_k)=q_n$, $f(c_{k+1})=r_n=-s_n$, we have $f(c_k)+f(c_{k+1})=c_k-c_{k+1}$. It follows from the above argument that, for any $c_k<c'<c_{k+1}$, the generating sequence of $c'$ has the same recursive relation as $(s_i)_{i=0}^n$ and $(q_i)_{i=0}^n$, giving: $f(c')=f(c_k)+(c'-c_k)$ We now consider two cases: If $f(c_k)=-c_k$ for some $k$, we are done. If $f(c_k)=c_k$ for some $k$, then consider the generating sequence of $c_k$, reversing every term after the first $0$, and we obtain a new sequence $z_0=c_k, z_1,\dots, z_n=-c_k$, which satisfies the required conditions. Now assume that $|f(c_k)|\neq c_k$ for every $k$, and we shall consider two cases to show that $f(a)=-a$ for some $a\in[0,1)$: Case 1: $|f(c_m)|<c_m$: Since $|f(c_1)|>c_1=0$, then there exists a $k$ s.t. $|f(c_k)|>c_k-c_{k+1}$ and $c_k-c_{k+1}<c_{k+1}$. Since $f(c_k)+f(c_{k+1})=c_k-c_{k+1}$, we have $f(c_k)-c_k=-(f(c_{k+1})+c_{k+1})<0$, and hence $f(c_k)<-c_k$. By $f(c_k)+f(c_{k+1})=c_k-c_{k+1}$, we have: $f(c_k)=c_k-c_{k+1}-f(c_{k+1})>c_k-2c_{k+1}$. In other words: $c_k-2c_{k+1}<f(c_k)<-c_k$. Let $c'=\frac{c_k-f(c_k)}{2}$. Then $c_k<c'<c_{k+1}$, and $f(c')=f(c_k)+f(c'-c_k)=(c_k-2c')+(c'-c_k)=-c'$, and the result follows. Case 2: $|f(c_m)|>c_m$. Since there is no chika number in $(c_m,1)$, we see from our previous case that for any $c'\in(c_m,1)$, the generating sequence of $c'$ and the generating sequence of $c_m$ have the same recursive relation, and hence: $f(c')=f(c_m)+f(c'-c_m)$ Since $|f|\leq 1$, we have $f(c_m)\leq c_m$, and so $-1\leq f(c_m)<-b_m$. Let $c'=\frac{c_m-f(c_m)}{2}$. Then: $c_m=\frac{c_m-(-c_m)}{2}<c'<\frac{c_m+1}{2}<1$, $f(c')=f(c_m)+(c'-c_m)=(c_m-2c')+(c'-c_m)=-c'$. The result again follows, and we are done $\blacksquare$ I believe that this is also the official solution.