50 PRIGIONIERI

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
PIELEO13
Messaggi: 58
Iscritto il: 05 feb 2015, 23:12

50 PRIGIONIERI

Messaggio da PIELEO13 »

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?
Ultima modifica di PIELEO13 il 23 lug 2016, 21:02, modificato 1 volta in totale.
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 50 PRIGIONIERI

Messaggio da Drago96 »

Youtube dice che almeno 2 milioni di persone sanno la soluzione :lol:
Comunque è un bel problema! :D
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Re: 50 PRIGIONIERI

Messaggio da polarized »

Drago96 ha scritto:Youtube dice che almeno 2 milioni di persone sanno la soluzione :lol:
Comunque è un bel problema! :D
La stessa cosa che ho pensato quando lo ho letto :D :lol: :lol:
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia
PIELEO13
Messaggi: 58
Iscritto il: 05 feb 2015, 23:12

Re: 50 PRIGIONIERI

Messaggio da PIELEO13 »

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ì!
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: 50 PRIGIONIERI

Messaggio da fph »

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]
PIELEO13
Messaggi: 58
Iscritto il: 05 feb 2015, 23:12

Re: 50 PRIGIONIERI

Messaggio da PIELEO13 »

Si confermo quello che dici tu, le bottiglie vanno aperte una per volta, in effetti era impreciso
giorgia17
Messaggi: 34
Iscritto il: 03 mag 2016, 20:04

Re: 50 PRIGIONIERI

Messaggio da giorgia17 »

PIELEO13 ha scritto:Sapreste trovarla?
No, non saprei da dove cominciare :D :roll:

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...
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 »

giorgia17 ha scritto:la scelta di ognuno è indipendente da quello che gli altri hanno trovato
No, puoi decidere in base ai risultati precedenti
giorgia17
Messaggi: 34
Iscritto il: 03 mag 2016, 20:04

Re: 50 PRIGIONIERI

Messaggio da giorgia17 »

Allora forse non ho capito il testo :roll:
Quindi i prigionieri sanno se i precedenti prigionieri hanno trovato il loro nome?
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 »

Meglio, sanno di preciso cosa hanno trovato
RiccardoKelso

Re: 50 PRIGIONIERI

Messaggio da RiccardoKelso »

E sanno anche dove trovare il loro biglietto!
Avatar utente
Sirio
Messaggi: 317
Iscritto il: 08 set 2016, 22:01

Re: 50 PRIGIONIERI

Messaggio da Sirio »

Bh, allora...
Testo nascosto:
Il primo sceglie i primi 25 e se non trova il suo nome, amen, è un 50% che se ne va, altrimenti se non trova il nome del secondo allora il secondo sceglie gli altri 25 e, da lì in poi, tutti sanno dov'è di preciso il loro nome, altrimenti il secondo sceglie il proprio nome, visto che sa dov'è, e poi gli ultimi 24 ed anche qui tutti sanno dov'è il loro nome, anche il 26esimo che non l'ha visto uscire dalla bottiglia perché va ad esclusione.
Ma, visto che così è troppo facile, vuol dire che ho sbagliato qualcosa...
$T=\sqrt{\dfrac l g 12\pi}$
matpro98
Messaggi: 479
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 »

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
Rispondi