OlympiadBench / 1968 / For a sequence x₁,x₂,…,x_(n) of real numbers, we define its…

For a sequence x₁,x₂,…,x_(n) of real numbers, we define its price as

max_(1≤i≤n)|x₁+⋯+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₁ such that |x₁| is as small as possible; among the remaining numbers, he chooses x₂ such that |x₁+x₂| 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₁+x₂+⋯+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≤cD.

For a sequence $x_{1}, x_{2}, \ldots, x_{n}$ of real numbers, we define its price as

$$
\max _{1 \leqslant i \leqslant 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 \leqslant c D$.