Per ogni $n$-upla di numeri reali $(x_1,\ldots, x_n)$ definiamo il suo peso come $\omega(x_1,\ldots, x_n): = \max_{1\le i\le n} |x_1+\ldots+x_i|$.
Data ora una $n$-upla $(y_1,\ldots, y_n)$ di numeri reali, Dvorny e Goblin vogliono permutarla in modo da ottenere una $n$-upla $(x_1,\ldots, x_n)$ con il peso minore possibile.
Dvorny, che è diligente, calcola con pazienza il peso di tutte le possibili permutazioni della $n$-upla data, riuscendo così a stabilire con certezza il peso minimo possibile, che indica con $D$.
Goblin ha invece un atteggiamento più sbrigativo e procede in modo "greedy", scegliendo gli elementi $x_i$ uno per volta. Prima sceglie un elemento $x_1$ tra gli $n$ elementi dati in modo che $|x_1|$ sia il più piccolo possibile. Poi tra i rimanenti sceglie un elemento $x_2$ in modo che $|x_1 + x_2|$ sia il minimo possibile, e così via. In poche parole, all'$i$-esimo passaggio Goblin sceglie un elemento $x_i$ tra quelli non ancora utilizzati in modo tale che $|x_1 +\ldots+x_i|$ sia il minimo possibile. Se in qualche momento Goblin ha più opzioni equivalenti a disposizione, sceglie a caso una di esse. Così facendo, alla fine si ritrova una $n$-upla di peso $G$.
Determinare la più piccola costante $k$ con questa proprietà: qualunque sia l'intero positivo $n$, qualunque sia la $n$-upla $(y_1,\ldots,y_n)$ di partenza, e in qualunque modo proceda Goblin quando il suo algoritmo gli impone una scelta casuale, alla fine si avrà comunque che $G \le kD$.
A me questo in realtà sembrava più miscellanea tendente a combinatoria, ma fonti autorevoli (ISL, ad esempio) dicono che è algebra. Vabbè, buon divertimento!
