Olimpiadi della Matematica Torino - OliMaTO - Forum

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%

Non ho avuto molto tempo per pensarci, ma credo di avere bisogno di un hint...

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.

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.

Non era un gran consiglio forse, ma è servito nel mio caso a chiarire in quale ambito ragionare.

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...

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.

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.

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

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...