50 PRIGIONIERI

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

50 PRIGIONIERI

Messaggio da PIELEO13 » 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?
Ultima modifica di PIELEO13 il 23 lug 2016, 21:02, modificato 1 volta in totale.

Avatar utente
Drago96
Messaggi: 1114
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 50 PRIGIONIERI

Messaggio da Drago96 » 23 lug 2016, 14:13

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 » 23 lug 2016, 15:01

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: 49
Iscritto il: 05 feb 2015, 23:12

Re: 50 PRIGIONIERI

Messaggio da PIELEO13 » 31 lug 2016, 02:29

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: 3329
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: 50 PRIGIONIERI

Messaggio da fph » 31 lug 2016, 10:46

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: 49
Iscritto il: 05 feb 2015, 23:12

Re: 50 PRIGIONIERI

Messaggio da PIELEO13 » 31 lug 2016, 18:20

Si confermo quello che dici tu, le bottiglie vanno aperte una per volta, in effetti era impreciso

giorgia17
Messaggi: 6
Iscritto il: 03 mag 2016, 20:04

Re: 50 PRIGIONIERI

Messaggio da giorgia17 » 28 gen 2017, 18:04

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: 401
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 » 28 gen 2017, 18:36

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: 6
Iscritto il: 03 mag 2016, 20:04

Re: 50 PRIGIONIERI

Messaggio da giorgia17 » 28 gen 2017, 18:38

Allora forse non ho capito il testo :roll:
Quindi i prigionieri sanno se i precedenti prigionieri hanno trovato il loro nome?

matpro98
Messaggi: 401
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 » 28 gen 2017, 18:40

Meglio, sanno di preciso cosa hanno trovato

Avatar utente
RiccardoKelso
Messaggi: 108
Iscritto il: 25 ago 2015, 14:17
Località: Provincia di Milano

Re: 50 PRIGIONIERI

Messaggio da RiccardoKelso » 29 gen 2017, 14:01

E sanno anche dove trovare il loro biglietto!
Hai paura di bagnarti?

Non si può entrare nell'angolo rotture della lidl

$N_n=(n-1)(N_{n-1}+N_{n-2}), \space N_1=0, \space N_2=1$

Avatar utente
Sirio
Messaggi: 198
Iscritto il: 08 set 2016, 22:01

Re: 50 PRIGIONIERI

Messaggio da Sirio » 29 gen 2017, 17:41

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: 401
Iscritto il: 22 feb 2014, 18:42

Re: 50 PRIGIONIERI

Messaggio da matpro98 » 29 gen 2017, 17:47

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

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti