# Greedy algoritme is voldoende

Tags:

## Opgave - IMOSL 2014 vraag 3

Voor een rij reele getallen $x_1,x_2,\ldots,x_n$ definieer de prijs als $\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$.