Re: Problema delle luci
Il Bragozzi
> Vorrei proporre questo problema, anche se forse è un po' vecchio.
> Ad un numero n di prigionieri viene data la possibilità di salvarsi se
> riusciranno a risolvere un rompicapo: i prigionieri vengono messi in celle
> buie separate tra loro, in modo che non possano comunicare e avere nozione
> del tempo.
> A intervalli di tempo irregolari, viene chiamato un prigioniero a caso (lo
> stesso prigioniero può essere chiamate tre volte di fila senza accorgersene)
> dalla sua cella,e portato in una stanza particolare senza che gli altri se
> ne accorgano. La stanza è completamente vuota, a parte una lampadina con un
> interruttore, che il prigioniero può accendere, spegnere o lasciare
> invariato. Dopo essere stato condotto nella stanza, al prigioniero viene
> chiesto se tutti i prigionieri sono stati nella stanza.
> Se sbaglia, tutti i prigionieri vengono uccisi. Se afferma che tutti i
> prigionieri siano stati nella stanza, ed è vero, allora i prigionieri
> vengono liberati. Altrimenti se non risponde, il prigioniero viene rimandato
> nella cella, e il procedimento ricomincia. I prigionieri hanno però
> all'inizio la possibilità di mettersi d'accordo e di adottare una strategia
> comune. Considerato che non sanno se inizialmente l'interruttore è spento o
> acceso, quale strategia dovranno adottare?
Problema interessante, ma OT sul gruppo di matematica (vedi
manifesto).
Lo rilancio su it.hobby.enigmi
Dalet
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
Il raccattapalle
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 raccattapalle
> -Ma c'è un ostacolo: con l'enunciato esposto qui del problema, come fa
> il primo prigioniero a essere il primo???
Leggi: a _sapere_ di essere il primo???
Ciao!
Dalet
>On 10 Dic, 18:33, Dalet <da...@tiscali.it> wrote:
>Non mi è chiaro cosa significa "lo trova scambiato". Scambiato
>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
Dalet
>>On 8 Dic, 18:53, "Paolo" <thekanga...@libero.it> wrote:
>>>Vorrei proporre questo problema, anche se forse è un po' vecchio.
>>>Ad un numero n di prigionieri viene data la possibilità di salvarsi se
>>>riusciranno a risolvere un rompicapo: i prigionieri vengono messi in celle
>>>buie separate tra loro, in modo che non possano comunicare e avere nozione
>>>del tempo.
>>>A intervalli di tempo irregolari, viene chiamato un prigioniero a caso (lo
>>>stesso prigioniero può essere chiamate tre volte di fila senza accorgersene)
>>>dalla sua cella,e portato in una stanza particolare senza che gli altri se
>>>ne accorgano. La stanza è completamente vuota, a parte una lampadina con un
>>>interruttore, che il prigioniero può accendere, spegnere o lasciare
>>>invariato. Dopo essere stato condotto nella stanza, al prigioniero viene
>>>chiesto se tutti i prigionieri sono stati nella stanza.
>>>Se sbaglia, tutti i prigionieri vengono uccisi. Se afferma che tutti i
>>>prigionieri siano stati nella stanza, ed è vero, allora i prigionieri
>>>vengono liberati. Altrimenti se non risponde, il prigioniero viene rimandato
>>>nella cella, e il procedimento ricomincia. I prigionieri hanno però
>>>all'inizio la possibilità di mettersi d'accordo e di adottare una strategia
>>>comune. Considerato che non sanno se inizialmente l'interruttore è spento o
>>>acceso, quale strategia dovranno adottare?
>>spoiler, ma mi sembra troppo facile... sara' sbagliato!
>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???
[--taglio]
>Nel thread citato, però, non si era ancora giunti a trovare la
>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
Ministry
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)