The best such constant is $c=2$.

Can you prove this? I can prove that $c \geq 2$ with $x_1=1, x_2=-1, x_3=2, x_4=-2$, but I can't prove that $G \le 2D$ always hold. Any ideas?

Just note that $|x_i| \le 2D$ for all $i$ and also $|x_1+...+x_n|\le D$. George can start with his permutation $y_i$ such that $|y_1+...+y_i| \le 2D$ for all $i$. Assume George fails choosing $y_{i+1}$. If there is some remaining $y$ with the opposite sign of $y_1+...+y_i$, we can choose this one (or a better one). In the other case, we know $y_1+...+y_i$ and the others $y$ have all the same sign and the sum of all these in absolute value is $|x_1+...+x_n|\le D$.

I claim that $c = 2$. As mentioned above, us $1, -1, 2, -2$ as a construction. Now I will prove that $G \le 2D$. Suppose George's sequence goes like $x_1, x_2, ..., x_n$. Now, since by definition, Dave's price is the minimum possible price, then $G \le 2D$ iff $G \le 2 \cdot \text{price for any permutation}$. And since $G \ge |x_1 + x_2 + \cdots + x_i|$ for any $1 \le i \le n$, we have that if for every $i$, $$|x_1 + x_2 + \cdots + x_i| \le 2 \cdot \text{price for any permutation}$$then we're good to go. Lemma 1: If $|a| > 2|b|$ then $|a+b| > |b|$. Proof: From triangle inequality $|a+b| + |-b| \ge |a|$ so $|a+b| \ge |a| - |b| > |b|$. $\Box$ Lemma 2: If $ab < 0$ then $|a+b| \le \max \{|a|, |b|\}$ Proof: WLOG $|a| < |b|$. So we have to show that $|a+b| \le |b|$. Squaring both sides yields $a^2 + 2ab + b^2 \le b^2$ iff $a^2 + 2ab \le 0$. Let our arbitrary permutation be $y_1, y_2, ..., y_n$ and let the price be $P = |y_1 + y_2 + \cdots + y_p|$ for some $1 \le p \le n$. Let $S_0 = 0$ and $S_i = y_1 + y_2 + \cdots + y_i$. First of all, we can prove that $|x_j| \le 2P$. Assume that $|x_j| > 2P$, and we have $y_i = x_j$ for some $i$. Then $$2P \ge |S_i| + |S_{i-1}| \ge |S_i - S_{i-1}| = |x_j|$$contradiction. Then we can use induction. Base case: We prove that $|x_1| \le 2P$. Already done. Inductive step: Assume that $|x_1 + \cdots + x_k| \le 2P$. We want to prove that $|x_1 + \cdots + x_{k+1}| \le 2P$. Now let's not forget the definition of $G$. We certainly know that $|x_1 + x_2 + \cdots + x_{k+1}| \le |x_1 + x_2 + \cdots + x_k + x_j|$ for some $j > k$. Let's select an $x_j$ such that $x_j (x_1 + x_2 + \cdots + x_k) < 0$. Then we're done by lemma 2. If we cannot find an $x_j$ like that, that means $x_1 +x_2 + \cdots + x_k, x_{k+1}, x_{k+2}, ..., x_n$ all have the same sign. But that means $$|x_1 + \cdots + x_{k+1}| \le |x_1 + \cdots + x_n| \le P \le 2P$$So by induction we are done.

SCP wrote: Just note that $|x_i| \le 2D$ for all $i$ and also $|x_1+...+x_n|\le D$. George can start with his permutation $y_i$ such that $|y_1+...+y_i| \le 2D$ for all $i$. Assume George fails choosing $y_{i+1}$. If there is some remaining $y$ with the opposite sign of $y_1+...+y_i$, we can choose this one (or a better one). In the other case, we know $y_1+...+y_i$ and the others $y$ have all the same sign and the sum of all these in absolute value is $|x_1+...+x_n|\le D$. I think that this is incorrect. If some remaining $y$ is the opposite sign then it is not necessarily better. Suppose we have 1 -2 4 already taken, and out choices are -50, 1, 2, 3. Then it's obviously not good to choose the -50 (in george's perspective)

This is an awful problem, and the answer is $c = 2$. I will provide some commentary as to why I thought this problem was awful. We can use $(-1, 1, 2, -2)$ as an example for why the answer should be at least $2$. Now, we will prove that it is at most $2$. When I did this portion, I first thought to consider the case $x_1 + x_2 \cdots + x_n = 0$, but this was a terrible idea. Read on to find out why. Let $u = \max(|x_i|)$. I now claim that $D \ge \dfrac{u}{2}$. This is fortunately not so hard to prove: At some point we must add said $|x_i|$ to the sequence. When this happens, say that we had $a$ before it and we have $a + x_i$ after it. Now by the triangle inequality, it is true that \[ |a| + |a + x_i| = |-a| + |a + x_i| \ge |x_i| = u \], so by the piegonhole principle, one of $|a|$ and $|a + x_i|$ must be larger than $u/2$, implying that $D \ge \dfrac{u}{2}$. I now claim that $C \le u$. We will show this through induction based on $i$. At first, $a_0 = 0$. Say that we had $x$ at some point. If it is positive, since the sum of all terms is zero, there must be $\textit{some}$ negative number left, or else the overall sum would be positive. Hence, we can subtract the negative. After this operation, the number either has either stayed on the same side of the $x$-axis, but become smaller and hence still within $u$, or has crossed and cannot have magnitude more than $u$ (this is easy to verify) ---Random Commentary--- Now with this case out of the way, let's attempt to directly generalize the approach used. Just try dealing directly with a mean of $\mu$ instead of a mean of zero, and now do casework. But for Greedy George, he might not try to approximate the line, so we have to do casework on how large $\mu$ is with respect to $\max(|a_i - \mu|)$, yadayada With that part out of the way, the above attempts will ultimately all fail to come to conclusions. If the above worked, I would have been quite pleased with the problem. However, this dream will not come to be, and here is the actual solution. ---Random Commentary--- Instead of being facetious with the $\mu$, let's try repeating the argument directly! Again, let $u$ be the maximum value of $|a_i|$. Repeat the argument to show that we won't ever have an absolute value exceeding $u$, and we should be good... but there's a small catch here. What if, we can only keep going down or keep going up? Then, obviously $G$ cannot exceed $\max(u, |x_1 + x_2 \cdots + x_n|)$. But what about $D$? Well its clear that it must be at least $\max(|x_1 + x_2 \cdots + x_n|, \frac{u}{2})$ and the result follows. One would expect the $\mu \neq 0$ case to be quite different than the $\mu = 0$ case, and this seems like it should happen. However, its very very similar, which wasted several of my hours, as you can see in the blurb in the middle.

We claim that $c=2$ is least possible. First we show that $c=2$ is possible. Consider the real numbers $2k, 2k, -2k, -k, -k$, where $k>0$ is any positive real number, then no matter how Dave permute this sequence, the first term has an absolute value of at least $k$, so $D\ge k$, and the equality can be acheived by permuting it into $-k, 2k, -2k, 2k , -k$, so $D=k$ for this sequence. For George, he must first chooses $-k$, then $2k$, then $-k$, so his sequence is either $-k, 2k, -k, 2k, -2k$ or $-k, 2k, -k, -2k, 2k$, which both sequences have price $G=2k$. So $c=2$ is possible. Now we claim that for every collection of $n$ real numbers, and for every possible sequence that George might obtain, we have $G\le 2D$. Let $x_1, x_2, \cdots x_n$ be Dave's sequence of $n$ reals with price $D$, Let $y_1, y_2, \cdots y_n$ be George's permutation of $x_1, x_2, \cdots x_n$ and with price $G$. Write $y_k=x_{\sigma(k)}$ for some $\sigma(k)$, then note that by Triangle Inequality, $$|y_k|=|x_{\sigma(k)}|\le |x_1+x_2+\cdots+x_{\sigma(k)}|+|x_1+x_2+\cdots+x_{\sigma(k)-1}|\le 2D$$So we have $|y_k|\le 2D$ for all $k\le n$. Define a function on reals $s(x)$ such that $s(x)=1$ if $x\ge 0$ and $s(x)=-1$ if $x<0$. It is clear that if $s(x)=s(y)$ then $|x+y|=|x|+|y|$. Also note that if $s(x)\neq s(y)$, and $|x|<|x+y|$ then $|x+y|=|y|-|x|$. It is also clear that if $s(x)=s(y)$, then $s(x+y)=s(x)=s(y)$. First, it is clear that $|y_1|\le 2D$, and suppose that in some step, $|y_1+y_2+\cdots +y_i|> 2D$ at the first time, then $|y_1+y_2+\cdots+y_{i-1}|\le 2D$. Note that by the choice of $y_i$ we have $$|y_1+y_2+\cdots +y_{i-1}+y_j|\ge|y_1+y_2+\cdots +y_i|> 2D $$for all $i\le j\le n$. We cannot have $s(y_1+y_2+\cdots +y_{i-1})\neq s(y_j)$, otherwise since $|y_1+y_2+\cdots+y_{i-1}|\le 2D<|y_1+y_2+\cdots +y_{i-1}+y_j|$, we have $$|y_1+y_2+\cdots +y_{i-1}+y_j|=|y_j|-|y_1+y_2+\cdots y_{i-1}| \Rightarrow |y_j|\ge |y_1+y_2+\cdots +y_{i-1}+y_j|>2D$$which contradicts $|y_j|\le 2D$. So $s(y_1+y_2+\cdots y_{i-1})=s(y_j)$ for all $j\ge i$. Therefore, we must have $s(y_1+y_2+\cdots+ y_i)=s(y_{i+1}+\cdots +y_n)$ and thus $$|x_1+x_2+\cdots x_n|=|y_1+y_2+\cdots y_n|=|y_1+y_2 +\cdots+y_i|+|y_{i+1}+y_{i+2}+\cdots+y_n|\ge |y_1+y_2 +\cdots+y_i|>2D$$contraction, since $|x_1+x_2+\cdots+ x_n|\le D$. So the original assumption is false, $|y_1+y_2+\cdots +y_i|> 2D$ can never happen for all $i$, which means exactly $G\le 2D$. We conclude that $c=2$ is the least possible constant.

I claim that the best constant $c$ is 2. To show that this is sufficient, suppose that George begins to construct his sequence, and gets $x_1,x_2,\ldots,x_i$ where $\max\limits_{1\le j\le i} |x_1+\ldots + x_j|\le 2D$ , but is unable to find a suitable $x_{i+1}$ such that $|x_1+\ldots+x_{i+1}|\le 2D$. WLOG the current sum is positive, it is clear that if there exists a remaining number which is negative, then we can choose that number, since $|x_k|\le 2D$ for all $k$. Otherwise, we know that all the remaining numbers are positive. This is also a problem, since then the sum of all the numbers will exceed $2D$, which is a contradiction as this means the price is at least $2D$. Of course, a natural construction is $(1,-1,2,-2)$.

The best constant $c$ is 2. It is tight because the the price of ${k,-k,2k,-2k}$ using George's algorithm would be $2k$, while the price using Dave's algorithm would be $k$. We will now prove $G\le 2D$ always. Claim: $x_i\le 2D$ Proof: Let the sequence with minimum price of $D$ be $x_{\sigma(1)}, x_{\sigma(2)}, \dots,x_i= x_{\sigma(k)},\dots,x_{\sigma(n-1)},x_{\sigma(n)}$. If $k=1$, then $|x_{\sigma(1)}|\le D$ implies $x_i\le 2D$. Otherwise, $|x_{\sigma(1)}+\dots x_{\sigma(k-1)}|\le D$ and $|x_{\sigma(1)}+\dots x_{\sigma(k)}|\le D$ imply $x_i \le 2D\quad \square$ Claim: $x_1+\cdots x_n \le D$ Proof: Let the sequence with minimum price of $D$ be $x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}$. Clearly $x_{\sigma(1)}+ x_{\sigma(2)}+ \cdots, x_{\sigma(n)} \le D \quad \square$ Following George's greedy algorithm, say we get a sequence $x_1,\dots ,x_n$. Suppose for contradiction that for some $i$, $|x_1+\cdots+x_i|>2D$. The case $i=1$ is not allowed by our first claim, and the case $i=n$ is not allowed by our second claim. From now on $2\le i\le n-1$. By the rules of the algorithm, for any $k$ from $i+1$ to $n$, $|x_1+\cdots+x_{i-1}+x_k|\ge|x_1+\cdots+x_i|>2D$. Clearly $x_k$ is nonzero, and so is $x_1+\cdots+x_{i-1}$, so they both are either positive or negative. If all of $x_{i+1},x_{i+2},\dots x_n$ had the same sign as $x_1+\cdots+x_{i-1}$, then $|x_1+\cdots+x_n|>|x_1+\cdots+x_i|>2D>D$, contradicting our second claim. Otherwise, some $x_k$ had opposite sign as $x_1+\cdots+x_{i-1}$. Then $|x_k|>2D$, contradicting our first claim$\quad \blacksquare$

We claim that $c=2$ is optimal. This value is achievable with $x_i = \{1,-1,2,-2\}$ which gives $G=2$ and $D=1$. Also, let $g_i = \sum_{j=0}^i x_i$ be George's partial sums, and $s_i$ be Dave's partial sums. Claim: The total sum $|x_1+x_2+\cdots x_n|$ is $\leq D$. Proof: Clear by definition of $D$.$\square$ Claim: All $x_i\leq 2D$. Proof: Note that since $s_{i+1} = s_i + x_i$, and since we have $|s_j|\leq D$ for all $j$. \[2D \geq |s_{i+1}| + |s_i| = |s_i+x_i| + |s_i| \geq x_i \]so we clearly have $x_i\leq 2D$. $\square$ Now, we claim that $G\leq 2D$. AFTSOC there exists some $i$ such that in $G$'s sequence, $g_{i+1}>2D$ (we WLOG say it will be positive). Then, we must have that $s_i =s_{i+1} - x_{i+1} > 2D - 2D >0$. Claim: $\min(x_{i+1}, x_{i+2},\ldots x_n) \leq D-s_i$. Proof: This is clearly true because if we denote the minimum as $M$, then since $i+1\leq n$ (or else $s_{i+1}$ does not exist) \[D \geq s_n = s_i + \sum_{j=i+1}^n x_j \geq s_i + (n-i) M \geq s_i + M \]From which the claim is proven. $\square$. Thus, we should in fact by definition of $G$ have that $g_{i+1} \leq D \leq 2D$, so we have found a contradiction. Thus, we always have $g_{i+1}\leq 2D$ for all $i$, and therefore $G\leq 2D$, and we are done. $\blacksquare$.

The best $c$ is $c=2$. This is attainable through the numbers $-2, -1, 1, 2 ~(D=1, G=2)$. Now we put two bounds on $D$. Let $M=\max_{1\le i\le n} |x_i|$, and let $S=|x_1+x_2+\ldots+x_n|$. Large Element Bound. $D\ge \frac{M}{2}$. This is easily proved by considering the numbers before and after this number is inserted. Since they differ by $M$, their absolute values must add up to at least $M$ - making the bound clear. Sum Bound. $D\ge S$. Trivial. Now if we prove that George must do at most double one of these bounds, we are done. Case 1: $S\le M$. Then we can prove $G\le M$. Suppose to the contrary that at a particular point that George has no choice but to bring his cost over $M$. WLOG let his current sum be positive, given there exists a number to bring the sum over $M$ and $S\le M$, there must be a negative number present. Then George can choose that negative number, contradiction. Case 2: $S>M$. Then we can prove that $G\le 2S$. Suppose to the contrary that at a particular point that George has no choice but to bring his cost over $2S$. WLOG let his current sum be positive, given there exists a number to bring the sum over $2S$ and $S>M$, the current sum must be greater than $S$ and there must be a negative number present. Then George can choose that negative number, contradiction.

Spent three hours thinking the original expression was $\sum_{1\le i\le n}|x_1+\cdots +x_i|$ rather than $\max_{1\le i\le n}|x_1+\cdots +x_i|$ And yes, the wrong version is much harder, I have no clue how to even approach it. Anyways, $\text{Dave} \geq \max_i \frac{|x_i|}{2}, \text{Greed} \leq \max_i |x_i|$, equality achieved at $(x_1, x_2, x_3, x_4) = (-1, 2, -2, 1)$.

It is hard for me to give this example.

hajimbrak wrote: For a sequence $x_1,x_2,\ldots,x_n$ of real numbers, we define its $\textit{price}$ as \[\max_{1\le i\le n}|x_1+\cdots +x_i|.\]Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_1$ such that $|x_1 |$ is as small as possible; among the remaining numbers, he chooses $x_2$ such that $|x_1 + x_2 |$ is as small as possible, and so on. Thus, in the $i$-th step he chooses $x_i$ among the remaining numbers so as to minimise the value of $|x_1 + x_2 + \cdots x_i |$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$. Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G\le cD$. Proposed by Georgia Just note that $|x_i| \le 2D$ for all $i$ and also $|x_1+...+x_n|\le D$. George can start with his permutation $y_i$ such that $|y_1+...+y_i| \le 2D$ for all $i$. If there is some remaining $y$ with the opposite sign of $y_1+...+y_i$, we can choose this one (or a better one). In the other case, we know $y_1+...+y_i$ and the others $y$ have all the same sign and the sum of all these in absolute value is $|x_1+...+x_n|\le D$.

Here's a proof of why $G\le 2D$. (I spent a little too long trying to show that the answer was $c=\frac{3}{2}$, missing the obvious construction.) Clearly we have $|x_i|\le 2D$. In addition, we also have $|x_1+\dots+x_n|\le D$. Now suppose for the sake of contradiction that George currently has the numbers \[s=y_1+y_2+\dots+y_i\]and adding any of $\{y_{i+1},y_{i+2},\dots,y_n\}$ would cause the price to exceed $2D$ (and assume that $i<n$ is minimal). Clearly all such numbers have the same sign as $s$; however we also find that \[s+y_{i+1}+\dots+y_n\ge s+y_{i+1}>2D>D,\]done. (Instinct tells me this solution has errors.)

With $(-2,-1,1,2)$ note that $G=2D$. Now, we show that $G\le 2D$. Clearly, we must have $x_i\le 2D$ for all $i$ because otherwise, in Dave's sequence, \[x_1+\dots+x_{i-1}+x_i=(x_1+\dots+x_{i-1})+(x_i)\> -D+2D\ge D\]which is a contradiction. Similarly, $x_i\ge -2D$. Now let's work with George's sequence. Suppose $i$ is the minimal value such that $x_1+\dots+x_{i+1}>2D$ then $x_1+\dots+x_{i}>0$ because $|x_{i+1}|\le 2D$. Indeed, by minimality of $i$, $x_{i+1}>0$. If $x_{j}$ is negative for any $x_j$ then replacing $x_{i+1}$ with $x_j$ will get a lower partial sum absolute value, which is a contradiction. Thus, all terms are positive, which means that $x_1+\dots+x_n>2D$ which contradiction.

First of all let's try $(1,-1,2,-2)$, which means $D=1$ while $G=2$. From there we can get the construction $(k,-k,k,-k....,2k,-2k,2k,-2k....)$, which with George's algorithm it will give us $2k$ while with Dave's it will give us $k$. We want to show that $G \leq 2D $. Of course we know that $D \geq |x_1+x_2+....+x_i|$ for all $i$. Claim : $x_i \leq 2D $ for all $1 \leq i \leq n$. Let $S_i$ be Dave's partial sum. So we have that $S_{i+1} = S_i + x_{i+1}$, and since that $S_j \leq D $ for all $j$. \[ 2D \geq |S_{i+1}| + |S_i| = |S_i+x_{i+1}| + |S_i| \geq x_i\] Now by George's algorithm assume that the sequence is $x_1,x_2,...x_n$, then we want to show that for all $i$ we have that $|x_1+x_2+...+x_i | \leq 2D$. Assume the contrary, so $|x_1+x_2+...+x_i| > 2D$, So for some $j$ where $i+1 \leq j \leq n$ we have. \[|x_1+\cdots+x_{i-1}+x_j|\ge|x_1+\cdots+x_i|>2D\]Obviously $x_j$ is nonzero, and so is $|x_1+\cdots+x_{i-1}|$, implying that they are either positive or negative, but if all $x_{i+1},x_{i+2},...,x_n$ have the same sign, But that also means that \[|x_1+\cdots+x_n|>|x_1+\cdots+x_i|>2D>D\]A contradiction since $D \geq |x_1+x_2+....+x_i|$. Otherwise, $x_j$ is opposite sign to $x_1+x_2+....+x_i$, but that means that $|x_j|> 2D$ contradicting our claim.

Got trolled and got this weird construction of $c\geq 2-\frac{1}{2^n}$ $$1,2,-4,-6,8,14,-16,-30,32,-62,64,\dots$$

The answer is $c=2$. If the sequence is $1,-1,2,-2$, then we get $D=1$ and $G=2$, so we cannot do better than $c=2$. Now, we show that $G\leq 2D$. Let $M$ be the maximum magnitude of a term in the sequence, and let $S$ be the sum of all terms. Assume $S\geq 0$. Clearly, $D\geq \frac{M}{2}$, as a change of $M$ cannot stay within an interval of width smaller than $M$. Now, consider George's process. Clearly, if George's prefix sums never go beyond $[-M,M]$, we are done since then $G\leq M\leq 2D$. Now, consider the first step at which George's prefix sum goes outside this interval. If he was between $-M$ and $0$, the only way he can be forced out of $[-M,M]$ is if all remaining terms are negative, as any positive term is safe. However, this contradicts $S\geq 0$. If he was between $0$ and $M$, the only way he can be forced out is if all remaining terms are positive. After adding all remaining terms, he ends up at $S$, so his price is at most $\max(M,S)$. We have shown that $D\geq \frac{M}{2}$. However, clearly $D\geq S$ as well. Thus, $$G\leq \max(M,S)=2\max(\frac{M}{2},\frac{S}{2})\leq 2\max(\frac{M}{2},S)\leq 2D,$$as desired.