50 PRIGIONIERI
Inviato: 22 lug 2016, 18:56
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?
