100 detenuti

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: 100 detenuti

Messaggio da 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 !
Enrico

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: 100 detenuti

Messaggio da 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
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: 100 detenuti

Messaggio da Gianfranco »

Lucignolo ha scritto:
sab mag 02, 2020 3:41 pm
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ì?
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: 100 detenuti

Messaggio da Gianfranco »

delfo52 ha scritto:
sab mag 02, 2020 3:16 pm
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.
Pace e bene a tutti.
Gianfranco

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: 100 detenuti

Messaggio da delfo52 »

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

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: 100 detenuti

Messaggio da 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
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: 100 detenuti

Messaggio da franco »

Gianfranco ha scritto:
ven mag 01, 2020 5:15 pm
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"
Ultima modifica di franco il dom mag 03, 2020 2:23 pm, modificato 1 volta in totale.
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: 100 detenuti

Messaggio da delfo52 »

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

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: 100 detenuti

Messaggio da Lucignolo »

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

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: 100 detenuti

Messaggio da 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 :(
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: 100 detenuti

Messaggio da 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
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: 100 detenuti

Messaggio da Gianfranco »

franco ha scritto:
dom mag 03, 2020 7:36 pm
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).
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: 100 detenuti

Messaggio da Gianfranco »

Lucignolo ha scritto:
lun mag 04, 2020 10:18 am
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.
Pace e bene a tutti.
Gianfranco

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: 100 detenuti

Messaggio da franco »

Gianfranco ha scritto:
lun mag 04, 2020 10:51 am
franco ha scritto:
dom mag 03, 2020 7:36 pm
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
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Rispondi