Newsgroup: it.hobby.enigmi
Titolo: Re: Problema delle luci

 acceso, quale strategia dovranno adottare?
Problema interessante, ma OT sul gruppo di matematica (vedi
manifesto).
Lo rilancio su it.hobby.enigmi

Il 10-12-2007, Il Bragozzi dice:


spoiler, ma mi sembra troppo facile... sara' sbagliato!
Ognuno degli n prigionieri adotta questa strategia.
-- solo la prima volta inverte l'interruttore
-- tutte le altre volte lo lascia immutato
-- conta  quante volte lo trova scambiato
-- il conto lo fa partire dalla prima volta: c=1
-- ogni volta ognuno dice: "non lo so"
-- finche' uno di loro non raggiunge c=n
-- costui sara' necessariamente il primo chiamato.
-- 
Saluti, Dalet


Non mi è chiaro cosa significa "lo trova scambiato". Scambiato
rispetto a cosa? A come lo aveva lasciato lui?
In ogni caso, per funzionare il tuo metodo necessita delle modifiche.
Altrimenti, già nel caso in cui i prigionieri vengono chiamati in
ordine (1, 2, 3, .... n), fallirebbe perché ognuno raggiungerebbe un
conteggio di c=1 e poi l'interruttore non verrebbe più toccato da
nessuno.
Il metodo "corretto" sarebbe:
(spoilers)
.
.
.
.
.
.
-Viene stabilito un prigioniero che faccia da "contatore".
-Solo costui può spegnere la luce quando la trova accesa (e,
spegnendola, aumenta il suo conteggio da c a c+1)
-Tutti gli altri, la prima volta che trovano la luce spenta, la
accendono. Se la trovano già accesa, non fanno niente. Se la trovano
spenta ma l'avevano già accesa in passato, non fanno niente.
-Ovviamente, non sapendo qual è lo stato iniziale della lampadina, il
prigioniero che entrerà per primo la accende se era spenta, la lascia
accesa (contando come se l'avesse accesa lui) se era accesa.
-Quando il contatore raggiunge il conteggio di n (compreso se stesso),
il gioco finisce.
-Ma c'è un ostacolo: con l'enunciato esposto qui del problema, come fa
il primo prigioniero a essere il primo???
In realtà, di questo problema si è già dibattuto. Vedi per esempio:
<
http://groups.google.com/group/it.hobby.enigmi/browse_frm/thread/
37790e73fead1801/65dcc41a5c3034c8?
hl=it&lnk=gst&q=lampadina#65dcc41a5c3034c8>
L'unica differenza è che stavolta viene detto che i prigionieri
vengono convoncati "a intervalli di tempo irregolare", il che oltre a
causare l'ostacolo di cui sopra, elimina le soluzioni che si basavano
sul conteggio dei giorni.
Nel thread citato, però, non si era ancora giunti a trovare la
soluzione ottimale. La sfida è ancora aperta!
Ciao!

 il primo prigioniero a essere il primo???
Leggi: a _sapere_ di essere il primo???
Ciao!

rispetto a cosa? A come lo aveva lasciato lui?
Si', ma e' chiaro che non va: possono andarcene 2, 4, 6...
prima che lui ritorni, TNX (me lo sentivo che era troppo
semplice come soluzione).
-- 
Saluti, Dalet

soluzione ottimale. La sfida è ancora aperta!
Con questo contatore che dici mi sembra semplice... sara'
sbagliato ancora!?
Tutto come dici tu, ma con la condizione che ognuno
la deve spegnere due volte e il contatore basta che
raggiunga 2(n-1).
Esempio.
sono 5, nasce accesa: c=8, OK: tutti 2 volte uno una volta
sono 4, nasce accesa: c=3, OK: tutti 2 volte
sono 5, nasce spenta: c=8, OK: tutti 2 volte
sono 4, nasce accesa: c=3, OK: tutti 2 volte.
-- 
Saluti, Dalet


Se ho inteso bene il problema, non credo che questi metodi funzionino.
Difatti un singolo prigioniero può essere chiamato più di una volta, 
senza un'ordine particolare, per cui magari Tizio è stato convocato 100 
volte, Caio nemmeno una (fino a quel momento).
m.
-- 
"La legge, in Italia, è come l'onore delle puttane"
(Curzio Malaparte)