100 detenuti

[delfo52]

è interessante vedere come, di fronte ad un problemino tutto sommato facile, che si descrive in poche righe, gente preparata come voi, con tecniche informatiche simili, arriva a risultati così difformi.
In queste ore in cui si discute, per la fase 2 e la riapertura, sulla validità degli algoritmi usati dagli esperti per fare simulazioni e proiezioni, la cosa , più che interessante, diviene inquietante !

[Lucignolo]

il test fatto sulla prima soluzione che avete dato mi ha dato una media di estrazioni di 10.000 per arrivare a conteggiare 100 ingressi sicuri

ho fatto ulteriori analisi e test sviluppando un altra idea che migliora la prima

e sono arrivato a trovare un sistema con una media di 2000 estrazioni

chi offre di meno D:

[Gianfranco]

ho fatto ulteriori analisi e test sviluppando un altra idea che migliora la prima

Ho cercato questo problema in rete (ovviamente senza guardare la soluzione) e ne ho trovato una versione in cui viene fatta un'estrazione al giorno e i prigionieri lo sanno.
Forse questa informazione può aiutare a migliorare l'algoritmo(?).
Lucignolo, nella tua versione dichiari che i prigionieri non conoscono il ritmo delle estrazioni. Confermi che è così?

[Gianfranco]

In queste ore in cui si discute, per la fase 2 e la riapertura, sulla validità degli algoritmi usati dagli esperti per fare simulazioni e proiezioni, la cosa , più che interessante, diviene inquietante !

E' vero. Ho seguito fin dall'inizio le analisi matematiche di Federico Ricci-Tersenghi e di Emanuele Paolini su Facebook e mi sembra di aver capito che gli algoritmi validi non mancano e si devono scegliere in base ai dati che abbiamo a disposizione. Purtroppo è evidente che i dati a cui si può accedere sono inadeguati o peggio inaffidabili.
E ogni giorno sentiamo ai telegiornali giornalisti che leggono frettolosamente liste di numeri e le commentano con frasi fatte che non saprei definire.
Aspetto l'app.

[delfo52]

consiglio anche Fausto Tomei e il prof De Nicolao, come analisti. Ho mandato a Gianfranco alcune mie riflessioni, sperando non abbia cambiato indirizzo

[Lucignolo]

nella versione che ho proposto vi sono alcune precisazioni una della quali recita cosi

Precisazioni:
_i detenuti non sanno quando un altro detenuto viene chiamato e non sanno se le estrazioni vengono fatte a tempi regolari

certo se facessero una estrazione al giorno per la media di 10.000 estrazioni.... sarebbero 27 anni...

penso che fare una estrazione al giorno cmq potrebbe cambiare tutto il ragionamento... magari in meglio?

meditiamo anche su questa nuova ipotesi come fosse un nuovo indovinello!

[franco]

Bello questo problema, grazie Lucignolo!
Credo che non sia -ancora- nell'archivio di BASE Cinque.
Ho ripassato il problema del collezionista (coupon collector) che credo sia equivalente a questo.
Se non erro, il numero atteso di estrazioni per chiamare tutti i prigionieri è:
3 prigionieri -> 5,5 estrazioni
100 prigionieri -> 518,7... estrazioni
Naturalmente questo è un valore medio perciò le estrazioni in realtà possono variare da n. prigionieri all'infinito(?).
In generale, se il numero dei prigionieri è n, il numero atteso di estrazioni E(n) è:
$\large E(n)=\sum_{i=1}^n {\frac{1}{i}} $
---
Non ho fatto progressi nella soluzione del problema, ma questi numeri possono aiutare a valutare l'efficienza di un strategia.

Ho provato a ragionare in questa maniera ...
Sappiamo che il numero atteso di estrazioni perchè vengano chiamati tutti i 100 detenuti è circa 519 (come detto sopra da Gianfranco).
A questo punto dobbiamo stimare quando sarà chiamato per la prima volta il detenuto A che è quello che fa partire l'uso della lampadina (sino ad allora spenta).
A potrebbe essere il primo estratto o l'ultimo, o uno intermedio.
Se faccio la media di tutti i "momenti attesi di prima estrazione di un carcerato" ottengo esattamente 100!
Il calcolo l'ho fatto con excel ma credo possa essere espresso analiticamente sotto forma di sommatoria.

Concludendo, ammesso e non concesso che non siano tutte fesserie (cosa che non escluderei), a me risulterebbe che occorrono in media circa 619 (in realtà 618,7378...) estrazioni prima del "liberi tutti":


Applicando lo stesso concetto al caso di 3 detenuti, le estrazioni necessarie sarebbero 8,5.

Edit: ho rimosso degli allegati sbagliati che per qualche motivo erano rimasti "appesi"

[delfo52]

qualsiasi risultato numerico che comincia con 618...DEVE essere fibonaccianamente, aureo. quindi, a furor di Delfo, 6180339...

[Lucignolo]

ma chi conta le estrazioni per urlare "son passati tutti" ?

[franco]

I detenuti si accordano su un loro rappresentante, chiamiamolo Alberto per comodità.
Se il mio ragionamento è corretto, ci si deve attendere che passino 100 estrazioni prima che venga chiamato e, quindi, accenda per le prima volta la lampadina.
Da allora Alberto comincia a accendere e spegnere le lampadine.
Questa seconda fase ha una durata attesa di circa 518,7 estrazioni (per avere a giro tutti i detenuti estratti) che sommate alle 100 necessarie per arrivare alla prima chiamata di Alberto fanno 618,7.
....
Così almeno pensavo prima di mettermi a scrivere.
Mi rendo però conto ora che è tutto una fesseria
Perchè Alberto possa tenere il conto, deve essere estratto dopo ognuno dei detenuti che hanno spento la lampadina.
Le estrazioni aumentano in maniera colossale

[Lucignolo]

la mia soluzione migliore è questa:

il primo che arriva a contare di essere entrato 25 volte dice: "siamo passati tutti"
ho fatto dei test su 100.000 combinazioni casuali è si salvano sempre tutti
la media delle estrazioni è di 2000

[Gianfranco]

Le estrazioni aumentano in maniera colossale

A spanne, Alberto deve contare 100 spegnimenti e viene estratto in media ogni 100 volte: se tutto va bene fanno circa 10.000 estrazioni.

Per diminuire il tempo di attesa si potrebbe aumentare il numero delle persone che "contano gli spegnimenti" ma non possono comunicare fra loro, quindi...

Lancio qui un'idea che potrebbe ridurre a 2500 estrazioni medie ma con una probabilità di riuscita stimata pari a 0,9999 (aumentabile, volendo):

a) ogni detenuto, per UNA SOLA VOLTA, accende la luce quando la trova spenta.
b) ogni detenuto, spegne la luce TUTTE LE VOLTE che la trova accesa.

In questo modo, la luce verrà accesa 100 volte ma chiunque potrà spegnerla.
E' come dire che ogni persona lascia un'impronta digitale una sola volta ma tutte le persone cancellano le impronte.
Da un certo punto in avanti non ci saranno più impronte, ovvero la lampadina rimarrà sempre spenta.
Ma come si fa a sapere che TUTTI hanno lasciato un'impronta e che le impronte sono state tutte ripulite?
A questo provvede Alberto che fa la parte della "sentinella": controlla che la lampadina rimanga spenta per un ragionevole numero di cicli consecutivi e poi si prende la responsabilità di dire che sono passati tutti.
Secondo la mia stima, se Alberto vede la lampadina spenta per 20 volte consecutive, il tempo di attesa è circa 2500 estrazioni e la probabilità che siano passati tutti è circa 0,9999

Purtroppo, con questo metodo non c'è la sicurezza matematica.
I carcerati devono trovare un equilibrio tra la vincita (libertà) e la posta in gioco (tempo di attesa in prigione).

[Gianfranco]

la mia soluzione migliore è questa:
il primo che arriva a contare di essere entrato 25 volte dice: "siamo passati tutti"
ho fatto dei test su 100.000 combinazioni casuali è si salvano sempre tutti
la media delle estrazioni è di 2000

Ho visto ora questa tua soluzione, dopo averne postata una che prevede in media 2500 prove.
Che dire?
La tua, come pure la mia, non hanno la certezza matematica di successo ma solo una probabilità molto alta.
Potresti dirci qual è la probabilità di successo della tua soluzione e come hai fatto a valutarla?

Se hai provato 100.000 combinazioni casuali, secondo me sono troppo poche.
Le combinazioni con ripetizione di 100 elementi a gruppi di 2000 sono dell'ordine di 10^70 e tu ne hai provato solo 10^5.

[franco]

Le estrazioni aumentano in maniera colossale

A spanne, Alberto deve contare 100 spegnimenti e viene estratto in media ogni 100 volte: se tutto va bene fanno circa 10.000 estrazioni.

10518,74