2014 IMO Shortlist A3

For a sequence $x_{1}, x_{2}, \ldots, x_{n}$ of real numbers, we define its price as $$\max _{1 \leq i \leq n}\left|x_{1}+\cdots+x_{i}\right|$$ 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 $\left|x_{1}\right|$ is as small as possible; among the remaining numbers, he chooses $x_{2}$ such that $\left|x_{1}+x_{2}\right|$ is as small as possible, and so on. Thus, in the $i^{\text {th }}$ step he chooses $x_{i}$ among the remaining numbers so as to minimise the value of $\left|x_{1}+x_{2}+\cdots+x_{i}\right|$. 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 \leq c D$. (Georgia)

对于实数序列 $x_{1}, x_{2}, \ldots, x_{n}$，我们将其价格定义为 $$\max _{1 \leq i \leq n}\left|x_{1}+\cdots+x_{i}\right|$$ 给定 $n$ 实数，Dave 和 George 希望将它们排列成价格较低的序列。勤奋的戴夫检查了所有可能的方法并找到了可能的最低价格 $D$。另一方面，贪婪的乔治选择 $x_{1}$ 使得 $\left|x_{1}\right|$ 尽可能小；在剩余的数字中，他选择$x_{2}$，使得$\left|x_{1}+x_{2}\right|$尽可能小，依此类推。因此，在$i^{\text {th }}$步骤中，他在剩余的数字中选择$x_{i}$，以最小化$\left|x_{1}+x_{2}+\cdots+x_{i}\right|$的值。在每一步中，如果多个数字提供相同的值，乔治会随机选择一个。最后他得到了一个价格为 $G$ 的序列。找到最小可能的常数 $c$，使得对于每个正整数 $n$、对于每个 $n$ 实数集合以及对于 George 可能获得的每个可能序列，结果值满足不等式 $G \leq c D$。 (乔治亚州)