Newsgroup: it.hobby.enigmi
Titolo: Cento prigionieri e una lampadina

(L'ho trovato su un forum di lingua inglese)
Cento prigionieri vengono portati in un carcere di massima sicurezza,
dove verranno rinchiusi ciascuno in una cella isolata e insonorizzata,
senza alcuna possibilità di comunicare fra loro. Prima, però, vengono
radunati in cortile dove il direttore del carcere spiega loro le regole
della struttura.
Nel carcere esiste una stanza centrale, che contiene una lampadina con
il suo interruttore. Ogni mattina, un prigioniero _scelto assolutamente
a caso_ verrà condotto nella stanza centrale, dove potrà (se lo
vuole) accendere o spegnere la lampadina. Poi gli verrà chiesto se
tutti e cento i prigionieri sono stati almeno una volta in quella
stanza. Se la sua risposta sarà "sì", ed è vero, i prigionieri
verranno tutti liberati. Se la sua risposta sarà "sì", ma è falso, i
prigionieri verranno tutti fucilati. Se risponderà "no", o "non so",
verrà semplicemente ricondotto in cella.
Prima di essere portati nelle celle, i prigionieri hanno un'ora di
tempo per discutere insieme un'eventuale strategia.
Sapendo che:
-la lampadina è inizialmente spenta.
-i guardiani del carcere non modificano mai lo stato della lampadina.
-i prigionieri non possono lasciare oggetti, o tracciare segni, nella
stanza.
-i prigionieri non possono toccare la lampadina.
-se la lampadina si fulmina, viene sostituita con una nuova (che viene
lasciata nello stesso stato della lampadina precedente).
Ci si chiede:
-Qual è un metodo per poter essere sicuri al 100% di dare una risposta
affermativa?
-Si può ottimizzare questo metodo?
-Variante: e se lo stato iniziale della lampadina fosse sconosciuto?

a caso_ verrà condotto nella stanza centrale
I prigionieri possono essere portati piu volte nella stanza prima che
tutti e 100 siano stati condotti li? Ad esempio il primo giorno viene
scelto il primo prigioniero e il secondo giorno sempre il primo
prigioniero.
--
SisQo

Il raccattapalle wrote:

s
p
o
i
l
e
r
ogni prigioniero accenderà o spegnerà la lampada solo la prima volta.
dopo che la lampada si sarà accesa 50 e spenta 50 volte, chiunque verrà
richiamato risponderà si e tutti saranno liberi.

<Il raccattapalle> ha scritto:

S
P
O
I
L
E
R
|
|
|
|
|
|
|
|
I prigionieri possono organizzare la conta di coloro che entrano per la 
prima volta nella stanza centrale affidandola ad uno di loro.
Chi entra nella stanza e trova la lampadina spenta la accende, ma solo se 
entra per la prima volta.
Chi la trova già accesa, non la tocca.
Quando arriva il turno del rilevatore designato, se trova la lampadina 
accesa, entra in possesso dell'informazione che un altro prigioniero è 
entrato almeno una volta.
Quando il rilevatore designato arriva a 100 pronuncia il fatidico "Sì"
Ci vorrà un po', però!
----
Ciao, plinius 

prima volta nella stanza centrale affidandola ad uno di loro.
Stando al testo del gioco i prigionieri non possono assolutamente
comunicare tra di loro e sono isolati da tutto quindi nessuno sa chi
viene portato nella stanza.

 richiamato risponderà si e tutti saranno liberi.
Non funziona.
Se uno entra e la trova spenta, come fa a sapere quante volte in
passato e' stata accesa e spenta?

 Ci vorrà un po', però!
Giusto!!
Ma adesso:
1) Sapresti calcolare (statisticamente o con un programma) quanti
giorni ci vorranno in media con questa strategia?
2) Puoi ottimizzare la strategia? Esiste un modo per guadagnare tempo!
Ciao

 viene portato nella stanza.
"Prima di essere portati nelle celle, i prigionieri hanno un'ora di
tempo per discutere insieme un'eventuale strategia".
In quest'ora, ovviamente, possono designare uno di loro come
rilevatore.
Ciao

"Il raccattapalle"  ha scritto nel messaggio
(L'ho trovato su un forum di lingua inglese)
Cento prigionieri vengono portati in un carcere di massima sicurezza,
dove verranno rinchiusi ciascuno in una cella isolata e insonorizzata,
senza alcuna possibilità di comunicare fra loro. Prima, però, vengono
radunati in cortile dove il direttore del carcere spiega loro le regole
della struttura.
----------------------------------------------------------
Mi sembra che questo quesito sia già stato esaminato su IHE...
Comunque, se si vuole la certezza (al 100%), occorre stabilire un
prigioniero-contatore (che conterà le volte che trova la lampada accesa
quando è il suo turno di entrare nella stanza; all'uscita spegnerà
la lampada che verrà accesa dal primo prigioniero che vi entrerà
per la prima volta).
Ma in teoria potrebbero morire tutti in galera prima di avere tale
certezza, cioè che il prigioniero-contatore trovi per 100 volte la
lampada accesa (dovrebbero passare in media 30 anni...), senza contare
che potrebbe anche non essere scelto mai casualmente per tutte le
volte necessarie (nella durata della vita).
I prigionieri amano la libertà (di cui sono stati privati) e certamente
sono pronti a barattarla con un valore (purchè esiguo) di probabilità
di essere uccisi (perchè sbagliano a dire che tutti e 100 sono stati
scelti).
Io penso che una probabilità negativa di un milionesimo di sbagliare
possa essere accettata (io l'accetterei senz'altro); quindi, senza
calcoli e strategie, diranno SI' dopo 3 anni e 9 mesi... (ammesso
che il direttore del carcere non sia figlio di mig****a e scelga
veramente a caso).
Ciao, Nino 


Certo.
E' possibile (anche se improbabile) che uno stesso prigioniero venga
scelto per cento giorni consecutivi.
E' anche possibile (anche se improbabile) che un particolare
prigioniero non venga scelto per anni e anni.
Ciao

 volte necessarie (nella durata della vita).
Statisticamente verrebbe scelto una volta ogni 100 giorni. La scelta è
casuale, non dipende dalla cattiveria (o dalla bontà) del direttore
del carcere o dei guardiani.
Diciamo che è il risultato del tiro di un dado a 100 facce.
Ciao

Il raccattapalle wrote:

non hai detto che dalla cella non era possibile vedere la lampadina :))))

 Diciamo che č il risultato del tiro di un dado a 100 facce.
O dell'estrazione di 100 numeri con reimbussolamento.
Ciao, Nino

 2) Puoi ottimizzare la strategia? Esiste un modo per guadagnare tempo!
Certo, il rilevatore non si designa a priori, ma si designa in base al
giorno in cui è chiamato nella cella.
Ossia, è meglio ad esempio che il rilevatore sia colui che è chiamato il
secondo giorno, molto probabilmente almeno due prigionieri sono già
contati il secondo giorno.
-- 
Emilio? Voil'him!
Ateo ed anarchico per grazia di Dio e volonta' della Nazione.
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 > 2) Puoi ottimizzare la strategia? Esiste un modo per guadagnare tempo!
Anzi, meglio.
Il primo giorno chi entra nella cella accende la luce.
Il secondo giorno, se chi entra nella luce non è lo stesso del primo
giorno, spegne la luce.
Il terzo giorno chi entra è il rilevatore in ogni caso, ossia, chi è
chiamato il terzo giorno prende l'incarico di fare da rilevatore, se trova
la luce spenta, sa che prima di lui sono passate due persone, se la trova
accesa sa che è passata di li' solo una persona, se lui è già passato di
li' sa che non deve contarsi due volte.
In questa prima passata insomma generalmente, nella stragran parte dei
casi  il rilevatore ha già contato 3 prigionieri.
I prigionieri già entrati nei primi 3 giorni ovviamente ai fini della
strategia si riterranno già contati e non faranno nulla.
Il rilevatore a questo punto spegne in ogni caso la luce.
POi tutto come prima.


 O dell'estrazione di 100 numeri con reimbussolamento.
100 è una parolona, 99 nel caso peggiore (1 caso su 10mila) , 97 in quello
più favorevole (9702 probabilità su 10mila) e 98 nel caso intermedio
(probabilità di 297 su 10mila).
Quindi peserei con questi pesi il risultato che hai calcolato con 100
ottenendo 25,78 anni.


 Puoi ottimizzare la strategia? Esiste un modo per guadagnare tempo!
Si può migliorare così.
I prigionieri si accordano di stabilire che diventerà contatore
colui che per primo entrerà nella stanza per la seconda volta.
In pratica, il primo che entra nella stanza il primo giorno, accende
la lampadina (o la lascia accesa se si inizia con la lampada accesa);
il secondo, se è diverso dal primo, la lascia accesa, e così gli altri
che seguiranno uno ogni giorno.
Prima o dopo arriverà un prigioniero che è scelto per la seconda
volta, diventerà il contatore e  provvederà a spegnere la lampadina.
Logicamente, potrà calcolare dal numero di giorni che sono passati
dall'inizio, quanti prigionieri diversi sono già entrati nella stanza
(N-1 giorni passati dall'inizio della prova).
Da questo momento, il gioco prosegue secondo la procedura normale
(accendere la lampada quando si entra per la prima volta e lasciarla
sempre accesa finchè arriva il prigioniero-contatore, che annota +1
e spegne la lampada).
In tal modo, la durata media dovrebbe ridursi da 27 a circa 24 anni.
Ciao, Nino


Vediamo. Il prigioniero-contatore sia fissato a priori.
Il tempo minimo si ha se entra uno, poi il contatore, poi un altro che non
è il primo, poi il contatore, ecc..
Con N prigionieri sarà 2(N-1) = 198 giorni per N=100
Il tempo massimo può evidentemente essere infinito.
Ma quale può essere il tempo medio (da me approssimato a N*N)?
Si hanno N persone: la probabilità del primo turno è (N-1)/N   e l'attesa
N/(N-1); poi deve entrare il contatore, che ha probabilità 1/N   e
attesa N.
A questo punto deve entrare uno degli altri (N-2) prigionieri validi,
con un'attesa N/(N-2) e quindi ancora il contatore con attesa N.
Si deve procedere fino alla fine, quando l'attesa sarà N sia per l'ultimo
prigioniero che per il contatore.
Il tempo medio per tutti gli N prigionieri inframezzati dal contatore
sarà quindi dato dalla sommatoria di N/i con i da 1 a (N-1) + le attese
del contatore che sono N*(N-1).
Sono arrugginito per la prima parte, comunque il totale dovrebbe essere
un po' di più di N + N(N-1) , cioè di N*N.
Quindi, la media che avevo indicato per N=100 (27,3 anni) mi sembra
attendibile (in leggero difetto), e comunque più corretta della tua.
Ciao, Nino 


Ma non va bene... perchè gli altri non possono sapere chi è il
primo estratto due volte e che sarà il contatore...
Nino 

 Vediamo. Il prigioniero-contatore sia fissato a priori.
Non lo fisso a priori, ma è il prigioniero che viene chiamato il TERZO
giorno.
Non ho fatto gli altri calcoli, ma ho solo ridotto il sistema da N=100 a
tre sistemi con N=97, N=98 o N=99 con diverse probabilità.
Devi vedere i miei post in cui spiego appunto una variante per ridurre il
tempo medio.


 tempo medio.
Supponiamo di partire a valutare il tempo medio quando ci sono ancora
97 prigionieri (con il contatore che deve verificarne l'ingresso nella
stanza):
il tempo medio sarà = sommatoria di 96/i (con i da 1 a 96) +
+ 96*100 = 514,67 + 9600 = 10115 giorni  circa 27,69 anni


No, il ragionamento è giusto. Basta solo una piccola modifica. :-)
Si decide che i primi 100 giorni verranno "spesi" per determinare chi
sarà il contatore (che, come hai suggerito, sarà il primo che
entrerà per la seconda volta nella stanza).
Chi entra il primo giorno lascia spenta la lampadina (o la spegne se
era accesa).
Chi entra nei giorni successivi la lascia spenta se sta entrando per la
prima volta. Chi entra per la seconda volta, la accende e diventa
ufficialmente il contatore. In questo modo, se è il giorno n, sa di
aver già contato n-1 prigionieri compreso se stesso.
Fino al centesimo giorno, poi, si lascia la lampadina accesa e chi
entra non fa più nulla. Se chi entra il centesimo giorno la trova
ancora spenta, allora può dichiarare che tutti sono entrati una volta,
ma è un caso particolarmente fortunato. Altrimenti la spegne.
Dal giorno 101 si procede come da soluzione standard. Però chi era
entrato nei primi 100 giorni e aveva trovato la lampadina spenta sa di
essere già stato contato.
In questo modo si riduce notevolmente il tempo di conteggio. Per sapere
di quanto, bisognerebbe calcolare quante estrazioni in media ci
vogliono prima che un numero venga estratto due volte.
E comunque, anche questo metodo è ulteriormente migliorabile :-)
Ciao

 Ciao
Sono curioso di saperlo, ci penserò ancora un po'
Ciao, Nino

 Sono curioso di saperlo, ci penserò ancora un po'
Buone notizie per i prigionieri!
Ho studiato un metodo che dovrebbe consentir loro di uscire di prigione in 
pochissimi anni, ma devo ancora ottimizzare i tempi.
A presto!
plinius 

<Il raccattapalle> ha scritto:

Quando <Il raccattapalle> ha proposto questo quesito, mi sono detto: c'è una 
sola lampadina - on/off - quindi una sola informazione può essere passata. 
Dunque nominiamo un rilevatore, aspettiamo che passi per la stanza almeno 99 
volte e raccolga l'informazione delle 99 presenze ed il gioco è fatto.
Abbiamo visto però che questo procedimento richiede, più o meno, 99*100 
giorni, cioè più di 27 anni!
Ho continuato allora a pensare se non fosse possibile diminuire il tempo 
necessario al trasferimento delle informazioni ad un unico prigioniero.
L'idea che ho avuto mi è sembrata inizialmente molto funzionale ma poi, a 
conti fatti, si è rivelata in parte deludente.
Ma vediamo come funziona.
SISTEMA DEL LASCIA O RADDOPPIA
Partiamo, per semplicità, da un numero di prigionieri pari ad una potenza di 
2 (facciamo 128).
FASE 1
Ogni prigioniero che accede alla stanza centrale:
- se trova la lampadina spenta lascia nella stanza la propria presenza 
accendendo la lampadina. A partire da quel momento non dispone più della 
propria presenza e non farà mai più nulla.
- se trova la luce accesa ed egli stesso dispone ancora della propria 
presenza, spegne la luce per prelevare la seconda presenza e, quindi, ne 
accumula 2.
- se un prigioniero che non dispone più della propria presenza torna di 
nuovo nella stanza centrale, non farà assolutamente nulla.
- se un prigioniero che dispone già della presenza raddoppiata torna di 
nuovo nella stanza centrale, non farà assolutamente nulla.
Alla fine della fase 1 (che deve durare un tempo t1 predeterminato in modo 
da dare una buona probabilità che tutte le presenze siano trasferite) avremo 
64 prigionieri privi di presenza e 64 prigionieri che ne hanno 2
FASE 2
Comportamento dei prigionieri identico a quello della fase 1 ma, per tutto 
il tempo t2 di durata della fase, i trasferimenti hanno valore pari a 2 
presenze.
Alla fine della fase 2 (che deve durare un tempo t1 predeterminato in modo 
da dare una buona probabilità che tutte le presenze siano trasferite) avremo 
che 32 prigionieri dispongono ciascuno di 4 presenze.
FASE 3
Durata t3. Valore trasferimenti 4. Termina con 16 prigionieri che dispongono 
di 8 presenze ciascuno.
FASE 4
Durata t4. Valore trasferimenti 8. Termina con 8 prigionieri che dispongono 
di 16 presenze ciascuno.
FASE 5
Durata t5. Valore trasferimenti 16. Termina con 4 prigionieri che dispongono 
di 32 presenze ciascuno.
FASE 6
Durata t6. Valore trasferimenti 32. Termina con 2 prigionieri che dispongono 
di 64 presenze ciascuno.
FASE 7
Durata t7. Valore trasferimenti 64. Termina con 1 prigioniero che dispone di 
128 presenze.
Ho provato a determinare dei valori funzionali per i tempi t1, t2, ...,t7 ma 
il calcolo delle probabilità mi ha suonato ben bene ed ho ripiegato sulla 
simulazione al computer:
 Fase    MIN      MAX      MEDIA
   1     361     1793     698.86   % < di 1100 gg.: 97.50
   2     284     1626     608.68   % < di 1000 gg.: 97.17
   3     152     1719     519.10   % < di  920 gg.: 97.93
   4     108     1442     433.51   % < di  800 gg.: 96.87
   5      58     1639     347.82   % < di  750 gg.: 97.62
   6      12     1282     267.37   % < di  700 gg.: 98.43
   7       2     1378     193.04   % < di  580 gg.: 97.90
Se scegliessimo questi tempi, le possibilità di successo sarebbero pari 
all'84,55% (97,50*97,17*97,93*96,87*97,62*98,43*97,90).
Se avessimo successo al primo tentativo, quindi, impiegheremmo 5850 giorni, 
(1100+1000+920+800+750+700+580), cioè circa 16 anni.
Ma, considerando che nel 15,45% dei casi dovremo ripetere tutto il ciclo 
dell 7 fasi, e poi di nuovo, ecc. ecc., dobbiamo considerare che il tempo 
medio effettivo sarebbe
5850 + 5850*0,1545 + 5850*0,1545^2 + 5850*0,1545^3 + ..... =
= 5850 / 0,1545 = 6919 giorni (quasi 19 anni)
Non è che non ci sia una riduzione rispetto all'altro metodo (anche 
considerando che questo calcolo è riferito a 128 prigionieri e non a soli 
100) ma, francamente, mi aspettavo qualcosa di meglio.
Probabilmente si può lavorare ancora sulla ottimizzazione dei tempi di 
durata delle varie fasi, se qualcuno ne ha voglia... (io non più!)
Altra analisi merita l'adattamento del sistema ai 100 prigionieri (o anche a 
qualunque altro numero che non sia potenza di 2).
Un metodo potrebbe essere (ma allunga ovviamente i tempi) quello di 
aggiungere in coda una fase per i resti.
Per i 100 prigionieri avremmo:
Fase 1: 100x1 -> 50x2
Fase 2:  50x2 -> 25x4
Fase 3:  25x4 -> 12x8 + resto 1 (da  4)
Fase 4:  12x8 -> 6x16
Fase 5:  6x16 -> 3x32
Fase 6:  3x32 -> 1x64 + resto 1 (da 32)
a questo punto l'unico detentore, sapendo che esistono 2 resti, prima di 
annunciare il "sì" spetta una ulteriore fase per verificare la presenza del 
corretto numero di resti
Fase 7:  2 resti = LIBERTA' !!!!!!!!!!!!!!!!!!
In buona sostanza per 100 prigionieri occorrerebbe lo stesso tempo 
necessario ai 128 di capienza massima per 7 fasi.
Beh! sempre meglio di 27 anni, però!
----
Ciao, plinius

 necessario ai 128 di capienza massima per 7 fasi.
Si può passare da 128 a 100 in un altro modo:
Uno dei prigionieri non parte con 1 presenza, ma con 29.
Depositerà 1 presenza nella fase 1, 4 presenze nella fase 3, 8
presenze nella fase 4, e 16 presenze nella fase 5.
In questo modo, la fase 7 non è necessaria. Si risparmiano molti
giorni!
C'è qualche programmatore che ha voglia di fare un po' di simulazioni
con i diversi metodi? :-)

 con i diversi metodi? :-)
----
plinius 

 fuorigioco per  rientrare solo nella fase 3 (in cui gli scambi sono da 4.
Dunque, funzionerebbe così:
Nella fase 1 sono in gioco solo 96 prigionieri (e si termina con 48 che
valgono 2)
Nella fase 2 sono in gioco 48 (e si termina con 24 che valgono 4)
Nella fase 3 sono in gioco 24+2 che entrano solo ora (e termina con 13
che valgono 8)
Nella fase 4 sono in gioco 13+1 che entra solo ora (e termina con 7 che
valgono 16)
Nella fase 5 sono in gioco 7+1 che entra solo ora (e termina con 4 che
valgono 32)
Nella fase 6 sono in gioco 4 (e termina con 2 che valgono 64)
Nella fase 7 sono in gioco 2 (e la fase termina con uno che vale 128:
libertà!)
Secondo me, comunque, le durate che hai calcolato per le singole fasi
sono un po' esagerate. Forse accorciandole si guadagnerebbe un po' di
tempo. E' vero che cresce il rischio di dover fare un secondo ciclo, ma
credo che la durata media complessiva calerebbe, anche considerando che
il secondo ciclo può durare meno del primo.
Ciao

<Il raccattapalle> ha scritto:
[cut]
Dunque, facendo una "con-fusione" dei nostri ragionamenti, per i 100 
prigionieri potremmo riepilogare così:
Intesa iniziale:
1 - si fissano i tempi t1, t2, t3, t4, t5, t6, t7 per le fasi del CICLO_1
2 - si fissa un tempo tr valido per ciascuna le fasi dei cicli successivi al 
primo
3 - si individuano 2 prigionieri che partono con 4 presenze
4 - si individua 1 prigioniero che parte con 8 presenze
5 - si individua 1 prigioniero che parte con 16 presenze
CICLO 1
----------------------------------------------
|  |New|presenze|Ca|Distribuzione a fine fase|
|Fa|en-|trasfe- |du|-------------------------|
|se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
----------------------------------------------
| 1|   | 96 x  1|  |    |   |   |   |  |  |48|
| 2|   | 48 x  2|  |    |   |   |   |  |24|  |
| 3| 2 | 26 x  4|  |    |   |   |   |13|  |  |
| 4| 1 | 14 x  8|  |    |   |   | 7 |  |  |  |
| 5| 1 |  8 x 16|  |    |   | 4 |   |  |  |  |
| 6|   |  4 x 32|  |    | 2 |   |   |  |  |  |
| 7|   |  2 x 64|  |  1 |   |   |   |  |  |  |
----------------------------------------------
Eventuali mancati passaggi in una qualunque delle fasi possono essere 
determinati:
1 - dal fatto che uno dei prigionieri che detiene presenze non sia 
sorteggiato e perciò non possa depositare le sue presenze: il prigioniero sa 
di non aver depositato 2^(f-1) presenze e si farà carico di depositarle 
nella appropriata fase del CICLO_2
2 - dal fatto che un deposito non sia seguito dalla raccolta. Ciò si 
verifica quando il prigioniero sorteggiato nell'ultimo giorno della fase non 
dispone delle sue presenze e trova la lampadina accesa. In questo caso 
questo prigioniero si appropria di quelle presenze e si farà carico di 
depositarle nella appropriata fase del CICLO_2
Se allo scadere del CICLO_1 i prigionieri non vengono liberati, si 
incazzano, imprecano ma, obtorto collo, danno avvio al CICLO_2.
Se allo scadere del tempo del secondo ciclo i prigionieri non vengono 
liberati, si incazzano^2, imprecano^2 ma, obtorto collo^2, danno avvio al 
CICLO_3.
E così via...
Vediamo ora lo svolgimento di un ipotetico CICLO_2.
Per renderlo più chiaro (tanto l'adattamento a 100 ormai l'abbiamo capito), 
facciamolo partendo da 128 prigionieri.
CICLO_1 (con un paio di cadute di passaggi di presenze)
----------------------------------------------
|  |New|presenze|Ca|Distribuzione a fine fase|
|Fa|en-|trasfe- |du|-------------------------|
|se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
----------------------------------------------
| 1|   |128 x  1|  |    |   |   |   |  |  |64|
| 2|   | 64 x  2|**|    |   |   |   |  |31| 2|
| 3|   | 31 x  4|  |    |   |   |   |15| 1| 2|
| 4|   | 15 x  8|  |    |   |   | 6 | 3| 1| 2|
| 5|   |  6 x 16|**|    |   | 3 |   | 3| 1| 2|
| 6|   |  3 x 32|  |    | 1 | 1 |   | 3| 1| 2|
| 7|   |  1 x 64|  |    | 1 | 1 |   | 3| 1| 2|
----------------------------------------------
I titolari delle presenze cadute (che come abbiamo detto ne hanno 
conoscenza) incluso l'ultimo col pacchetto da 64 (che anche lui ne 
acquisisce consapevolezza perché non viene liberato) partecipano attivamente 
al ciclo di recupero.
CICLO_2
----------------------------------------------
|  |New|presenze|Ca|Distribuzione a fine fase|
|Fa|en-|trasfe- |du|-------------------------|
|se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
----------------------------------------------
| 1|   |  0 x  1|  |    |   |   |   |  |  |  |
| 2| 2 |  2 x  2|  |    |   |   |   |  | 1|  |
| 3| 1 |  2 x  4|  |    |   |   |   | 1|  |  |
| 4| 3 |  4 x  8|  |    |   |   | 2 |  |  |  |
| 5|   |  2 x 16|  |    |   | 1 |   |  |  |  |
| 6| 1 |  2 x 32|  |    | 1 |   |   |  |  |  |
| 7| 1 |  2 x 64|  |  1 |   |   |   |  |  |  |
----------------------------------------------
Resta ora aperto solo il problema dei tempi ottimali delle 7 fasi del 
CICLO_1 ed il tempo di ciascuna delle fasi dei cicli successivi che, io 
credo, può essere unico, visto che è destinato a consentire un numero 
tendenzialmente piccolo e uniforme di passaggi.
Un programmino di simulazione, come ho già detto, l'ho approntato (per il 
solo CICLO_1) e funziona in questo modo:
inserisco manualmente il numero di simulazioni (per ora 10000) ed un tempo 
per ciascuna delle sette fasi. Il programma esegue le simulazioni portando 
avanti tutte fasi fino al completamento dei passaggi e mi fornisce un report 
di dati statistici riassuntivi per ogni fase:
1 . Numero minimo di giorni nei quali è stata completata la fase
2 - Numero massimo di giorni nei quali è stata completata la fase
3 - Numero medio di giorni nei quali è stata completata la fase
4 - Percentuale di fasi completate entro il numero di giorni da me impostato
poi modifico manualmente i giorni in modo da cercare una certa uniformità 
nelle percentuali di successo nelle 7 fasi ed ottengo, in definitiva, una 
sequenza t1,t2,t3,t4,t5,t6,t7 con la relativa percentuale di successo.
Tieni presente che la % di successo in una singola fase deve necessariamente 
essere alta in quanto la probabilità di esito favorevole dell'intero ciclo è 
pari alla sua 7.a potenza.
Se ogni fase riesce nell'85% dei casi, tutte e 7 riescono nel 32% dei 
casi!!!!!!!!
Non riesco a fare di meglio perché dispongo dei dati in modo dinamico e, 
quando effettuo l'
n.ma
 simulazione non so più nulla delle prime (n-1) e non 
conosco ancora le successive.
Per ottenere dalla simulazione un contributo maggiore devo cambiare 
l'approccio e memorizzare in un file tutti i dati per farne successivamente 
oggetto di analisi.
Magari cerco di trovare il tempo di farlo, ma se qualcuno avesse voglia di 
dare una mano...
Ciao.
----
plinius 

<Il raccattapalle> ha scritto:
[cut]
Outlook trasforma il carattere "|" a inizio riga nel carattere ">" rendendo 
poco chiare le tabelle. Riposto il messaggio in modo più leggibile, spero.
Dunque, facendo una "con-fusione" dei nostri ragionamenti, per i 100
prigionieri potremmo riepilogare così:
Intesa iniziale:
1 - si fissano i tempi t1, t2, t3, t4, t5, t6, t7 per le fasi del CICLO_1
2 - si fissa un tempo tr valido per ciascuna le fasi dei cicli successivi al
primo
3 - si individuano 2 prigionieri che partono con 4 presenze
4 - si individua 1 prigioniero che parte con 8 presenze
5 - si individua 1 prigioniero che parte con 16 presenze
CICLO 1
---------------------------------------------
  |New|presenze|Ca|Distribuzione a fine fase|
Fa|en-|trasfe- |du|-------------------------|
se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
---------------------------------------------
 1|   | 96 x  1|  |    |   |   |   |  |  |48|
 2|   | 48 x  2|  |    |   |   |   |  |24|  |
 3| 2 | 26 x  4|  |    |   |   |   |13|  |  |
 4| 1 | 14 x  8|  |    |   |   | 7 |  |  |  |
 5| 1 |  8 x 16|  |    |   | 4 |   |  |  |  |
 6|   |  4 x 32|  |    | 2 |   |   |  |  |  |
 7|   |  2 x 64|  |  1 |   |   |   |  |  |  |
---------------------------------------------
Eventuali mancati passaggi in una qualunque delle fasi possono essere
determinati:
1 - dal fatto che uno dei prigionieri che detiene presenze non sia
sorteggiato e perciò non possa depositare le sue presenze: il prigioniero sa
di non aver depositato 2^(f-1) presenze e si farà carico di depositarle
nella appropriata fase del CICLO_2
2 - dal fatto che un deposito non sia seguito dalla raccolta. Ciò si
verifica quando il prigioniero sorteggiato nell'ultimo giorno della fase non
dispone delle sue presenze e trova la lampadina accesa. In questo caso
questo prigioniero si appropria di quelle presenze e si farà carico di
depositarle nella appropriata fase del CICLO_2
Se allo scadere del CICLO_1 i prigionieri non vengono liberati, si
incazzano, imprecano ma, obtorto collo, danno avvio al CICLO_2.
Se allo scadere del tempo del secondo ciclo i prigionieri non vengono
liberati, si incazzano^2, imprecano^2 ma, obtorto collo^2, danno avvio al
CICLO_3.
E così via...
Vediamo ora lo svolgimento di un ipotetico CICLO_2.
Per renderlo più chiaro (tanto l'adattamento a 100 ormai l'abbiamo capito),
facciamolo partendo da 128 prigionieri.
CICLO_1 (con un paio di cadute di passaggi di presenze)
---------------------------------------------
  |New|presenze|Ca|Distribuzione a fine fase|
Fa|en-|trasfe- |du|-------------------------|
se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
---------------------------------------------
 1|   |128 x  1|  |    |   |   |   |  |  |64|
 2|   | 64 x  2|**|    |   |   |   |  |31| 2|
 3|   | 31 x  4|  |    |   |   |   |15| 1| 2|
 4|   | 15 x  8|  |    |   |   | 6 | 3| 1| 2|
 5|   |  6 x 16|**|    |   | 3 |   | 3| 1| 2|
 6|   |  3 x 32|  |    | 1 | 1 |   | 3| 1| 2|
 7|   |  1 x 64|  |    | 1 | 1 |   | 3| 1| 2|
---------------------------------------------
I titolari delle presenze cadute (che come abbiamo detto ne hanno
conoscenza) incluso l'ultimo col pacchetto da 64 (che anche lui ne
acquisisce consapevolezza perché non viene liberato) partecipano attivamente
al ciclo di recupero.
CICLO_2
---------------------------------------------
  |New|presenze|Ca|Distribuzione a fine fase|
Fa|en-|trasfe- |du|-------------------------|
se|try| ribili |te|x128|x64|x32|x16|x8|x4|x2|
---------------------------------------------
 1|   |  0 x  1|  |    |   |   |   |  |  |  |
 2| 2 |  2 x  2|  |    |   |   |   |  | 1|  |
 3| 1 |  2 x  4|  |    |   |   |   | 1|  |  |
 4| 3 |  4 x  8|  |    |   |   | 2 |  |  |  |
 5|   |  2 x 16|  |    |   | 1 |   |  |  |  |
 6| 1 |  2 x 32|  |    | 1 |   |   |  |  |  |
 7| 1 |  2 x 64|  |  1 |   |   |   |  |  |  |
---------------------------------------------
Resta ora aperto solo il problema dei tempi ottimali delle 7 fasi del


 CICLO_1 ed il tempo di ciascuna delle fasi dei cicli successivi
Per calcolarli, sarebbe utile vedere com'è la distribuzione dei tempi
nelle tue simulazioni. Se è una simil-gaussiana con un picco molto
marcato e code molto sottili, si può tagliare di più.
Bisogna insomma valutare quanto è possibile tagliare, mantenendo
comunque una buona probabilità di riuscita. E inoltre se conviene
rischiare di più di dover eseguire il CICLO_2 ma guadagnandoci nella
durata del CICLO_1.
Inoltre: se hai voglia, proveresti a simulare la mia strategia
precedente?
2 fasi soltanto. Nella prima si parte da 100 prigionieri con 1 presenza
e si termina con 10 prigionieri con 10 presenze. Nella seconda si
termina con 1 prigioniero con 100 presenze. A occhio non credo che sia
meglio di quella a 7 fasi, ma non si sa mai.