Newsgroup: it.hobby.enigmi
Titolo: [LO] Carcerati

E' un po' che non vedo problemi di questo genere e cosi provo a proporne uno
io, non è difficilissimo ma sicuramente di primo acchito appare sconcertante
(almeno lo è stato per me).
Il direttore del carcere di massima sicurezza di logiclandia ha deciso
un'amnistia generale dei 32 detenuti condannati all'ergastolo a patto che
si dimostrino dei veri logici e quindi riacquistino il diritto di cittadini
liberi.
Gli propone allora il seguente patto:
 "Sarete tutti sottoposti ad interrogatori continui, uno dopo l'altro in un
ordine qualsiasi e senza nessuna logica. Ognuno sarà interrogato quando e
quante volte ci pare ad insaputa degli altri, sarete interrogati uno per
volta nella medesima stanza per quanto tempo sarà necessario.
Vi libererò se uno di voi sotto interrogatorio dichiarerà che siete stati
interrogati tutti almeno una volta. Badate bene però: se qualcuno farà
questa dichiarazione e non si dimostrerà vera allora sarete tutti impiccati!
Avrete una sola possibilità, una sola persona potrà tentare la sorte per
provare a liberarvi, se avrà ragione sarete tutti liberi
altrimenti.....zack! Vi lascio tutti insieme in questa stanza ancora per
dieci minuti, dopo sarete isolati e cominceranno gli interrogatori, non
avrete altre possibilità di contatto o di comunicazione a parte un
interruttore nella stanza dell'interrogatorio. Un normale interruttore
ON/OFF ma che non comanda alcunché, vi prometto che solo voi avrete la
facoltà di toccarlo , ne io e ne le guardie interferiremo.
I 10 minuti cominciano ... ADESSO!".
Come possono fare i carcerati a tornare in libertà?
Un saluto a tutti
Gabriele

Mmm...
Magari non c'entra niente, ma non è importante sapere se l'interruttore è su
on o su off prima dell'inizio degli interrogatori?
Ciao,
  Ste

 on o su off prima dell'inizio degli interrogatori?
E' una mia dimenticanza, l'interrutore all'inizio è su OFF, il buon
direttore ne è sicuro.
Scusate,
Gabriele


Poco convinto.
I 32 si danno un numero da 1 a 32.
Nessun tocca l'interruttore finchè l'1 viene interrogato. Quando 1 viene
interrogato alza l'interruttore.
A questo punto tutti sanno che 1 è stato interrogato.
Nessun tocca l'interruttore finchè 2 viene interrogato. Quando 2 viene
interrogato abbassa l'interruttore.
A questo punto tutti sanno che 2 è stato interrogato.
Nessun tocca l'interruttore finchè 3 viene interrogato. Quando 3 viene
interrogato alza l'interruttore.
Loop to 31
Nessun tocca l'interruttore finchè 31 viene interrogato. Quando 31 viene
interrogato alza l'interruttore.
A questo punto tutti sanno che 31 è stato interrogato.
Quando entra 32 dice "Ehi io sono l'ultimo".
Ma credo che il direttore di logiclandia li abbia già rilasciati prima per
disperazione.
---- /\ ----
   o/  \
   /    \
  /Sisifo\


Non credo funzioni:  come fanno a sapere a quale punto sono? Se ho ben
capito il problema i prigionieri possono essere interrogati in qualsiasi
ordine anche per più di una volta.
Io provo ad ipotizzare che la soluzione abbia a che fare col sistema
binario, ma non riesco a immaginare nulla.
Alessandro


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Si mettono d'accordo nel seguente modo.
L'interruttore è inizialmente su OFF. Uno di loro agirà da "supervisore".
Tutti gli altri si comporteranno così: ogni volta che ognuno di questi entra
nella stanza, se l'interruttore è su OFF ed è la prima volta che ciò si
verifica, lo mette su ON. In tutti gli altri casi non fa niente.
Il supervisore, ogni volta che entra nella stanza, se l'interruttore è su ON
lo rimette su OFF e tiene un conteggio dell'azione appena effettuata. Quando
il conteggio raggiunge 31 (N-1), ha la certezza che tutti siano entrati
almeno una volta nella stanza.
Bello!
Ciao :-)
Giorgio

 
Questa soluzione perň crolla nel momento in cui smettono di interrogare 
il supervisore prima che lui abbia contato 31 volte.
Ciao,
Bl@de

 il supervisore prima che lui abbia contato 31 volte.
Beh, tutto crolla anche se non interrogano mai una persona e quindi non c'è
niente da fare.
La mia risposta è la stessa data da Giorgio (complimenti), non vedo altre
possibilità.
Ho provato anche a pensare a cosa si potesse fare se non si sapesse la
posizione iniziale dell'interruttore ma non vedo niente di utile.
Alla prossima, un saluto a tutti,
Gabriele
P.S.: Ho deciso di mettere 32 carcerati cercando di dare una falsa
indicazione su una soluzione tramite sistema binario :o)

 La mia risposta è la stessa data da Giorgio (complimenti),
Mi associo. Devo dire che a prima vista mi sembrava impossibile una
soluzione esclusivamente logica, per cui stavo cercando soluzioni
laterali.
Quesito aggiuntivo: quanto dura *mediamente* il tutto?
Il minimo dovrebbe essere 64 interrogatori, supposto per esempio che
vengano chiamati nell'ordine
1, 32, 2, 32, .........31, 32
essendo 32 il supervisore.
Il massimo dovrebbe *tendere a infinito*.
E' possibile calcolare una media (supposto che i detenuti vengano
chiamati con criterio assolutamente casuale)?
ciao
paolo


Si può supporre che ognuno venga chiamato mediamente una volta ogni 32. In
particolare questo capita al supervisore, il quale dovrebbe sempre trovare
l'interruttore su ON, perché, mediamente, prima di lui sono stati chiamati
tutti gli altri e tra questi anche quello che ha trovato l'interruttore su
OFF per la prima volta. Quindi, ad ogni "giro" il supervisore dovrebbe
incrementare il suo conteggio di 1. Direi che mediamente il numero delle
persone chiamate dovrebbe aggirarsi sul valore N*N o N*(N-1) o giù di lì.
Cosa ne dite?
Ciao :-)
Giorgio

"Giorgio Vecchi"

Visto che nessuno dice niente, dico io qualcos'altro. :-)
Un calcolo più preciso dovrebbe essere questo. Si tratta di calcolare il
numero medio di chiamate che smuova la situazione per ogni turno. Ad
esempio, bisogna che al primo turno entri uno che non sia il supervisore, al
secondo turno deve entrare il supervisore, al terzo turno deve entrare uno
che non sia quello che è entrato prima, né il supervisore, al quarto turno
di nuovo il supervisore e così via.
Con N persone, il primo turno si smuove se entra uno tra N-1 persone. La
probabilità che ciò avvenga è naturalmente (N-1)/N; l'attesa è il suo
reciproco N/(N-1). Quindi al primo turno bisogna aspettare N/(N-1) chiamate
perché entri una persona che va bene.
Al secondo turno deve entrare il supervisore che ha probabilità 1/N, quindi
l'attesa è N.
Poi deve entrare uno degli N-2 rimasti validi e qui l'attesa è N/(N-2), poi
ancora il supervisore con attesa N.
Si va avanti così fino all'ultimo che avrà probabilità 1/N e quindi attesa N
e poi ancora il supervisore.
Il tutto diventa la sommatoria di N/(N-i) con i che va da 1 a N-1, più le
attese del supervisore che sono in totale N*(N-1).
Io le sommatorie non le so risolvere (se qualcuno lo facesse avremmo una
bella formula compatta), ma per alcuni valori di N ho calcolato il numero
medio di chiamate.
N    Chiamate
32    1120.872
10    118.2897
4    19.33333
3    10.5
2    4
In generale è un po' più di N*N.
Ciao :-)
Giorgio

A questo punto non serve nemmeno più sapere se l'interruttore è inizialmente
su ON o OFF: infatti in queste ipotesi è sufficiente che il supervisore la
prima volta che entra nella stanza degli interrogatori "resetti" il conto,
ovvero metta per la prima volta su OFF l'interruttore. Dopodichè si procede
con quanto già esposto da Giorgio.

Lo so, sembro pazzo a rispondermi da solo, ma ho letto il resto del 3d solo
dopo aver già postato...
Ad ogni modo, se escludiamo di conoscere a priori lo stato dell'interruttore
al momento iniziale, dobbiamo attendere che il supervisore venga interrogato
per la prima volta in modo che possa predisporre le condizioni iniziali per
permettere il conteggio degli altri interrogati da parte propria. Questo
significa che occorre semplicemente fare un "giro" di algoritmo in più...
Come Giorgio ha più volte fatto notare, la probabilità che il supervisore
venga chiamato è 1/N mentre l'attesa è N.
Questo significa che, se vogliamo conoscere il numero medio di chiamate che
devono essere effettuate per risolvere il problema quando non si sa la
posizione iniziale dell'interruttore a partire dai valori che ci ha già
fornito Giorgio nel suo post, ci basterà moltiplicarli per N!
Li riporto di seguito per comodità:
N    Chiamate*    Chiamate* (caso generale)
32    1.121        35.868
10    118            1183
4    19                77
3    11                32
2    4                    8
* ho arrotondato all'intero più vicino
Ciao,
  Ste

 significa che occorre semplicemente fare un "giro" di algoritmo in più...
Ma come fa il supervisore a capire se l'interruttore è su ON perché ce l'ha
messo uno dei suoi compagni o perché quella era la posizione iniziale (e
quindi è il primo ad essere interrogato)?

 significa che occorre semplicemente fare un "giro" di algoritmo in più...
Non c'è modo di fare un "giro" in più. La logica di ogni carcerato impone di
dare la propria segnalazione una sola volta. Se il supervisore decide di
ignorare la prima volta che trova l'interruttore su ON, l'eventuale
indicazione del primo carcerato viene persa e il conteggio non arriverà mai
a N-1.
Se invece il supervisore decide di considerare comunque il messaggio ON
della prima volta come un'indicazione da parte del primo carcerato, potrebbe
trovarsi a credere di avere contato tutti gli N-1 compagni quando invece
questi potrebbero essere stati solo N-2.
Come ha detto anche ricky, la cosa non funziona. Del resto non si è mai
visto un flag non inizializzato portare a qualcosa di buono! :-)
Ciao :-)
Giorgio

 In generale č un po' piů di N*N.
Tu sei pigro, piů che altro.
Che la serie armonica H(n) = 1 + 1/2 + 1/3 + .. + 1/n
sia approssimabile con log(n+1) lo sanno pure i sassi.
In generale H(n) č un po' piu' grande del logaritmo, e quel "un po' piů
grande" tende alla costante di eulero-mascheroni che č poco piů di 1/2
(0.577215664901532).
Allora una buonissima approssimazione della tua formaula č:
n*(n-1+log(n)+k) dove k č la costante di EM
-- 
Ciao, Silv:o)

 n*(n-1+log(n)+k) dove k è la costante di EM
E finalmente abbiamo la formula, anche se dà valori un po' eccedenti
rispetto ai miei calcoli. Ma è mai possibile che non esista una formula per
1+1/2+1/3+..+1/n che dia il valore giusto, senza bisogno di logaritmi!? 'Sti
matematici lo sanno fare il loro mestiere??? :-))))
Ciao :-)
Giorgio

 'Sti matematici lo sanno fare il loro mestiere???
Secondo loro se comincio a spalare terra, cominciando con una palata e
proseguendo con mezza palata, poi un terzo, un quarto, una paletta da mare,
un cucchiaio da cucina, un cucchiaino e così via ... riempio l'universo!
Secondo me non riempio neanche una buchetta, figurati.
--
Ciao, Silv:o)

non leggo neanche i vostri post prima di rispondere...
FACCIO AMMENDA HO DETTO UNA IMMANE CAGATA...
me ne sono accorto oggi in mensa mentre venivo ingaggiato da una piatto
stantio di pennette biologiche all'arrabbiata...
cosě per farmi perdonare ci ho pensato su per vedere se c'era una
scappatoia...
non l'ho ancora trovata, ma sono convinto che si possa risolvere l'enigma
anche senza sapere lo stato iniziale dell'interruttore... stavo pensando a
qualcosa del tipo che un detenuto commuta l'interruttore solo se ha visto
l'interruttore in entrambi gli stati (cioč se č entrato almeno 2 volte ed
una volta ha visto l'interruttore diciamo su OFF la prima volta e su ON
un'altra volta)...
boh... prima dell'esame cmq mi risparmio i neuroni...
ancora sorry e ciao a tutti...
  Ste

non sapendo lo stato iniziale dell'interruttore, il problema ha "quasi"
sempre soluzione...
mi spiego: supponiamo di essere nei panni del supervisore e di venire
interrogati per la prima volta. se vedessimo l'interruttore sulla posizione
opposta a quella che per convenzione abbiamo deciso che significhi "nel
tempo intercorso un collega del supervisore è stato interrogato per la prima
volta", capiremmo di sicuro di essere stati i primi ad essere interrogati.
dopodichè, quindi, procederemmo come già descritto ed arrivati a contare 31
colleghi, dichiareremmo che tutti hanno subito almeno un interrogatorio e
tutti i carcerati avrebbero salva la vita.
se al contrario, al nostro primo ingresso nella stanza degli interrogatori,
vedessimo che l'interruttore è sulla posizione che significa che un collega
è stato interrogato per la prima volta, capiremmo che quel segnale è
ambiguo. significa che l'interruttore era inizialmente in quella posizione o
che è stato messo in quello stato da un collega interrogato per la prima
volta? per questo motivo, giunti a contare 31 colleghi ci asterremmo dal
fare qualsiasi dichiarazione, non avendo la certezza matematica che tutti
siano stati interrogati almeno una volta.
se il segnale prestabilito dovesse giungerci per la 32° volta, capiremmo che
l'interruttore era inizialmente settato, faremmo la nostra dichiarazione e
saremmo tutti salvi. se quel segnale invece non dovesse giungerci, non
sapremmo mai se effettivamente tutti sono stati interrogati (ma noi non lo
abbiam capito per via della ambiguità iniziale), o se l'ultimo collega da
interrogare non è ancora stato interrogato per via del modo casuale con cui
i carcerati vengono scelti per l'interrogatorio. il supervisore, essendo un
puro logico, non si assumerebbe mai il rischio di fare la dichiarazione
anche dopo un tempo sufficientemente lungo e dunque tutti i carcerati
sconterebbero un ergastolo...
le cose doverbbero stare così...
ciao e scusate il post lungo e contorto,
  Ste

un flag non inizializzato semplicemente non porta informazione...
ma noi siamo più furbi di un flag e come puoi leggere nel mio penultimo
post, ragionando si riesce a risolvere il problema "quasi" sempre...
un flag non inizializzato non porta a nulla di buono ma anche a nulla di
cattivo!
sciocchezze a parte, tu che studi hai fatto/stai facendo?
ciao,
  Ste
PS: postate altri giochini come questo che sono bellissimi!!!

 sempre soluzione...
[cut]
Il tuo *quasi* è un po' relativo, supponiamo che la posizione iniziale
dell'interruttore sia completamente casuale. Dobbiamo ora decidere la
strategia del supervisore, dobbiamo vedere se fa la fatidica dichiarazione
dopo aver contato fino a 31 o se aspetta il 32 per *essere sicuro*.
Se arrivato a 31 tenta la sorte ci azzecca una volta su 2 e cioè solo se
l'interruttore è inizialmente su OFF.
Se invece aspetta il 32 penso che, in media, si sconta tutto l'ergastolo e
muore di vecchiaia. Infatti in un caso su due (posizione iniziale su OFF) ha
un valore aspettato di interrogatori pari ad infinito che, mediato con il
valore aspettato nel caso che inizialmente si abbia l'interruttore su ON, da
una media ancora infinita. (vi torna?)
Certo, si può aumentare la probabilità di salvezza a piacimento, si può
avere una probabilità di salvezza tanto prossima ad 1 quanto si vuole ma a
costo di aspettare un tempo tendente ad infinito.
Ciao,
Gabriele


Concordo in pieno! Altrimenti qui si parla solo di polimini! ;-)))))))
Ciao :-)
Giorgio

no no, come ho detto lui non tenta la sorte perchè siamo in un mondo di
logici che si rifiutano anche solo di considerare un azzardo...
nel caso sfortunato i carcerati rimarrebbero in enpasse... senza ombra di
dubbio...
la situazione si risolverebbe solo se effettivamente arrivasse il 32°
segnale...
che può arrivare perchè in quel caso i colleghi danno al supervisore 31
stimoli (che lui conta) più uno che gli deriva dalla posizione iniziale
dell'imnterruttore (in tutto effettivamente 32).
l'unico caso in cui si rimane bloccati è quello in cui quando il supervisore
vede l'interruttore su "già interrogati" la prima volta, questo è dovuto ad
un suo collega piuttosto che alla posizione iniziale...
se ci ragioni x assurdo vedrai che è così... stavolta ci ho pensato bene..
non avevo pennette all'arrabbiata che mi distraevano!
ciao,
  Ste
"Gabriele Carelli" <gas...@iol.it.toglimidaqui> ha scritto nel messaggio
news:BFR7c.5707$jY1....@tornado.fastwebnet.it...


io sono studente di ingegneria informatica... mi piacerebbe laurearmi con
indirizzo sviluppo software... chiedevo perchč ho notato che tu avevi
strumenti mentali per trovare la soluzione, mentre io non avendoli ancora
(mi sto tenendo gli esami di info alla fine per divertirmici) vado "alla
vecchia" cioč ragionandoci su ma sprecando un sacco di risorse...
volevo giusto carpire un po' dei tuoi "segreti" per modificare magari il
piano di studi! ;-)
so che voi "informatici puri" vi sollazzate coi "problemi dei filosofi a
tavola con gli arti deformi e poche posate" e che quindi siete
avvantaggiati! :-D
Per il resto algoritmo buono... algoritmo cattivo... le parole sono
convenzioni tra uomini... io lo ritengo "non cattivo" perchč ci piglia quasi
sempre... se ci pigliasse quasi sempre e fosse ottimizzato sarebbe ottimo...
tu lo chiami "non buono" invece perchč non č ottimo... il modus ragionandi
da ingengere che mi hanno inculcato mi dice che, in mancanza d'altro, un
algoritmo che ci piglia quasi sempre non fa poi cosě schifo! ;-)
Ma occorre perň trovare quello ottimo!
Secondo te si puň risolvere questo problema senza sapere lo stato iniziale
del flag?
Altri giochini come questo mancano.. potremmo incapponirci su questa
variante...
Ciao e scusate l'insistenza, ma č agitella pre-esame! :-D
Ste

 del flag?
Penso di no. Ma qui si entra nei problemi da "informatico puro" e anche un
po' masochistici, che non mi appassionano molto. :-)
Ciao e in bocca al lupo per i tuoi studi! :-)
Giorgio

 po' masochistici, che non mi appassionano molto. :-)
Ciao,
scusate l'intromissione di un lurker informatico :-)
Secondo me il problema si può risolvere anche non sapendo lo stato 
iniziale dell'interruttore.
Nel caso in cui si sappia che lo stato iniziale è 0, il "supervisore" 
conta le volte in cui lo trova su 1, e quando è arrivato a 31 è sicuro 
che tutti siano passati almeno una volta (posto che i detenuti passino 
l'interruttore da 0 a 1 una sola volta).
Se non sappiamo lo stato iniziale, ognuno dei 31 deve passare 
l'interruttore da 0 a 1 le prime *due* volte che ne ha la possibilità.
In questo modo, quando il supervisore ha contato fino a 62, sa che:
- se l'interruttore era inizialmente su 0, tutti i 31 sono passati 2 volte.
- se l'interruttore era inizialmente su 1, allora 30 detenuti sono 
passati 2 volte e uno è passato una volta sola.
In entrambi i casi tutti i detenuti sono passati almeno una volta. Non 
so se si possa fare di meglio, ma questo metodo funziona sempre.
Saluti
Nico

 variante...
non so tu, ma io spero di non ... incapponirmi mai !!!!!!
-- 
Ciao, Silv;o)

 .. Una volta scoperto che scopriamo che ..
ecco un esempio di codice non ottimizzato ;)
-- 
Silv:o)


:-))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))
Ciao :-)
Giorgio

 ha scritto nel messaggio
news:c3p4uj$291u9j$1...@ID-162977.news.uni-berlin.de...

Ciao a tutti,
mi intrometto anch'io....
Voi partite tutti dal fatto che il "supervisore" venga interrogato N volte.
Ma se il supervisore viene interrogato una volta sola? e magari è il primo
ad essere interrogato?

 un suo collega piuttosto che alla posizione iniziale...
Sono perfettamente d'accordo, il fatto è che quello che tu consideri "unico
caso" ha 1 probabilità su 2 di accadere (se consideriamo equiprobabile lo
stato iniziale dell'interruttore). Quindi nel 50% dei casi potresti
aspettare un tempo infinito senza ricevere il 32-esimo input: non mi sembra
che funzioni *quasi* sempre, funziona 1 volta su 2.
Ciao,
Gabriele

 ad essere interrogato?
L'OP dice che
"Sarete tutti sottoposti ad interrogatori continui, uno dopo l'altro in un
ordine qualsiasi e senza nessuna logica. Ognuno sarà interrogato quando e
quante volte ci pare ad insaputa degli altri, sarete interrogati uno per 
volta nella medesima stanza per quanto tempo sarà necessario."
Credo che, per il tipo di soluzione che prevede un supervisore (ammesso 
che ne esistano altre) ci sia un'assunzione implicita, cioè che la frase 
sopra implica che, se t è il tempo e N(t) è il numero di volte che una 
persona è stata chiamata chiamata, allora [lim(t->oo) N(t)]>M, con M 
grande a piacere (oo sta per infinito :-)
Se questa assunzione non è giustificata (ed è plausibilissimo) allora 
entrambe le soluzioni date (la mia e quella per lo stato noto 
dell'interruttore) non sono valide, o almeno non sono deterministiche :-)
Saluti
Nico

 so se si possa fare di meglio, ma questo metodo funziona sempre.
Lo sai che mi hai convinto? Bravissimo, mi sembra proprio una bella
soluzione.
Non pensavo si potesse fare e quindi all'inizio ho letto con un po' di
scetticismo la tua mail, ti chiedo scusa.
Complimenti,
Gabriele
P.S. per d_daves: naturalmente partiamo dall'assunto che, avendo a
disposizione un tempo teoricamente infinito, ognuno viene interrogato N
volte (con N grande a piacere) con probabilità 1. Naturalmente il direttore
del carcere potrebbe fare come dici te, ma potrebbe anche chiamarli tutti
tranne 1 e quindi il gioco non si pone proprio, ipotizziamo che chiami
completamente a caso.

 completamente a caso.
e se diamo una distribuzione di probabilità uniforme alla variabile 
casuale "persona chiamata" (ad esempio) funziona tutto, se il direttore 
è bastardo e scopre il metodo invece no :-)
Ciao
Nico


Se è per questo, il supervisore potrebbe anche venire interrogato un milione
di volte (e anche tutti gli altri) e non essere comunque in grado di dire
alcunché. Ad esempio perché vengono tutti interrogati prima di lui oppure
(se proprio non vogliamo pensare che venga interrogato da solo alla fine per
un milione di volte) che si alterni negli interrogatori con tutti gli altri
tranne uno che non viene interrogato più.
La tua osservazione (in forma un po' più corretta) è comunque già stata
fatta da Bl@de con relativa risposta di Gabriele.
Siamo tutti consapevoli che questo metodo funziona solo se si verificano
certe determinate condizioni. E' però anche vero che ti garantisce che non
rischierai mai la vita. Allora le alternative sono: o trovi un metodo
migliore, o usi questo sperando che ti vada bene o rinunci e te ne stai in
galera a vita o magari ti affidi al caso rischiando di morire. Tu
rinunceresti in partenza al metodo, solo perché non hai la certezza assoluta
della riuscita?
Ciao :-)
Giorgio

 ha scritto nel messaggio
news:c3pjtl$2acki8$1...@ID-56302.news.uni-berlin.de...

Scusa se insisto. Aggiungo anche una premessa che prima non ho fatto: sono
nuovo del ng e non sono esperto di questi giochi. Sto solo cercando di
entrare nell'ottica delle cose. Spero che possiate perdonarmi.
Credo però che alla base di tutto ci siano troppe condizioni che devono
essere rispettate. Non parlo di certezza assoluta, però nella vostra
soluzione il supervisore deve essere interrogato N volte fino a quando non
ha trovato l'interrutore 31 volte su ON ( o 62 come in altre soluzioni).
Quindi mi chiedo: se due carcerati vengono interrogati per la prima volta
uno dopo l'altro, il primo mette l'interruttore su on, il secondo no. Quindi
il secondo lo metterà la volta dopo (sperando che nel frattempo sia passato
il supervisore). Ma se non viene più interrogato? Alla fine del giro il
supervisore avrà contato 30 anche se in realtà sono stati interrogati tutti.
Quindi?
Ciao e scusa ancora

 ha trovato l'interrutore 31 volte su ON ( o 62 come in altre soluzioni).
Questa è la mia opinione (ovviamente discutibile):
La condizione è fondamentalmente una, cioè quella che Gabriele e io 
abbiamo scritto in altri post. Il fatto che sia una non sigifica che sia 
poco restrittiva, però.
Ad ogni modo, anche accettando la condizione, il numero di interrogatori 
che vengono effettuati tra il momento in cui tutti i prigionieri sono 
passati almeno una volta e il momento in cui il supervisore se ne rende 
conto e lo annuncia, è sicuramente molto alto...
Però, secondo me, è un gioco di logica, e il fatto che, al ritmo di un 
interrogatorio all'ora, il supervisore ci impieghi anni a capire che 
tutti sono stati interrogati è abbastanza marginale. Se esistono 
soluzioni migliori, meglio, ma questa mi basta.
E' un po' come l'approccio matematico "ho scoperto che esiste una 
soluzione... non so come calcolarla, ma che mi frega" :-)
Se invece si considera che il direttore, da un certo momento in poi, 
possa decidere che non chiamerà MAI PIU' (all'infinito) una certa 
persona, che ha già chiamato ma non ha potuto muovere l'interruttore, 
allora la soluzione non funziona. Ma la condizione è solo questa.
Ciao
Nico

Capisco cosa intendi, non mi sono espresso bene...
Ma non è esatto nemmeno quello che sostieni tu: il valore esatto è 50% -
Epsilon, perchè non bisogna dimenticare il caso (raro ma pur sempre
possibile) in cui il supervisore venga interrogato per primo...
Per unico caso che non portava a soluzione io intendevo unica alternativa
logica che non portava a soluzione. Se disegnamo un albero binario a partire
da ragionamento esposto, una sola foglia non porta a soluzione...
Comunque sorry!
Ciao,
  Ste
"Gabriele Carelli" <gas...@iol.it.toglimidaqui> ha scritto nel messaggio
news:XkX7c.6304$jY1....@tornado.fastwebnet.it...


CAVOLO!!! IL FAMOSO BIT DI PARITA'!!!
:-D

 possibile) in cui il supervisore venga interrogato per primo...
Secondo me è sempre 50%, perché il supervisore non sa di essere il 
primo, e quindi per lui è obbligatorio spegnere e contare 1, e quindi 
mandare a monte tutto il calcolo.
Non credo che uno possa sapere di essere il primo interrogato (questa 
almeno è la mia interpretazione :-)
Ciao
Nico

 almeno è la mia interpretazione :-)
Come non sa di essere il primo! Leggi di seguito:
ON = "sono stato interrogato per la prima volta o è la prima volta che
riesco a segnale che mi hanno interrogato una volta"
OFF = - contrario di ON -
Caso A (interruttore inizialmente su ON)
Il supervisore entra effettivamente per primo, ma non può capire se e quanti
sono stati interrogati prima di lui. Non sa come considerare l'ON che vede:
- non sono stato il primo ad entrare ma l'interruttore era già su ON e non
dovrei contare questo segnale
- non sono stato il primo ad entrare e l'interruttore è stato messo su ON da
un collega, quindi dovrei contare questo segnale
- sono entrato per primo e l'interruttore era fià su ON e non dovrei contare
questo segnale
Se non è il supervisore il primo ad entrare, significa che almeno un suo
collega entra prima di lui nella stanza e vedendo l'ON, capirà che:
- un altro carcerato ha già fatto sapere al supervisore che è stato
interrogato o l'interruttore era già così da prima, io comunque non devo
fare niente
Caso B (interruttore inizialmente su OFF)
Se non è il supervisore il primo ad entrare, significa che almeno un suo
collega entra prima di lui nella stanza e vedendo l'OFF, capirà che:
- l'interruttore era già nella posizione iniziale giusta o il supervisore lo
ha già resettato, il mio compito comunque è di fargli sapere che sono stato
interrogato
Se invece il supervisore entra effettivamente per primo, e vede
l'interruttore su ON, dedurrà che:
- se l'interruttore fosse stato inizialmente su ON, nessuno lo avrebbe
spostato e io l'avrei visto su ON. lo vedo su OFF quindi non è questo caso
- se l'interruttore fosse stato inizialmente su OFF e non fossi stato il
primo, quell'altro l'avrebbe messo su ON, ma io lo vedo su OFF quindi non è
questo caso
- se l'interruttore fosse stato inizialmente su OFF e io fossi il primo,
dato che nessuno avrebbe avuto la possibilità di metterlo su ON, io lo
vedrei su OFF, ma lo vedo su OFF dunque avendo considerato tutti i casi
possibili, io devo proprio essere il primo ad essere interrogato. questo mi
fa molto piacere perchè così non ho casi ambigui da considerare per il conto
dei segnali
Tornando alle probabilità, visto che il capo della prigione non sa chi sia
il supervisore non ha motivo di preferire un carcerato piuttosto che
un'altro e dunque almeno inizialmente sceglierà completamente a caso
(probabilità di estrazione equamente distribuite). La probabilità che esca
proprio il supervisore è proprio 1/C con C numero di carcerati, nel nostro
caso 1/32.
La probabilità che l'interruttore inizialmente sia su un certo stato è
ovviamente 1/2.
Dunque (supponendo che il gioco continui per un tempo sufficientemente
grande e che il capo della prigione non abbia motivo di scegliere i
carcerati da interrogare anche nel seguito del gioco, cioè pescando sempre a
caso) si ha che:
- se il supervisore è il primo ad entrare (1/32) e l'interruttore è su OFF
(1/2), prima o poi arrivano al supervisore 31 segnali e riescono a risolvere
il problema (in tutto 1/32 * 1/2 = 1/64)
- se il supervisore è il primo ad entrare (1/32) e l'interruttore è su ON
(1/2), prima o poi arrivano al supervisore 32 segnali (di cui uno dovuto
allo stato iniziale dell'interruttore) e anche in questo caso riescono a
risolvere il problema (in tutto 1/32 * 1/2 = 1/64)
- se non è il supervisore il primo ad entrare (31/32) e l'interruttore è
inizialmente su ON (1/2), sostanzialmente succede quanto detto al punto
precedente, cioè il supervisore conta 32 segnali (di cui dovuto allo stato
iniziale dell'interruttore) e riescono comunque a risolvere il problema (in
tutto 31/32 * 1/2 = 31/64)
- infine, se non è il supervisore il primo ad entrare (31/32) e
l'interruttore è inizialmente su OFF (1/2), il supervisore conta solo 31
segnali. se passasse un tempo infinito ed il 32 segnale non fosse ancora
arrivato, capirebbe di trovarsi in questo caso, ma non potendo aspettare un
tempo infinito, il supervisore non riuscirebbe mai a dare soluzione al
problema. Questo è dunque il solo caso che non porta a soluzione, in tutto
pari a 31/32 * 1/2 = 31/64
Ai casi che portano a soluzione corrisponde dunque una probabilità totale
di: 1/64 + 1/64 + 31/64 = 33/64 pari al 51,6% dei casi totali.
Mentre all'unico caso che non porta a soluzione compete la probabilità di
31/64 (giusto, è il negato di 33/64) pari al 48,4% dei casi totali.
Ebbene, vi ho rotto per benino le scatole con questo post così lungo anche
se tutti ormai sappiamo che il metodo per avere sempre soluzione è un altro,
quello proposto da Nico!
Ciao,
  Ste

 Come non sa di essere il primo! Leggi di seguito:
Ops! hai ragione :-) Il supervisore (e solo lui) può sapere di essere il 
primo qualora trovi l'interruttore su OFF. Mea culpa :-)
Io avevo detto
 >>Secondo me è sempre 50%, perché il supervisore non sa di essere il
 >>primo, e quindi per lui è obbligatorio spegnere e contare 1, e quindi
 >>mandare a monte tutto il calcolo.
ed è vero, se trova ON (spegne e conta 1, anche se porterà ad un 
conteggio sbagliato). Ma se trova OFF sa di essere il primo, e sa che 
quindi il suo conteggio sarà corretto.
Ciao
Nico

 sono sicuro che il tizio 1 1 1 1 1 e' stato interrogato.
Devo non aver capito, perché nel mio esempio, nella seconda riga è stato 
chiamato il 21 nello slot 0, il 10 nello slot 1, ecc...
Non funziona o (più probabilmente) mi sono perso qualcosa?
A proposito, chi dice che i prigionieri hanno a disposizione un 
orologio? :-)
Ciao
Nico

 Non ho ben capito il ragionamento: 
Ritiro tutto :-)
Ciao
Nico


Ok, potrei correggere un attimino la cosa osservando che
non devo per forza aspettarmi che tutte le colonne abbiano
almeno 16 zeri e 16 uni.
Credo che basterebbe:
15 zeri e 16 uni nella colonna i-esima se il bit i-esimo del mio codice = 0
altrimenti 16 zeri e 15 uni.
Questo per evitare di cercare di ottenere anche la combinazione riga
corrispondente anche al mio codice, cosa inutile, dato che sono 
sicuramente stato interrogato e non serve andarlo a verificare con quel 
sistema che ho proposto.

 I 10 minuti cominciano ... ADESSO!".
Dopo i fatidici 10 minuti, i carcerati escono sconsolati dalla stanza senza
essere riusciti ad escogitare alcunché e si avviano mesti verso le loro
celle di isolamento accompagnati dai relativi carcerieri. Uno di questi
carcerieri però, dal cuore tenero, fa una proposta al suo carcerato:
"Ho pensato che, invece di accompagnarti nella cella che ti è stata
assegnata, potrei accompagnarti in un'altra cella che ha una particolarità:
dalla sua finestra puoi comodamente vedere chi entra nella stanza degli
interrogatori. Non preoccuparti, nessuno si accorgerà dello scambio di
cella."
Al che il carcerato riflette: "E' facile! Basta che conti tutti quelli che
entrano per la prima volta nella stanza e quando il conto raggiunge 31 sono
certo che siano entrati tutti! ... Però c'è un problema: io ogni tanto dovrò
pure dormire e se uno o più di uno dei miei compagni vengono interrogati
sempre e solo quando dormo, come posso contarli? E se, anche ammesso che sia
riuscito a contarli tutti, non vengo più interrogato io?"
Quindi si rivolge sconsolato al carceriere: "Ti ringrazio per la proposta ma
non la posso accettare. Ci sono troppe condizioni che devono essere
rispettate. Accompagnami pure nella cella cui ero destinato."
A sentire queste parole, al carceriere cascano le ... Opps, scusate.
A sentire queste parole, il carceriere si incapponisce!
Ciao ;-)
Giorgio


Non lo vedo nemmeno io...
A parte gli scherzi, penso che il tuo metodo si basi sulla capacità di
stabilire lo slot temporale in cui quello che ti ha preceduto è stato
interrogato. E come fai? Forse presumi che ogni ora sistematicamente venga
interrogato un carcerato? Nessuno ha detto che ciò avvenga, anzi il
direttore dice: "Ognuno sarà interrogato quando e quante volte ci pare...".
Ciao :-)
Giorgio

complicato, ma bello...
solo che nell'esposto non si parla di orologi, fogli di carta e penne... ;-)
ciao,
 Ste

 O forse non c'è sufficiente spazio nei margini... :-)
lol
Fai bene ad essere scettico, perche' ho appunto trovato una cosa che mi 
smentisce.
Facciamo che vi sono 4 prigionieri:
i codici sono 00 01 10 11.
avrebbe dovuto verificarsi, se avessi avuto ragione, ad esempio, che:
- Se c'e' uno che non viene mai chiamato, allora la mia tebella non 
arriva mai alla "condizione di uscita":
Invece:
il mio codice facciamo che sia 00, e chi non viene mai chiamato sia 11
quelli che mi hanno preceduto possono essere 10 o 01, allora
nella mia tabella posso avere nello slot 0 sia degli uni che degli zeri.
E posso avere nello slot 1 sia degli uni che degli zeri.
Quindi potrei avere:
0   1
-----
1   0
0   0
0   1
1   1
1   1
ovvero:
una volta mi ha preceduto 10 nello slot 0 ed ho segnato 1 alla prima colonna
una volta mi ha preceduto 01 nello slot 1 ed ho segnato 0 alle seconda 
colonna
una volta mi ha preceduto 01 nello slot 0 ed ho segnato 0 alla prima colonna
una volta mi ha preceduto 10 nello slot 1 ed ho segnato 0 alla seconda 
colonna,
etc...
ho almeno 1 zero e due uni in ogni colonna
(solo uno 0 e non due perche' escludo degli zeri che fanno parte del 
*mio* di codice), e credo di poter uscire, ma non e' vero perche' 11 non 
e' mai stato chiamato.
Quindi insomma il mio enunciato e' sostenzialmente falso.
Posso notare che dal punto di vista statistico le informazioni nella 
tabella sono comunque interessanti:
per esempio siccome 11 non e' stato mai chiamato, allora ho un numero 
molto minore di quanti me ne dovrei aspettare di uni (in entrambe le 
colonne)
se tutti vengono chiamati, statisticamente la distribuzione degli 1 e 0 
in ogni colonna dovrebbero  avvicinarsi a:
2/3 di uni e 1/3 di zeri.
Infatti se mi precedono i tizi: 10, 01, 11 allora posso avere:
1 in prima oppure 0 in seconda (se mi precede 10)
0 in prima oppure 1 in seconda  (se mi precede 01)
1 in prima oppure 1 in seconda   (se mi precede 11)
.....
a lungo andare quindi sono 2/3 di uni e 1/3 di zeri in entrambe le colonne.
Se invece appunto 11 non viene mai chiamato, allora avrei:
1 in prima oppure 0 in seconda
0 in prima oppure 1 in seconda
. . . .
che tende alla proporzione 1/2 1/2 di uni e zeri, che mi indica che
qualcosa non va.
[...]

 
ovviamente: "rilevazioni"
[...]


Ecco appunto...
Ciao :-)
Giorgio

Stefano Bragaglia wrote:

Ti ringrazio, ma non sono d'accordo sulle tue obiezioni.
Si dice ai carcerati che hanno 10 minuti per mettersi d'accordo.
Quindi il tempo e' una variabile che si puo' considerare.
Se la si puo' considerare per verificare che sono passati 10 minuti, la 
si puo' considerare anche successivamente, se non e' specificato 
diversamente, secondo me.
Per quanto riguarda il foglio di carta e penna:
possono incidere sul muro della cella delle scritte,  o possono 
strapparsi dei peli dal proprio corpo e disporli in un certo modo da 
formare delle scritte, o possono fare tutto a mente.
Devono dimostrare di essere dei perfetti logici, e quindi devono anche 
avere un supporto di memoria su cui scrivere (che sia la carta, che sia 
il muro, che siano i propri neuroni, che sia un nastro infinito): un 
logico e' anche un calcolatore (nel senso di Turing), e un calcolatore 
deve avere una memoria su cui scrivere informazioni.
Ciao
T.


Comincio a capire la tua interpretazione della frase: "Sarete tutti
sottoposti ad interrogatori continui, uno dopo l'altro in un ordine
qualsiasi e senza nessuna logica."
Tu quel "continui, uno dopo l'altro" lo intendi come una processione
continua senza soste. Mi sembra un'interpretazione un po' rigida. Per
"interrogatori continui" io intendo semplicemente che andranno avanti per un
bel po' di tempo e con un certo ritmo, ma senza escludere che ogni tanto
decidano di fare una pausa (per mangiare, per andare in bagno e magari ogni
tanto per dormire). Ed è sufficiente una pausa di un'oretta ogni tanto per
fare crollare tutto il metodo.
Ciao :-)
Giorgio

passi carta e penna (anche se io potendomi strappare peli e lasciare un
messaggio preferirei lasciar scritto: "io carcerato tal dei tali sono già
stato interrogato, quindi colleghi, fate un po' voi!")... ma non l'orologio!
il direttore potrebbe contare i primi 10 minuti per loro avvalendosi di un
cronometro, ma non fornire ai carcerati alcun supporto per tener conto del
tempo che passa...
i carcerati potrebbero contare continuamente da 1 fino a 600 per contare 10
minuti, ma ragionare e contare assieme diverrebbe complesso e logorante...
e poi è quasi impossibile che tutti loro contino il passare dei secondi in
perfetta sincronia, questi errori di misura del tempo sarebbero
trascurabili, ma solo inizialmente!
passi la macchina di turing, ma tu presumi che tutti i carcerati abbiano un
clock esatto e che il clock sia esattamente uguale per tutti... no, non è
plausibile!
a questo punto, SOLUZIONE BIZZARA:
ogni volta che un carcerato entra nella stanza, si disinteressa
completamente dell'interruttore, e tira un gran catarro contro il muro, in
modo da lasciare traccia inequivocabile del proprio passaggio. l'assunto non
vieta ai carcerati di sputare, nè ci dice che la stanza degli interrogatori
viene rassettata dopo ogni utilizzo, quindi quando un cercerato entra e
conta N-1 sputi, sa che tutti sono stati interrogati, fa la sua
dichiarazione e salva tutti.
Lo so, questo è barare! ;-)
Ciao,
  Ste

 tanto per dormire). 
Se dedichi mediamente 45 minuti al giorno per essere interrogato, il 
tempo di fare tutte queste cose ce l'hai.


 stato interrogato, quindi colleghi, fate un po' voi!")
Non puoi comunicare con gli altri carcerati in nessun modo se non 
modificando lo stato dell'interruttore.
