OliForum Matematico

Lo so che molti di voi l'hanno già visto (dunque i Winteristi sono invitati a non risolverlo), ma è bello e inoltre il testo è così lungo che ci si mette di più a leggerlo che a risolverlo (scherzo, magari!):

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!

Chissà perché gli originali Dave e George sono stati cambiati in Dvorny e Goblin...

Ahahah probabilmente i traduttori del testo sono Dvorny e Goblin!

Up! Daje con questa staffetta!

Qualcuno riesce a illuminarmi facendomi capire come l'algoritmo di goblin potrebbe portare a una permutazione con peso non minimo? Se l'algoritmo impone una scelta casuale significa che gli elementi candidati sono uguali (allora è indifferente) oppure sono tali che sommando entrambi con il valore R raggiunto prima di dover aggiungere essi si ottiene l'opposto di R.. Inoltre ho un frammento di idea sul discorso che quando s'ha da fare una scelta casuale non sono permessi tutti i valori, in quanto alcuni sarebbero stati selezionati in precedenza dall'algoritmo, poi cerco di razionalizzare questi fumi blu :S

Prendi la quaterna (1, -3, -5, 7). L'algoritmo ottimale di Dvorny la permuta come (-3, 7, -5, 1) in cui le somme parziali sono $|-3|=3$, $|-3+7|=4$, $|-3+7-5|=1$, $|-3+7-5+1|=0$, quindi il massimo è 4.
L'algoritmo greedy di Goblin la permuta come (1,-3, 7, -5), perché cosi ad ogni passaggio il modulo è il minimo tra i possibili: $|1|=1$, $|1-3|=2$, $|1-3+7|=5$, $|1-3+7-5|=0$. Qua il massimo è 5, che è maggiore di 4, quello ottenuto da Dvorny.
Per la scelta casuale, non c'è molto da dire: quello che ti interessa è trovare una stima di G, quindi nel caso di più scelte possibili occorre scegliere quella "peggiore" per farsi meno casi

Ok grazie, ora mi ricimento