Editing post
Fim
editing wAE/#p11
?
B
i
u
strike
img
url
spoiler
youtube
html
video
video (looped)
pre
>
Ok, soluzione per il caso finito. [spoiler]In quanto segue chiamo 0 il nero, 1 il bianco e "somma" la somma modulo 2 (XOR). Il prigioniero #0 dichiara la somma dei colori da #1 a #9. Il prigioniero #1 conosce tutti i colori da #2 a #9 e anche la loro somma S, quindi sommando S a tutti i colori che conosce può estrarre il proprio (così ora #2 conosce pure 8 colori più la loro somma). Con lo stesso ragionamento, se il prigioniero #k-1 conosce S e i colori da #1 a #9 eccetto il proprio, può fare la somma per ricavarlo. Per induzione su k, questo permette di salvare tutti i prigionieri tranne al più il #0.[/spoiler] Questa strategia permette di rendere il rapporto morti/sopravvissuti un o-piccolo di qualunque funzione positiva e decrescente, ma purtroppo non di salvare un numero cofinito di prigionieri. [spoiler]È evidente che il ragionamento di cui sopra funziona qualunque sia il numero (finito) di prigionieri: se sono M+1, permette di salvarne M. Nel caso infinito il ragionamento fallisce perché salvo casi particolari, le somme parziali dei colori non convergono, e quindi non si può definire quella che ho chiamato S. I prigionieri possono accordarsi in anticipo su una successione {a_n} di numeri naturali, e dividere la linea infinita in pezzi lunghi a_n, per poi applicare la strategia di cui sopra a ciascuna parte (ora finita) di linea. Questo permette di salvare ~ a_n/n prigionieri, per cui, prendendo {a_n} crescente in modo rapido a piacere, il rapporto morti/sopravvissuti è ordine n/a_n, decrescente in modo arbitrariamente rapido. Notare che un numero infinito di prigionieri è comunque destinato a morire.[/spoiler] [spoiler]Casi particolari possono essere trattati con successo: - se la successione di colori è definitivamente costante, una strategia vincente è che ciascuno dichiari il colore definitivamente costante; - più in generale, se la successione è definitivamente periodica, allora può essere interpretata come l'espansione in binario di un razionale, che può essere comunicato agli altri giocatori in un numero finito di bit, sacrificando un numero finito di prigionieri (è necessario qualche accorgimento per codificare non ambiguamente questo numero, ma si può fare; se volete dettagli chiedete); - ancor più in generale, se la lettura binaria della successione di colori definisce un irrazionale quadratico, si può codificare questo numero in un numero finito di bit in quanto la sua frazione continua è periodica; - e infine, la cosa più generale che mi viene in mente è che se la lettura binaria della successione di colori è esprimibile in termini di un algoritmo calcolabile ed esprimibile in un numero finito di bit, si può codificare (ad esempio in ASCII) l'espressione di questa funzione con un numero finito di sacrifici e salvare tutti gli altri. Ad esempio, se la successione di colori codifica 1/e, scrivere "sum from 0 to inf (-1)^k/k!" richiede una manciata di bit, e se i prigionieri si erano messi d'accordo sull'alfabeto e sulla codifica, possono comunicare questa informazione per salvare tutti i prigionieri successivi. Si noti che la scelta della strategia avviene prima che vengano messi in fila, e un'eventuale scelta in "runtime" può essere effettuata con un piccolo overhead di sacrifici (analogamente a come una macchina di Turing universale viene preprogrammata come parte del programma stesso). [/spoiler]
Back