MathDB

For a sequence

x_1,x_2,\ldots,x_n

of real numbers, we define its

<span class='latex-italic'>price</span>

\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

Problem Statement