Newsgroup: it.hobby.enigmi
Titolo: Ancora prigionieri matematici

Adatto un problemino forse già conosciuto (trovato su newsgroup
anglosassoni),
qui non l'ho visto passare (ma magari sbaglio).
Un gruppo di 20 prigionieri (matematici), numerati da 1, 2, …, 20.
Gli si dice che essi dovranno svolgere un gioco con un carceriere per
la libertà.
Nel gioco, il carceriere prenderà 20 biglietti, numerati da 1, 2,...,
20
e mette esattamente uno di questi biglietti in ciascuna di 20 celle
identiche,
anch'esse numerate 1, 2, …, 20.
Il carceriere sceglierà la cella per ogni biglietto in modo casuale.
Una volta che il carceriere ha distribuito i biglietti,
egli seleziona un prigioniero e e lo inviterà ad aprire
e analizzare il contenuto di 12 celle a sua scelta.
Dopo l'inizio del gioco non è consentita alcuna ulteriore
comunicazione con gli altri prigionieri,
spostamenti di biglietti o manipolazioni di alcun tipo.
In seguito, il carceriere farà lo stesso con tutti e 20 i prigionieri,
le celle che ha aperto un prigioniero saranno tutte chiuse nuovamente
prima del successivo.
Se, alla fine, ogni prigioniero è riuscito ad aprire la cella
contenente
il biglietto con il suo numero su di esso tra le 12 scelte, tutti i
prigionieri saranno liberi.
Che strategia dovrebbero utilizzare per massimizzare la loro
probabilità di libertà.
Secondo voi questa è maggiore o minore del 50% se tutti seguono la
corretta strategia?
A occhio infatti sembra che se tutti scelgono 12 celle a caso si abbia
una probabilità di
(12/20) ^ 20
e se tutti decidessero di aprire le prime 12 celle dello 0 %.
Ciao
Andrea

 corretta strategia?
Dunque. Il carceriere produce una permutazione dei 20 numeri nelle
venti celle. Visto che non ci sono possibilità di comunicare, l'unica
è scegliere una strategia che permetta la salvezza nel maggior numero
possibile delle possibili 20! permutazioni.
La prima (ed unica) che mi viene in mente è:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Il prigioniero n apre la cella n, legge il biglietto che trova nella
cella, apre la cella indicata dal biglietto e così via, sperando di
trovare il "cortocircuito" che lo riporta nella sua cella.
Tutti si salvano se nella permutazione dei foglietti non ci sono cicli
di lunghezza maggiore di 12.
Se per sfortuna ci fosse un ciclo di lunghezza n maggiore di 12,
allora ogni prigioniero appartenente alla catena non troverebbe in
tempo il suo numero. Per esempio, con un ciclo 3-5-8-7-15-..-11, il
prigioniero 3 troverebbe nella sua cella un 5, nella cella 5 un 8,
nella 8 un 7, e gli servirebbero più di 12 passi per arrivare alla
cella 11 dove troverebbe il suo 3.
Invece i quattro prigionieri del ciclo 1-17-5-9 troverebbero il loro
biglietto in 4 passi.
Per il calcolo delle probabilità di produrre casualmente permutazioni
senza cicli lunghi mi ci vuole un po' di tempo che ora non ho. A
occhio se non si arriva al 50% poco ci manca, ma mi potrei sbagliare.
--
Silv:o)

 occhio se non si arriva al 50% poco ci manca, ma mi potrei sbagliare.
Ottimo. Bravo bravissimo e a tempo di record, manca però il risultato
del calcolo,
ossia se siamo sopra o sotto il 50,
visto che la formula non è troppo complessa magari qualcun altro si
vuole cimentare :-)
Ciao
Andrea

 vuole cimentare :-)
Stamattina nel viaggio in macchina verso l'ufficio ho pensato la
soluzione.
Quante sono le permutazioni che hanno un ciclo da 13?
Intanto vediamo quanti sono i cicli possibili, ovvero le disposizioni
cicliche di 20 elementi in gruppi di 13:
sono 20*19*18*..*8/13 perchè il primo elemento del ciclo lo posso
scegliere in 20 modi, il secondo in 19 e così via, e poi devo dividere
per 13 per via della ciclicità.
In notazione compatta posso scrivere 1/13*20!/7!.
Per ogni scelta di ciclo, i restanti 7 numeri possono essere permutati
a piacere in tutti i 7! modi possibili: non ci interessa sepere se i 7
prigionieri trovano il proprio numero subito nella propria cella o se
tutti devono farsi il giro delle 7 parrocchie.
Quindi le permutazioni che presentano un ciclo da 13 sono 1/13*20! e
quindi hanno 1/13 di probabilità di essere prodotte generando a caso
le 20! permutazioni.
Stesso discorso per i cicli di lunghezza superiore.
La probabilita' totale vale 1/13+1/14+..+1/20 che guardacaso è vicina
al cinquanta per cento: 0.494528979+
--
Ciao, Silv:o)


Ottimo.
Finisco il ragionamento per tutti....
e quindi la probabilità di salvezza (che è complementare al tuo
calcolo) è superiore al 50%.
Io amo il lieto fine per cui i numeri li ho messi apposta in modo che
superassero il 50%.
Ciao
Andrea