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!
100. Dvorny & Goblin
100. Dvorny & Goblin
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
- Federico II
- Messaggi: 230
- Iscritto il: 14 mag 2014, 14:56
- Località: Roma
Re: 100. Dvorny & Goblin
Chissà perché gli originali Dave e George sono stati cambiati in Dvorny e Goblin...
Il responsabile della sala seminari
Re: 100. Dvorny & Goblin
Ahahah probabilmente i traduttori del testo sono Dvorny e Goblin!
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Re: 100. Dvorny & Goblin
Up! Daje con questa staffetta!
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Re: 100. Dvorny & Goblin
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
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: 100. Dvorny & Goblin
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
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
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"