100 prigionieri

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

100 prigionieri

Messaggio da ronny »

Vi propongo un problema visto su youtube:
- Ci sono 100 prigionieri numerati da 1 a 100
- Abbiamo una stanza che all'interno contiene 100 scatole numerate da 1 a 100.
- Abbiamo cento foglietti dove sono scritti i soliti numeri da 1 a 100. Questi vengono messi casualmente
dentro le 100 scatole.
- Uno alla volta ogni prigioniero entra nella stanza, apre 50 scatole e vede i numeri in esse contenuti. Dopodichè chiude
le scatole e rimette tutto a posto (non può spostare scatole, girare coperchi o altro che lasci indizi agli altri).
- Se tutti i prigionieri trovano all'interno delle 50 scatole che hanno aperto il loro numero allora sono tutti salvi. Se almeno uno non
trova il proprio numero allora sono tutti condannati a morte.

Quale strategia possono utilizzare per massimizzare la probabilità di salvarsi?

Con quella giusta possono arrivare a circa il 31%
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: 100 prigionieri

Messaggio da afullo »

Non ho avuto molto tempo per pensarci, ma credo di avere bisogno di un hint... 🤔
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: 100 prigionieri

Messaggio da ronny »

Una precisazione: non c'è trasferimento di informazioni tra i prigioniere. Infatti il gioco sarebbe lo stesso se ci fossero 100 stanza indentiche (cioè con le 100 scatole che contengolo la stessa permutazione dei 100 bigliettini) e i prigionieri entrassero in parallelo.
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: 100 prigionieri

Messaggio da ronny »

La strategia si esplica all'interno della stanza. Cioè: prima di entrare ogni prigioniero non ha ancora deciso tutte le scatole che aprirà.
Può decidere in base a quello che trova al loro interno.
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: 100 prigionieri

Messaggio da ronny »

Non era un gran consiglio forse, ma è servito nel mio caso a chiarire in quale ambito ragionare.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: 100 prigionieri

Messaggio da afullo »

Ok, grazie. Quindi, se sono indipendenti, bisogna calcolare la probabilità di uno, e poi elevarla a cento?

Scusa i tempi di risposta piuttosto lenti, ma sono settimane piene come delle uova...
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: 100 prigionieri

Messaggio da ronny »

Non ti preoccupare dei tempi.

Con il consiglio ti ho portato fuori strata. Non intendevo quello, ma che le uniche decisioni vengono prese dalla persona mentre è dentro la stanza.
Vista la strategia che adottano non credo le probabilità siano indipendenti.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: 100 prigionieri

Messaggio da afullo »

Ci ho pensato ancora un po' ma alla fine mi sono arreso, ho trovato e letto la soluzione. Devo dire che non avrei mai pensato ad un approccio del genere, anche se lo trovo molto interessante, visto che fa uso di uno strumento spesso sottovalutato nell'ambito di questo tipo di problemi.
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: 100 prigionieri

Messaggio da ronny »

Ho postato il gioco infatti in quanto inizialmente sembra molto difficile raggiungere quella percentuale di successo, anche perchè le scelte dei
vari prigionieri sembrano indipendenti.
Io sono arrivato alla soluzione dopo una piccola imboccata di mio figio che l'aveva vista.
Mentre gli facevo delle domande relative per chiarire il problema mi ha detto
Testo nascosto:
"un prigioniero da quale scatola potrebbe partire?" e quindi, anche per semplificare ho pensato: "da quella con il suo numero (tanto non cambia nulla....)"

e lui ha continuato "e dopo quale apre?"

questo mi ha suggerito in qualche modo l'idea di aprire quella corrispondente al numero trovato nella prima e quindi mi sono immaginato
i cicli, quelli che in genere si usa nella rappresentazione delle permutazioni
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: 100 prigionieri

Messaggio da afullo »

Sì infatti, sembra che già il primo abbia solo il 50%, come è possibile che gli altri novantanove facciano diminuire la probabilità di meno della metà?

Curioso anche che c'è un limite asintotico sopra il 30% per un numero di prigionieri crescente (con la possibilità di aprire sempre metà scatole), si sarebbe portati a pensare che la probabilità tenda semplicemente a zero...
Rispondi