La liberazione degli ostaggi
Su un testo di divulgazione scientifica ho letto un problema che mi ha incuriosito: sono tenuti prigionieri 1000 ostaggi, ciascuno dei quali lancia 10 monete contemporaneamente a tutti gli altri. Chi ottiene 10 teste viene liberato, gli altri continuano a tentare la sorte. Dopo quanti tentativi saranno liberi metà degli ostaggi ?
Il testo riporta il risultato: dopo 710 tentativi, pari a $ln(2)*1024$, ma non riporta il procedimento per ottenerlo.
Ho provato a formalizzare il problema, siano quindi:
$Q = 1000$ il numero degli ostaggi,
$N >= 0$ il numero di tentativi, ovvero il lancio delle monete da parte degli ostaggi ancora prigionieri,
$1/1024$ la probabilità di ottenere 10 teste con un lancio, ovvero di ottenere la libertà.
Allora per ogni valore di N si ha una distribuzione cumulativa discreta di probabilità $C(X)$ da $Q$ in $[0,..,1]$ che associa ad ogni $0 <= X <= Q$ la probabilità di avere meno di $X$ ostaggi prigionieri.
La domanda del testo potrebbe essere riformulata così: "per quale $N$ si ha $C(Q/2) > K$ con $K$ abbastanza vicino ad 1, ad esempio $K = 0,99$ ?"
Oltre non sono riuscito ad andare. Ringrazio chiunque volesse aiutarmi a trovare la funzione $C(X)$ e ad interpretare la soluzione $ln(2)*1024$
Il testo riporta il risultato: dopo 710 tentativi, pari a $ln(2)*1024$, ma non riporta il procedimento per ottenerlo.
Ho provato a formalizzare il problema, siano quindi:
$Q = 1000$ il numero degli ostaggi,
$N >= 0$ il numero di tentativi, ovvero il lancio delle monete da parte degli ostaggi ancora prigionieri,
$1/1024$ la probabilità di ottenere 10 teste con un lancio, ovvero di ottenere la libertà.
Allora per ogni valore di N si ha una distribuzione cumulativa discreta di probabilità $C(X)$ da $Q$ in $[0,..,1]$ che associa ad ogni $0 <= X <= Q$ la probabilità di avere meno di $X$ ostaggi prigionieri.
La domanda del testo potrebbe essere riformulata così: "per quale $N$ si ha $C(Q/2) > K$ con $K$ abbastanza vicino ad 1, ad esempio $K = 0,99$ ?"
Oltre non sono riuscito ad andare. Ringrazio chiunque volesse aiutarmi a trovare la funzione $C(X)$ e ad interpretare la soluzione $ln(2)*1024$
Risposte
Grazie dell'ottimo suggerimento, mi sono complicato inutilmente la vita pensando alla probabilità: si assume implicitamente che sia "certa" la liberarazione di $1/1024$ ostaggi ad ogni lancio e si ottiene un'ottima un'approssimazione del risultato.
Credo che sarebbe però necessario ragionare in termini probabilistici con numeri molto più piccoli, ad esempio 2 ostaggi che lanciano una moneta ciascuno: dopo il primo tentativo avremmo 2 ostaggi con probabilità $1/4$, un ostaggio con probabilità $1/2$, nessuno con probabilità $1/4$, e così via.
Credo che sarebbe però necessario ragionare in termini probabilistici con numeri molto più piccoli, ad esempio 2 ostaggi che lanciano una moneta ciascuno: dopo il primo tentativo avremmo 2 ostaggi con probabilità $1/4$, un ostaggio con probabilità $1/2$, nessuno con probabilità $1/4$, e così via.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo