Cento prigionieri e una lampadina

Post by Il raccattapalle
Ogni mattina, un prigioniero _scelto assolutamente
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

2006-02-20 14:04:13 UTC

Post by SisQo

Post by Il raccattapalle
Ogni mattina, un prigioniero _scelto assolutamente
a caso_ verrà condotto nella stanza centrale

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

carmine

2006-02-20 13:14:18 UTC

Post by Il raccattapalle
(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.
-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).
-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?

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

2006-02-20 13:43:28 UTC

Post by carmine
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.

Non funziona.
Se uno entra e la trova spenta, come fa a sapere quante volte in
passato e' stata accesa e spenta?

carmine

2006-02-20 14:26:11 UTC

Non funziona.
Se uno entra e la trova spenta, come fa a sapere quante volte in
passato e' stata accesa e spenta?

non hai detto che dalla cella non era possibile vedere la lampadina :))))

Plinius

2006-02-20 13:15:51 UTC

Post by Il raccattapalle
(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.
-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).
-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?

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

SisQo

2006-02-20 13:33:37 UTC

Post by Plinius
I prigionieri possono organizzare la conta di coloro che entrano per la
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.

Il raccattapalle

2006-02-20 13:48:58 UTC

Post by SisQo
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.

"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

2006-02-20 13:47:53 UTC

Post by Plinius
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.

Oppure se la prima volta (o le successive) in cui era entrato l'aveva
già trovata accesa. In questo caso, per accenderla a sua volta deve
aspettare di entrarci una volta che la trova spenta.

Post by Plinius
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.

E poi, prima di uscire, deve rispegnerla: questo "rilevatore designato"
è l'unico che ha il permesso di spegnere la lampadina.

Post by Plinius
Quando il rilevatore designato arriva a 100 pronuncia il fatidico "Sì"
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

uahlim

2006-02-20 18:26:15 UTC

Post by Il raccattapalle
Giusto!!
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!

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 ***@newsland.it

uahlim

2006-02-20 18:55:39 UTC

Post by Il raccattapalle
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.

Nino

2006-02-20 21:12:23 UTC

"Il raccattapalle" ha scritto nel messaggio
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

Nino

2006-02-20 22:25:44 UTC

Post by Nino
Si può migliorare così.
I prigionieri si accordano di stabilire che diventerà contatore
colui che per primo entrerà nella stanza per la seconda volta.

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

Nino

Il raccattapalle

2006-02-22 13:56:37 UTC

Post by Nino
Si può migliorare così.
I prigionieri si accordano di stabilire che diventerà contatore
colui che per primo entrerà nella stanza per la seconda volta.

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

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

Nino

2006-02-22 15:58:22 UTC

Post by Nino
"Il raccattapalle" ha scritto nel messaggio

Post by Nino
Si può migliorare così.
I prigionieri si accordano di stabilire che diventerà contatore
colui che per primo entrerà nella stanza per la seconda volta.

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

Mi sembrava che il ragionamento non fosse campato per aria...
Solo che mi sfuggiva l'astuzia di lasciar passare 100 giorni.

Post by Nino
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.

Questo l'avevo calcolato
"In tal modo, la durata media dovrebbe ridursi da 27 a circa 24 anni"

Post by Nino
E comunque, anche questo metodo è ulteriormente migliorabile :-)
Ciao

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

Ciao, Nino

Plinius

2006-02-22 17:10:45 UTC

Post by Il raccattapalle
E comunque, anche questo metodo è ulteriormente migliorabile :-)
Ciao

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

Nino

2006-02-20 13:59:58 UTC

"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

Il raccattapalle

2006-02-20 14:14:44 UTC

Post by Nino
Mi sembra che questo quesito sia già stato esaminato su IHE...

Sì, adesso l'ho visto. Ma anche allora era stata data solo la
soluzione "standard" del prigioniero-contatore. Invece, a quanto ne so,
ci sono soluzioni migliori (cioè più rapide).

Post by Nino
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).

Ipotizziamo (idealmente) che i prigionieri siano immortali.
In questo caso, per loro è meglio attendere 30 anni ed esseri sicuri
al 100% di uscire, piuttosto che attendere di meno con un rischio
(benché minimo) di morire.

D'altronde, il testo dell'enigma chiede proprio questo: una certezza al
100%. Sennò, sarebbe troppo facile e la soluzione non richiederebbe
alcuna fatica.

Post by Nino
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...)

Puoi essere più preciso? A me risultano circa 27 anni...

Post by Nino
senza contare
che potrebbe anche non essere scelto mai casualmente per tutte le
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

Nino

2006-02-20 14:31:37 UTC

Post by Nino
"Il raccattapalle" ha scritto nel messaggio

Puoi essere più preciso? A me risultano circa 27 anni...

Beh! Certo, avevo fatto i conti a mente.
100*100/365,25 = 27,38 anni

Post by Nino
Diciamo che è il risultato del tiro di un dado a 100 facce.

O dell'estrazione di 100 numeri con reimbussolamento.

Ciao, Nino

uahlim

2006-02-20 19:15:18 UTC

Post by Nino
"Il raccattapalle" ha scritto nel messaggio

Puoi essere più preciso? A me risultano circa 27 anni...

Beh! Certo, avevo fatto i conti a mente.
100*100/365,25 = 27,38 anni

Post by Nino
Diciamo che è il risultato del tiro di un dado a 100 facce.

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.

Nino

2006-02-20 22:12:46 UTC

"uahlim" ha scritto nel messaggio

Post by uahlim

Post by Nino
100*100/365,25 = 27,38 anni

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.

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

uahlim

2006-02-20 22:42:56 UTC

Post by Nino
"uahlim" ha scritto nel messaggio
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.

Nino

2006-02-20 23:10:09 UTC

"uahlim" ha scritto nel messaggio

Post by uahlim

Post by Nino
Vediamo. Il prigioniero-contatore sia fissato a priori.

Non lo fisso a priori, ma è il prigioniero che viene chiamato il TERZO
giorno.

Le cose anche così cambiano di pochissimo...

Post by uahlim
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.

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

Plinius

2006-02-23 19:27:28 UTC

Post by Il raccattapalle
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.
-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).
-Qual è un metodo per poter essere sicuri al 100% di dare una risposta
affermativa?

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

Il raccattapalle

2006-02-23 21:57:09 UTC

Post by Plinius
Ho continuato allora a pensare se non fosse possibile diminuire il tempo
necessario al trasferimento delle informazioni ad un unico prigioniero.

Innanzitutto complimenti per la tua soluzione. Io avevo pensato a un
meccanismo simile, ma meno complesso: solo 2 fasi. Dieci contatori
(prestabiliti). Nella prima fase ciascuno arriva a contare fino a 10
(compreso se stesso), nella seconda fase uno di loro (un
super-contatore) deve contare gli altri nove contatori.

Post by Plinius
SISTEMA DEL LASCIA O RADDOPPIA
Partiamo, per semplicità, da un numero di prigionieri pari ad una potenza di
2 (facciamo 128).

(snip)

Post by Plinius
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.,

Qui forse si può limare qualcosa. Nel caso si dovessero ripetere tutte
le fasi, non è necessario ricominciare il conteggio da zero.
Basterebbe che chi è già stato contato non si faccia più contare:
soltanto quelli che non erano riusciti a farsi contare si lasceranno
contare (naturalmente nella fase appropriata. Se un prigioniero da 4
presenze non era riuscito a farsi contare, dovrà farsi contare nella
fase 3).

In questo modo, il secondo ciclo di 7 fasi potrebbe durare molto meno.
Bisognerà fare un po' di conti per ottimizzarne la durata.

Però sorge un problema. Potrebbero esserci dei conteggi "persi": mi
riferisco al caso in cui, alla fine di una fase, c'è ancora la
lampadina accesa. Significa che un prigioniero ha lasciato le sue
"presenze" affinché qualcuno le raccogliesse, ma nessuno dei possibili
contatori è riuscito a raccoglierle. Il prigioniero che le ha lasciate
non può saperlo, e riterrà in buona fede di essere stato contato.
In questo caso, ritengo che il prigioniero che entra nell'ultimo giorno
di ciascuna fase e trova la lampadina accesa, debba farsi carico delle
presenze corrispondenti. Ovvero, anche se era stato contato e dunque
era uscito dai giochi, torna automaticamente in gioco (naturalmente
dovrà aspettare il secondo ciclo e la ripetizione della fase
corrispondente).

Post by Plinius
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.
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.

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? :-)

Plinius

2006-02-23 22:42:34 UTC

Post by Plinius
SISTEMA DEL LASCIA O RADDOPPIA
Partiamo, per semplicità, da un numero di prigionieri pari ad una
potenza di 2 (facciamo 128).

(snip)

Post by Plinius
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.,

Qui forse si può limare qualcosa. Nel caso si dovessero ripetere tutte
le fasi, non è necessario ricominciare il conteggio da zero.
soltanto quelli che non erano riusciti a farsi contare si lasceranno
contare (naturalmente nella fase appropriata. Se un prigioniero da 4
presenze non era riuscito a farsi contare, dovrà farsi contare nella
fase 3).

Purtroppo dimentichi che i prigionieri non possono comunicare più tra loro e
che, quindi, dopo aver espletato il ruolo assegnatogli, un prigioniero
l'unica notizia che riceve dall'esterno è quella della mancata libertà alla
scedenza dell'ultima fase! Se lui sia stato o meno contato non lo può
sapere!

Post by Il raccattapalle
In questo modo, il secondo ciclo di 7 fasi potrebbe durare molto meno.
Bisognerà fare un po' di conti per ottimizzarne la durata.
Però sorge un problema. Potrebbero esserci dei conteggi "persi": mi
riferisco al caso in cui, alla fine di una fase, c'è ancora la
lampadina accesa. Significa che un prigioniero ha lasciato le sue
"presenze" affinché qualcuno le raccogliesse, ma nessuno dei possibili
contatori è riuscito a raccoglierle. Il prigioniero che le ha lasciate
non può saperlo, e riterrà in buona fede di essere stato contato.
In questo caso, ritengo che il prigioniero che entra nell'ultimo
giorno di ciascuna fase e trova la lampadina accesa, debba farsi
carico delle presenze corrispondenti. Ovvero, anche se era stato
contato e dunque era uscito dai giochi, torna automaticamente in
gioco (naturalmente dovrà aspettare il secondo ciclo e la ripetizione
della fase corrispondente).

Io l'ho vista diversamente questa cosa. Intanto ho pensato che una fase può
essere considerata riuscita se tutte le presenze depositate vengono raccolte
e, dunque, che la lampadina alla fine della fase sia sempre spenta. Unica
eccezione quella del resto, cioè al prigioniero dispari non accoppiabile. In
questo caso, il prigioniero che entra nella stanza l'ultimo giorno di una
fase e trova la lampadina accesa è quello deputato a segnalare il resto
nella fase aggiuntiva.

Post by Plinius
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.
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.

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!

L'idea mi sembra ottima, ma merita un approfondimento: essendo possibili
scambi di presenze solo per potenze di 2, i 28 aggiuntivi dovrebbero essere
attribuiti:
- 15 a un soggetto che così parte con 16 e si mette fuorigioco per
rientrare solo nella fase 5 (in cui gli scambi sono da 16),
- 7 a un soggetto che così parte con 8 e si mette fuorigioco per rientrare
solo nella fase 4 (in cui gli scambi sono da 8,
- 3 ciascuno ad altri due soggetti che così partono con 4 e si mettono
fuorigioco per rientrare solo nella fase 3 (in cui gli scambi sono da 4.

Post by Il raccattapalle
C'è qualche programmatore che ha voglia di fare un po' di simulazioni
con i diversi metodi? :-)

----
plinius

Il raccattapalle

2006-02-24 00:09:06 UTC

Post by Plinius
Purtroppo dimentichi che i prigionieri non possono comunicare più tra loro e
che, quindi, dopo aver espletato il ruolo assegnatogli, un prigioniero
l'unica notizia che riceve dall'esterno è quella della mancata libertà alla
scedenza dell'ultima fase! Se lui sia stato o meno contato non lo può
sapere!

Appunto: una volta che un prigioniero accende la lampadina, per quanto
lo riguarda lui è stato contato. O meglio: ha "depositato" una
presenza (da 1, da 2, da 4, ecc., a seconda della fase) che qualcun
altro doveva raccogliere.

Ma se arriva l'ultimo giorno di quella fase e nessuno ha ancora
raccolto la presenza (perchè in seguito nella stanza non è entrato
nessuno che a sua volta possedeva ancora la propria presenza), bisogna
evitare che questa presenza si perda.

Post by Plinius
Io l'ho vista diversamente questa cosa. Intanto ho pensato che una fase può
essere considerata riuscita se tutte le presenze depositate vengono raccolte
e, dunque, che la lampadina alla fine della fase sia sempre spenta.

Non è detto, perchè la durata delle fasi viene prestabilita a priori.
Supponiamo per esempio di essere nella fase 1.
49 prigionieri cedono le loro presenze ad altri 49. Poi il 99esimo
prigioniero lascia la luce accesa. Ma se poi il centesimo prigioniero
(_l'unico_ che potrebbe raccogliere questa presenza) non viene più
scelto per il resto della fase, all'ultimo giorno della fase la lampada
sarà ancora accesa. E sarà necessario che il prigioniero che entra
l'ultimo giorno si faccia carico di questa presenza singola (andando a
1 se la sua l'aveva depositata, oppure a 3 se ne aveva raccolta una).
Terminato il ciclo (ovviamente con risultato negativo), questo
prigioniero potrà depositare la presenza nella nuova fase 1 (ed
eventualmente le altre due - se ne aveva 3 - nella nuova fase 2).

Post by Plinius

Post by Plinius
Altra analisi merita l'adattamento del sistema ai 100 prigionieri (o
anche a qualunque altro numero che non sia potenza di 2).

L'idea mi sembra ottima, ma merita un approfondimento: essendo possibili
scambi di presenze solo per potenze di 2, i 28 aggiuntivi dovrebbero essere
- 15 a un soggetto che così parte con 16 e si mette fuorigioco per
rientrare solo nella fase 5 (in cui gli scambi sono da 16),
- 7 a un soggetto che così parte con 8 e si mette fuorigioco per rientrare
solo nella fase 4 (in cui gli scambi sono da 8,
- 3 ciascuno ad altri due soggetti che così partono con 4 e si mettono
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

Plinius

2006-02-24 11:41:27 UTC

<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

Plinius

2006-02-24 11:47:42 UTC

<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 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

2006-02-24 13:00:24 UTC