50 PRIGIONIERI
50 PRIGIONIERI
Intuendo che i matematici anche quando sono sotto l'ombrellone hanno voglia di perdere la testa in problemi complessi, propongo un problema molto bello in cui mi sono imbattuto recentemente. Spero che non sia un problema noto. Divertitevi!
Il guardiano di una prigione promette di liberare tutti i 50 prigionieri della prigione se riusciranno a superare una prova. Il guardiano scrive i 50 nomi dei prigionieri (che per praticità chiamiamo $ P_1 , P_2 , ... , P_{50} $) su 50 bigliettini. Dopodiché inserisce CASUALMENTE ciascun bigliettino dentro a 50 bottiglie allineate su un tavolo (in ogni bottiglia inserisce un solo bigliettino). A questo punto conduce il prigioniero $ P_1 $ davanti alle bottiglie, egli sceglie 25 bottiglie tra il gruppo di 50, le apre e legge i nomi. Dopodiché richiude tutte le 25 bottiglie, se ne va e tocca al prigioniero successivo, e così via, fino a che tutti quanti hanno fatto ciò. Se TUTTI i 50 prigionieri, quando è il loro turno, trovano il loro nome tra le 25 bottiglie che aprono, sono tutti liberi di andare. In caso contrario dovranno tutti restare in prigione. Essi possono mettersi d'accordo solo prima di iniziare il gioco per elaborare una tattica comune che gli permetta di incrementare la probabilità di ottenere la libertà. Una volta che il gioco è iniziato non hanno più modo di comunicare (inutile dire quindi che devono richiudere le bottiglie dopo che le hanno aperte, non possono spostare bottiglie o bigliettini, non possono passarsi informazioni di alcun tipo...).
Parliamo ora della strategia che dovrebbero utilizzare per incrementare la probabilità di salvarsi tutti. Una strategia possibile potrebbe essere per esempio scegliete le bottiglie a caso. Così facendo ognuno avrebbe $ {1 \over 2} $ di probabilità di trovare il proprio nome, e quindi la probabilità che l'intero gruppo sia libero è $ {1 \over 2^{50}} $. Una probabilità molto bassa insomma: basti pensare che se aumentassimo sempre di più il numero di prigionieri, con questa tecnica la probabilità che vengano liberati tenderebbe a 0.
La parte interessante viene proprio qua: esiste una strategia di apertura delle bottiglie che permette ai prigionieri di trovare la libertà con una probabilità di poco maggiore del 30% (anche se aumenta il numero di prigionieri del gioco). Sapreste trovarla?
Il guardiano di una prigione promette di liberare tutti i 50 prigionieri della prigione se riusciranno a superare una prova. Il guardiano scrive i 50 nomi dei prigionieri (che per praticità chiamiamo $ P_1 , P_2 , ... , P_{50} $) su 50 bigliettini. Dopodiché inserisce CASUALMENTE ciascun bigliettino dentro a 50 bottiglie allineate su un tavolo (in ogni bottiglia inserisce un solo bigliettino). A questo punto conduce il prigioniero $ P_1 $ davanti alle bottiglie, egli sceglie 25 bottiglie tra il gruppo di 50, le apre e legge i nomi. Dopodiché richiude tutte le 25 bottiglie, se ne va e tocca al prigioniero successivo, e così via, fino a che tutti quanti hanno fatto ciò. Se TUTTI i 50 prigionieri, quando è il loro turno, trovano il loro nome tra le 25 bottiglie che aprono, sono tutti liberi di andare. In caso contrario dovranno tutti restare in prigione. Essi possono mettersi d'accordo solo prima di iniziare il gioco per elaborare una tattica comune che gli permetta di incrementare la probabilità di ottenere la libertà. Una volta che il gioco è iniziato non hanno più modo di comunicare (inutile dire quindi che devono richiudere le bottiglie dopo che le hanno aperte, non possono spostare bottiglie o bigliettini, non possono passarsi informazioni di alcun tipo...).
Parliamo ora della strategia che dovrebbero utilizzare per incrementare la probabilità di salvarsi tutti. Una strategia possibile potrebbe essere per esempio scegliete le bottiglie a caso. Così facendo ognuno avrebbe $ {1 \over 2} $ di probabilità di trovare il proprio nome, e quindi la probabilità che l'intero gruppo sia libero è $ {1 \over 2^{50}} $. Una probabilità molto bassa insomma: basti pensare che se aumentassimo sempre di più il numero di prigionieri, con questa tecnica la probabilità che vengano liberati tenderebbe a 0.
La parte interessante viene proprio qua: esiste una strategia di apertura delle bottiglie che permette ai prigionieri di trovare la libertà con una probabilità di poco maggiore del 30% (anche se aumenta il numero di prigionieri del gioco). Sapreste trovarla?
Ultima modifica di PIELEO13 il 23 lug 2016, 21:02, modificato 1 volta in totale.
Re: 50 PRIGIONIERI
Youtube dice che almeno 2 milioni di persone sanno la soluzione
Comunque è un bel problema!
Comunque è un bel problema!
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: 50 PRIGIONIERI
La stessa cosa che ho pensato quando lo ho lettoDrago96 ha scritto:Youtube dice che almeno 2 milioni di persone sanno la soluzione
Comunque è un bel problema!
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia
Re: 50 PRIGIONIERI
Ahahahah ok non era un problema così sconosciuto come pensavo, ma con i vostri commenti avete disinvogliato le persone più insicure a tentare di risolvere il problema!! Comunque, per i più pro, rilancio il problema: dimostrate che la strategia che io avevo proposto di trovare (quindi suppongo che quella che voi avete in mente sia la stessa che pensavo io) sia la strategia migliore attuabile... cioè che per i prigionieri non sia possibile fare meglio di così!
Re: 50 PRIGIONIERI
Il testo è leggermente impreciso, perché è importante specificare (se la strategia è quella che ho in mente io avendo già sentito il problema) che le bottiglie vengono aperte una per volta (con la possibilità di variare la scelta della successiva in base ai bigliettini già visti) e non "apro queste: la 1, la 2, la 3, la 5, la 12, ...".
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: 50 PRIGIONIERI
Si confermo quello che dici tu, le bottiglie vanno aperte una per volta, in effetti era impreciso
Re: 50 PRIGIONIERI
No, non saprei da dove cominciarePIELEO13 ha scritto:Sapreste trovarla?
Va bene o devo dimostrarlo?
A parte questo, qualcuno mi saprebbe dare un indizio? Se ho capito bene il problema, mi sembra che, se non possono assolutamente comunicare tra di loro, la scelta di ognuno è indipendente da quello che gli altri hanno trovato, e quindi ognuno dovrebbe avere probabilità 1/2 di trovare il suo nome...
Re: 50 PRIGIONIERI
No, puoi decidere in base ai risultati precedentigiorgia17 ha scritto:la scelta di ognuno è indipendente da quello che gli altri hanno trovato
Re: 50 PRIGIONIERI
Allora forse non ho capito il testo
Quindi i prigionieri sanno se i precedenti prigionieri hanno trovato il loro nome?
Quindi i prigionieri sanno se i precedenti prigionieri hanno trovato il loro nome?
Re: 50 PRIGIONIERI
Meglio, sanno di preciso cosa hanno trovato
Re: 50 PRIGIONIERI
Bh, allora...Ma, visto che così è troppo facile, vuol dire che ho sbagliato qualcosa...
Testo nascosto:
$T=\sqrt{\dfrac l g 12\pi}$
Re: 50 PRIGIONIERI
Ops, mi sono sbagliato nel mio messaggio precedente, scusate... comunque, i prigionieri (come effettivamente scritto nel testo) non sanno cosa hanno trovato gli altri, ma possono aprire le bottiglie ad una ad una scegliendo la bottiglia successiva in base a ciò che loro hanno trovato in precedenza
Scusate ancora l'errore
Scusate ancora l'errore