Newsgroup: it.hobby.enigmi
Titolo: La Rivolta dei Carcerati Logici

Bentornati nel Paese dei Logici.
Vi propongo un problema che coinvolge, ancora una volta, i carcerati 
detenuti nella prigione di questo Paese.
Il braccio di massima sicurezza è composto da tante celle uguali, tutte 
dotate di servizi igienici. Ogni cella può ospitare un solo detenuto ed è 
arredata con un letto, un tavolo ed una sedia. Ogni cella ha una porta da 
cui i secondini passano il cibo attraverso uno spioncino ma nessuna finestra 
che possa favorire in qualche modo la comunicazione diretta tra i detenuti. 
Ogni cella tuttavia è dotata di due finestrelle d'areazione (50cm x 10cm) 
poste in prossimità dell'alto soffitto (5m) che la mettono in comunicazione 
con le due celle adiacenti.
I detenuti del braccio di massima sicurezza, che vorrebbero coordinarsi per 
tentare la rivolta, non possono comunicare apertamente tra di loro. Ad 
esempio, non hanno diritto all'ora d'aria perchè potrebbero approfittarne 
per parlare tra di loro. L'acustica di ogni cella, inoltre, è tale che due 
carcerati detenuti in celle vicine non possano comunicare nemmeno urlando. 
Le uniche persone con cui i detenuti entrano in contatto sono i secondini a 
cui, però, è vietato parlare con loro o trasmettere messaggi per loro conto, 
ecc. pena il licenziamento. Vista la severità della pena, i carcerati non 
riescono in alcun modo a corrompere i secondini.
Il direttore del carcere, uomo severo ma molto umano, ha fornito ad ogni 
detenuto carta e penna come passatempo per impegnare il molto tempo libero a 
disposizione. La necessità, tuttavia, aguzza l'ingegno e i detenuti scoprono 
come poter comunicare tra di loro: si scrive il messaggio su un foglio di 
carta, lo si appallottola e lo si lancia al vicino attraverso la finestrella 
d'areazione che mette in comunicazione le due celle. I detenuti sanno di 
essere stati assegnati alla propria cella in modo casuale e di poter essere 
trasferiti in modo arbitrario da una cella all'altra in ogni momento, quindi 
non c'è garanzia di lanciare un messaggio in una cella effettivamente 
occupata da qualcuno. Tuttavia si sono resi conto che i secondini, visto che 
non c'è nessuna regola specifica che lo vieta, quando scoprono una messaggio 
appallottolato in una cella vuota lo trasmettono con lo stesso metodo dei 
detenuti di finestrella in finestrella fino a quando non raggiunge un altro 
carcerato (in pratica i carcerati fanno parte di una catena chiusa ed un 
messaggio potrebbe circolarvi virtualmente all'infinito senza mai fermarsi).
In questo modo, i detenuti del braccio di massima sicurezza potrebbero far 
circolare il messaggio che vogliono (ad esempio "tentare la sommossa tutti 
assieme durante la distrinuzione del pranzo") ma vorrebbero anche sapere in 
quanti sono in tutto (per stimare ad esempio quante probabilità di successo 
hanno: "siamo in 3 e i secondini sono 10, meglio lasciar perdere"). I 
detenuti sanno inoltre che, se un detenuto viene arbitrariamente spostato da 
una cella all'altra, la catena dei messaggi si riconfigura e che tutti i 
partecipanti di prima vi prendono parte anche se probabilmente in ordine 
diverso. Se un detenuto viene rilasciato o spostato in un altro braccio del 
carcere, la catena si riconfigura senza che gli altri anelli possano 
rendersi conto del cambiamento in modo esplicito. Infine, se un detenuto 
viene introdotto nel braccio di massima sicurezza del carcere, la catena si 
riconfigura ancora ma in questo caso il nuovo anello ricevendo il messaggio 
capirebbe immediatamente cosa sta succedendo e potrebbe annunciare il suo 
arrivo all'intera catena aggiungengo due righe in coda al messaggio.
Ed infine la domanda: che messaggio devono far circolare e come si devono 
accordare per stabilire in ogni momento quanti sono, sapendo che non si 
possono accorgere di quando un detenuto esce dalla catena, che i detenuti 
possono essere spostati a caso lungo la catena e che i nuovi detenuti si 
adeguino al loro comportamento?
Ciao,
   Stefano 

 stabilire in ogni momento quanti sono,
Provo con una risposta poco ortodossa, un po' paradossale e alquanto 
autoreferenziale.:
Ci sono due possibilità:
a) questo problema non ammette soluzione;
b) questo problema ammette soluzione.
Nel caso a) Inutile andare avanti.
Nel caso b) Io non conosco la soluzione, ma ... io non sono un logico. I 
detenuti invece, essendo logici, troverebbero sicuramente la soluzione 
al problema che hai proposto. Quindi uno di loro scriverà nel biglietto 
il testo di questo problema, e magari anche la soluzione, e tutti gli 
altri si comporteranno come la soluzione suggerisce.
:-)))
_________________
Per tentare una soluzione seria, invece, ho necessità di qualche 
chiarimento:
Che vuol dire catena chiusa? Le celle sono disposte ad anello o in 
linea?
Le celle sono numerate, o comunque contrassegnate in qualche modo? E, in 
caso affermativo, i detenuti conoscono il numero della propria cella.
I detenuti conoscono il numero totale di celle?
I detenuti hanno modo di conoscere l'ora esatta, e quindi valutare il 
tempo tra la spedizione e la ricezione del messaggio?
L'azione dei secondini consistente nel *ritrasmettere* un messaggio 
caduto in una cella vuota, è immediata, o avviene ad orari fissi, oppure 
casualmente?
Un detenuto ha la possibilità di lasciare un messaggio nella propria 
cella, in modo che in caso di trasferimento, il messaggio sia letto dal 
prossimo occupante?
Varie ed eventuali (che ci sta sempre bene).
ciao
paolo

 varie ed eventuali...
Mi sento di poter aggiungere che i trasferimenti, i nuovi arrivi e le 
partenze non si accavallano tra di loro e che non avvengono troppo 
frequentemente, anche se possono pur sempre avvenire a qualsiasi ora del 
giorno e della notte... In altre parole, tra uno di quegli eventi ed il suo 
successivo, il messaggio compie molti giri lungo la catena... Può capitare 
tuttavia che due o più eventi tra quelli suddetti avvengano consecutivamente 
pur sempre senza accavallarsi... Il problema comunque è che, i detenuti 
chiusi nelle loro celle non sanno quando questi eventi avvengono e quindi 
non sanno mai se il giro che il messaggio ha appena concluso è avvenuto 
senza intoppi o no...
Io avevo pensato di fare così... chiaramente, dato che non è possibile 
basarsi sulla bontà del servizio di spedizione dei messaggi, occorre 
sfruttare l'espressività del messaggio che circolare di sicuro, in un tempo 
imprecisato... ogni volta che il messaggio passa per le mani di un 
carcerato, questi guarda se il suo nome compare nell'elenco, se non compare 
lo aggiunge e passa il messaggio... quando mi torna il messaggio conto 
quanti nomi sono elencati e so quanti detenuti siamo... solo che, così 
facendo, mi metto al riparo da trasferimenti, tengo conto dei nuovi arrivi, 
ma le partenze non le gestisco e il numero calcolato può essere sbagliato...
Poi ho pensato di fare la stessa cosa aggiungengo oltre al nome, l'orario 
del proprio orologio... quando mi arriva un messaggio guardo se c'è il mio 
nome: ne non c'è lo aggiungo, ci metto l'orario che fa il mio orologio e 
rispedisco... se invece il mio nome c'è già, scorro la lista dei detenuti e 
dei loro orari e cancello tutte le coppie di dati che risultano essere state 
scritte prima dell'ultima volta che il messaggio è passato per le mie mani 
perchè probabilmente si riferiscono a detenuti non più presenti nel braccio 
di sicurezza. il numero di detenuti che mi rimangono nella lista dovrebbe 
essere il numero di detenuti presenti nel blocco, dopodichè aggiorno il mio 
orario sul messaggio e rispedisco. L'assunzione che ho fatto è forte: se un 
prigioniero viene spostato poco prima di riceve il messaggio, potrebbe 
perdere un giro ed il suo orario non verrebbe aggiornato. Al termine di quel 
giro io potrei ritenerlo assente e depennarlo dalla lista, chiaramente 
sbagliando. Inoltre se i nostri orologi sono davvero male sincronizzati e la 
spedizione del messaggio è sufficientemente veloce, potrei ritenere un 
orario correttamente aggiornato dal proprietario sbagliato e depennare il 
suo nome dalla lista, sbagliando.
Ho infine pensato di farmi una copia del messaggio ogni volta che il 
messaggio mi ritorna: ogni volta che mi arriva un nuovo messaggio, me ne 
faccio una copia. Quando già dispongo di una copia, prima di buttare via la 
vecchia e farmene una nuova, cancello tutti quei nomi il cui orario non è 
stato modificato nel corso del giro. Aggiorno il mio orario e con quel che 
rimane dal confronto faccio il nuovo messaggio. Me lo copio e spedisco 
l'originale. In questo modo dovrei mettermi a riparo di quei casi sfortunati 
analizzati sopra in cui cancellavo un nome per colpa dei nostri orologi 
malamente sincronizzati. Nessun miglioramento però per quanto riguarda gli 
spostamenti di cella che fanno perdere un giro di messaggio ad uno dei 
detenuti.
Non mi è venuta nessuna altra idea in questo senso e inizio a pensare che i 
detenuti debbano nominare uno di loro coordinatore e far girare tanti 
messaggi fino a quando non gli ritornano e lasciare prendere a lui ogni 
decisione...
Boooooooooooooooh....
Passo la palla a voi...
Ciao,
   Stefano
Forse occorre nominare uno dei dete
cancellando quei nomi che al termine del giro non sono stati aggiornati (per 
confronto della vecchia copia con il messaggio appena giunto), aggiornando 
il mio orario e rispedendo...
guardo l'ora e calcolo quanto tempo è passato dall'ultima volta che ho 
scritto l'ora fatta dal mio orologio. Confronto tutti gli orari riportati 
dagli carcerati
se c'è aggiorno solo l'orario, sennò aggiungo in coda nome è ora al mio 
orologio... se il mio nome già compare nella lista, prima di aggiornare 
l'ora calcolo quanto tempo è passato dal passaggio e faccio un contronto tra 
il tempo trascorso tra il momento in cui gli altri detenuti hanno aggiornato 
il loro orario per l'ultima volta ed adesso... cancello tutti quei nomi che 
risultano essere stati aggiornati per l'ultima volta 

 
[....]
Un po' troppo lungo per quotare tutto....
Comunque, se la situazione puo' cambiare in qualsiasi momento non vedo
com possa esserci una soluzione "esatta" dato che nel momento in cui
chiunque sia il "raccoglitore di informazioni" decide quale e' la
situazione gia' potrebbe essere diversa. Mettiamo pero' che i cambi
siano abbastanza infrequenti da permettere una soluzione "quasi esatta".
Una tecnica potrebbe essere di mandare dei messaggi "a scadenza", nel
senso che mando un messaggio con un numero e quando quel numero di
persone lo ha visto (e marcato) lo manda indietro. Tipo un messaggio di
valore 3 il primo lo vede e scrive il suo nome e lo manda alla prossima
stesso il secondo, il terzo scrive il nome e lo manda indietro al
secondo ( che sottolinea il suo nome per rimarcare che e' ancore li) e
lo ripassa al primo che fa lo stesso e lo rimanda all'originatore.
Se l'originatore sa che ci sono, mettiamo 10 celle, manda messaggi di
valore  da 1 a 9 (magari in tutti e due i sensi) e quando li ha ricevuti
tutti (se ci sono celle vuote, dalla parte sbagliata...) puo' avere
un'idea della situazione.
Non ho idea pero' di come sia possibile per i detenuti sapere quanti
secondini ci sono  a meno che non lo sappiano a priori.
Ciao,
Gorgo
P.S.
Se qualcuno pensa che questo metodo gli ricorda qualcosa vuol dire che
conosce il comando "traceroute" di Unix :-).
G 

 accorgono nemmeno dell'intervento dei secondini...
Pensavo di sfruttare il fattore tempo in modo diverso dal tuo, 
rallentando volutamente la velocità del giro. (la cosa si allunga, ma in 
prigione il tempo non manca :-)
Se per esempio possiamo determinare l'orine di grandezza del ritardo 
provocato dai secondini, per esempio qualche minuto, si potrebbe 
decidere di far partire i messaggi ad ore stabilite, per esempio ogni 
ora.
Cioè spedisco il messaggio alle 5.00 del mio orologio.
Il detenuto successivo lo riceve quando il suo orologio segna le 5.00 
più o meno qualche minuto (dipende da eventuali ritardi dei secondini e 
dalla non sincronizzazione degli orologi) e lo rispedisce alle 6.00. E 
così tutti gli altri.
Se il messaggio mi torna dopo n ore, è stato visto da n detenuti.
Questo naturalmente è solo un inizio. Resterebbe da risolvere il 
problema di trasferimenti ecc.
ciao
paolo

Vado a memoria
situazioni come quella che hai descritto si studiano nella gestione 
delle comunicazioni di rete
una serie di postazioni che comunicano tramite un canale del quale non 
abbiamo garanzie
nel caso descritto:
sembra che i messaggi non vadano mai persi
sembra che i messaggi possano girare in entrambi i sensi senza 
infastidirsi (segno sul biglietto se deve andare da destra a sinistra o 
viceversa;  dx e sx sono individuate dalle spalle alla porta e posso 
spiegarlo nel biglietto stesso e pare che i secondini seguano queste regole)
sembra che piu' biglietti possano viaggiare contemporaneamente
sembra che ogni postazione abbia una quantità di memoria illimitata, ma 
ogni tanto viene resettata e trasferita di posizione nella catena
sembra che il numero di postazioni sulla rete possa cambiare
sembra che non ci sia un limite preciso alla lunghezza dei messaggi 
(almeno un foglio A4 fronte retro)
sembra impossibile sincronizzare gli orologi
Le condizioni sono piuttosto buone direi
ci sarà un messaggio che circola continuamente che dice:
se sei appena arrivato scrivi il tuo nome in un nuovo biglietto ed 
invialo a dx;
ritiralo quando ti arriva da sx;
se vedi un biglietto con una lista di nomi aggiungi il tuo in fondo e 
fai proseguire;
tieni una lista dei nomi aggiornata con tutti i nomi che ti passano fra 
le mani;
se vuoi scrivere a qualcuno inizia il biglietto con il nome del 
destinatario, aggiungi il tuo e poi il messaggio;
fai girare tutti i messaggi che NON sono indirizzati a te;
quando ricevi un messaggio per te rispondi confermando la ricezione con 
un nuovo messaggio;
a questo punto, stabilito un minimo di "protocollo", ampiamente 
migliorabile; si inizia a progettare la fuga
certo che questi secondi ne avranno di lavoro a spostare bigliettini, e 
poi non essere curiosi di leggere un bigliettino raccolto? :)
Ciao
Zanna


Il numero dei secondini è noto a priori! 

s
p
o
i
l
e
r
s
p
o
i
l
e
r
s
p
o
i
l
e
r
Ci provo: quando un detenuto riceve un messaggio per la prima volta attende 
un tempo x (ad esempio un giorno) prima di inoltrarlo. Se invece ha già 
ricevuto il messaggio lo inoltra subito.
In questo modo se un detenuto che riceve un messaggio viene spostato non 
influisce più sul percorso, se non per pochi secondi.
Il primo che ha spedito il messaggio tiene conto del tempo che ci mette a 
tornare, però poi lo reinoltra subito per "catturare" eventuali detenuti 
che, spostati, non hanno ancora ricevuto il messaggio. Quando il messaggio 
torna indietro in meno di un giorno vuol dire che tutti i detenuti hanno 
trattenuto il messaggio e può contare quanti giorni sono stati impiegati 
complessivamente.
Questa soluzione presuppone che il messaggio venga trasmesso dai secondini 
in poco tempo quando la cella è vuota.

 detenuti nella prigione di questo Paese.
Riprovo:
Penso che si possa stabilire una sorta di sincronizzazione anche se non 
estremamente precisa.
Per esempio, se il mio orologio segna le 5.00, presumo che gli altri 
segnino un'ora compresa tra le 4.50 e le 5.10; potrebbe bastare.
Con una serie di messaggi preliminari, si concorda che il *gioco* inizi 
alle cinque.
Oppure uno dei detenuti, che funge da coordinatore, fa circolare un 
messaggio preliminare con scritto VIA!
Al via, ciascuno (quasi contemporaneamente) scrive un biglietto col il 
suo nome e lo fa circolare.
Chi riceve un biglietto, aggiunge il proprio nome.
Quando il biglietto ritorna al mittente, questo lo fa proseguire per un 
secondo giro. Chi riceve il biglietto, se il suo nome è già scritto, lo 
fa proseguire senza aggiungere nulla.
Quando il biglietto torna al mittente per la seconda volta, questo lo 
trattiene e conta i nomi scritti.
Se un detenuto viene spostato di cella durante il primo giro, può 
perdere qualche biglietto, ma recupera al secondo giro.
Se un detenuto si aggiunge al giro, scrive il proprio nome su tutti i 
biglietti che riceve.
Se un detenuto viene allontanato dal giro, il suo biglietto continua a 
girare *all'infinito*. Vedendo il biglietto che fa più di due giri, 
ciascuno si rende conto che quel detenuto non è più presente.
Mi pare che la cosa funzioni, salvo qualche piccolo bug:
_il detenuto che si aggiunge verso la fine del secondo giro rischia di 
non essere contato da tutti;
_un detenuto può essere allontanato subito dopo avere trattenuto il 
proprio biglietto alla fine del secondo giro.
ciao
paolo

 ha scritto nel messaggio 
news:GufYd.18331$WC1....@tornado.fastwebnet.it...


E infatti questo giochino mi è venuto in mente studiando proprio reti di 
calcolatori!
Quel che mi premeva esplorare, infatti  era la possibilità di ignorare 
l'incertezza del sistema adottando un buon protocollo... visto che tu ne sai 
già (io mi sto facendo le ossa), si può fare o no?
Intendo dire con esattezza, come solo i Logici saprebbero fare!
Ciao e grazie,
   Ste 

Ciao non sono un esperto
dovrei riaprire i libri ma da quel che ricordo i protocolli di rete 
(regole per comunicare) contemplano, sempre, la possibilità di 
sincronizzare gli orologi fra i partecipanti;
ci sono dei presupposti sulla qualità degli orologi di ogni partecipante 
e sul fatto che si possa (grazie a specifiche sequenze di comunicazione) 
sincronizzare ogni orologio con gli altri.
A partire da questi presupposti ci sono delle fasi iniziali di 
comunicazione in cui si scopre la velocità della linea e percio' i 
time-out dopo i quali si ritenta l'invio di un messaggio perchè è molto 
probabile non sia arrivato a destinazione.
Esistono molti modi (algoritmi) per individuare chi deve parlare e cosa 
fare quando due parlano contemporaneamente annullando vicendevolmente il 
messaggio dell'altro.
Il presupposto che gli orologi non siano di qualità (qualcuno piu' 
lento, qualcuno piu' veloce) ed intervalli random sulla linea (un 
biglietto potrebbe rimanere in una cella vuota per un giorno od un 
secondo e poi riprendere a girare) impediscono di applicare i vari metodi.
Il presupposto che i messaggi arrivano sempre, non vanno persi e che 
piu' messaggi sulla linea non si disturbano rende secondo me tutto il 
sistema semplice.
Si tratta di avere pazienza, la posizione dei carcerati nella linea non 
è importante, se qualcuno manca non è un problema.
Sapere che il mio messaggio verrà letto da tutti, sempre, già mi risolve 
i problemi maggiori; siamo in una mailing list fatta a mano in cui ci 
passiamo i messaggi l'un l'altro, solo che non sappiamo con che tempi 
questi messaggi vengono passati, ed anche se io non ci sono il messaggio 
viene inoltrato.
A questo punto iniziamo a proporre delle teorie su come assaltare le 
guardie in mensa :)
Se cominciamo a dire che un messaggio su 10 va perso, che c'e' una spia 
fra i detenuti che è un perfetto non logico, che ogni giorno i secondini 
fanno passare solo 10 messaggi, che vogliamo conferma che tutti sono 
d'accordo sul piano;
si puo' allora cercare di ottimizzare le comunicazioni per ottenere il 
risultato di chiedere tutti piselli in mensa e, quando finiscono, 
inscenare una protesta mentre il prescelto ruba le chiavi dell'uscita :)
Ciao
Zanna


Ciao Zanna!
Grazie ancora! Reti la sto studiando adesso... sarà che i lucidi del prof 
sono spesso un po' troppo criptici...
ma quello che mi dici non mi "sembra" ancora vero! ovviamente è colpa mia: 
mi metto a studiare con più attenzione...
Ciao,
   Ste 

Provo la mia, anche se mi sembra troppo semplicistica.
Allora, il sistema è ad anello e, pertanto, il carcerato MASTER
introduce il proprio biglietto in uscita e, dopo un certo tempo, gli
arriverà dalla parte opposta (in entrata).
Sfruttando questo sistema chiuso che, in caso di cella occupata o meno
è sempre funzionante grazie ai secondini, si potrebbe usare il
biglietto come se fosse una "chat a turni", ovvero una prima parte di
istruzioni e una seconda per i messaggi scritti con un certo criterio,
per esempio:
mess n. 1 - cella n. 1, Sig. Rossi - Messaggio del signor Rossi
mess n. 2 - cella n. 2, Sig. Tizio - Messaggio del signor Tizio
mess n. 3 - cella n. 4, Sig. Caio  - Messaggio del signor Caio
in questo si può costantemente monitorate la situazione delle celle
(nel caso sopra, la cella n.3 è vuota) con i relativi spostamenti (una
volta trasferito, il signor Rossi nella nuova cella può comunicare
agli altri la nuova posizione)
mess n. x - cella n. 8, Sig. Rossi - Ragazzi, mi hanno trasferito alla
cella 8
inoltre si potrebbe creare un sistema di comunicazione ciclico dove
scambiarsi i messaggi e organizzare il tentativo di rivolta.
mess n. y - cella n. 2, Sig. Tizio - per Rossi: com'è la nuova cella?
Che ne dite? Mi sono perso qualcosa? Saluti, Luca