Domanda: ai prigionieri è concesso sapere se il prigioniero precedente è stato ammazzato oppure no?
Su questo ci devo ancora pensare, ma intanto ne propongo un altro. Chi bazzica xkcd forse l'ha già sentito e magari anche risolto, ma per gli altri può rivelarsi carino; avviso che è un po' difficilotto, ma non richiede conoscenze pregresse particolari, solo logica elementare.
Visto che xkcd s'è preso la briga di formularlo in modo non ambiguo (per quanto non l'abbia inventato lui), quoto direttamente da lui.
> A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.
> On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
> The Guru is allowed to speak once (let's say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:
> "I can see someone who has blue eyes."
> Who leaves the island, and on what night?
> There are no mirrors or reflecting surfaces, nothing dumb. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language or doing genetics. The Guru is not making eye contact with anyone in particular; she's simply saying "I count at least one blue-eyed person on this island who isn't me."
> And lastly, the answer is not "no one leaves."
>> #1
Sì, altrimenti credo sia impossibile (ma attendi la conferma di Square).
Il fatto cruciale è che ogni prigioniero (tranne un numero finito che può essere preso uguale a 1), nel momento in cui viene interrogato, possiede tutta l'informazione sulla sequenza di colori. Il bit mancante (dovuto al fatto che un prigioniero non conosce il proprio colore) viene generato nel momento in cui il secondo prigioniero riceve dal primo sia il bit del suo "azzardo" sia quello del risultato di tale azzardo, per un totale di due bit. La soluzione deve implicare che questa informazione venga propagata per l'intera catena di modo che un numero cofinito di prigionieri sia nella condizione di dedurre il proprio colore in modo deterministico.
>> #1
No, ai prigionieri non serve sapere se quelli prima di loro sono vivi o morti.
>> #4
Azz, allora sto sbagliando approccio completamente. Mi sa che bisogna scomodare matematica vera per risolverlo con quel vincolo, e dubito di esserne in grado.
ma sono infiniti, che ci frega, basta dicano tutti lo stesso colore e anche se si dimezzano restano inifniti, no?
>> #0
Se per seduta stante non intendi che appena il prigioniero dice "A" lo ammazzano forse ho una soluzione. Uno dei prigionieri si sacrifica per urlare ad alta voce i colori dei cappelli nell'ordine in cui li vede e per fare più veloce usa solo le iniziali (es.: B N N B B N...).
Sono molto nabbo per quanto riguarda gli indovinelli e questa strategia mi pare troppo facile per essere la soluzione esatta, quindi se sbaglio non sarà una sorpresa per me.
>> #7
Porca puttana, ho dimenticato di spoilerare.
>> #7
Credo sia scontato che ogni prigioniero può solo dire "bianco" o "nero".
Io una soluzione per il caso finito, e in effetti sono in grado di ridurre il rapporto morti/sopravvissuti sotto qualunque fissata successione positiva, ma non di farne morire solo un numero finito. Dopo magari la scrivo.
>> #6
No, si richiede che ne muoia un numero finito.
Ok, soluzione per il caso finito.
In quanto segue chiamo 0 il nero, 1 il bianco e "somma" la somma modulo 2 (XOR). Il prigioniero #0 dichiara la somma dei colori da #1 a #9.
Il prigioniero #1 conosce tutti i colori da #2 a #9 e anche la loro somma S, quindi sommando S a tutti i colori che conosce può estrarre il proprio (così ora #2 conosce pure 8 colori più la loro somma). Con lo stesso ragionamento, se il prigioniero #k-1 conosce S e i colori da #1 a #9 eccetto il proprio, può fare la somma per ricavarlo. Per induzione su k, questo permette di salvare tutti i prigionieri tranne al più il #0.
Questa strategia permette di rendere il rapporto morti/sopravvissuti un o-piccolo di qualunque funzione positiva e decrescente, ma purtroppo non di salvare un numero cofinito di prigionieri.
È evidente che il ragionamento di cui sopra funziona qualunque sia il numero (finito) di prigionieri: se sono M+1, permette di salvarne M. Nel caso infinito il ragionamento fallisce perché salvo casi particolari, le somme parziali dei colori non convergono, e quindi non si può definire quella che ho chiamato S.
I prigionieri possono accordarsi in anticipo su una successione {a_n} di numeri naturali, e dividere la linea infinita in pezzi lunghi a_n, per poi applicare la strategia di cui sopra a ciascuna parte (ora finita) di linea. Questo permette di salvare ~ a_n/n prigionieri, per cui, prendendo {a_n} crescente in modo rapido a piacere, il rapporto morti/sopravvissuti è ordine n/a_n, decrescente in modo arbitrariamente rapido. Notare che un numero infinito di prigionieri è comunque destinato a morire.
Casi particolari possono essere trattati con successo:
- se la successione di colori è definitivamente costante, una strategia vincente è che ciascuno dichiari il colore definitivamente costante;
- più in generale, se la successione è definitivamente periodica, allora può essere interpretata come l'espansione in binario di un razionale, che può essere comunicato agli altri giocatori in un numero finito di bit, sacrificando un numero finito di prigionieri (è necessario qualche accorgimento per codificare non ambiguamente questo numero, ma si può fare; se volete dettagli chiedete);
- ancor più in generale, se la lettura binaria della successione di colori definisce un irrazionale quadratico, si può codificare questo numero in un numero finito di bit in quanto la sua frazione continua è periodica;
- e infine, la cosa più generale che mi viene in mente è che se la lettura binaria della successione di colori è esprimibile in termini di un algoritmo calcolabile ed esprimibile in un numero finito di bit, si può codificare (ad esempio in ASCII) l'espressione di questa funzione con un numero finito di sacrifici e salvare tutti gli altri.
Ad esempio, se la successione di colori codifica 1/e, scrivere "sum from 0 to inf (-1)^k/k!" richiede una manciata di bit, e se i prigionieri si erano messi d'accordo sull'alfabeto e sulla codifica, possono comunicare questa informazione per salvare tutti i prigionieri successivi.
Si noti che la scelta della strategia avviene prima che vengano messi in fila, e un'eventuale scelta in "runtime" può essere effettuata con un piccolo overhead di sacrifici (analogamente a come una macchina di Turing universale viene preprogrammata come parte del programma stesso).
per me basta calciare la sedia davanti. se hai il cappello bianco quello dietro ti tira un calcetto a destra, se è nero a sinistra (o qualunque altro segnale convenuto). ovviamente l'unico che resta fuori è il primo, che riesce a dare il segnale al secondo prima di morire.
>> #12
Questo però non vale, perché
> non può in alcun modo girare la testa o comunicare con gli altri prigionieri
...e questo è "comunicare" a tutti gli effetti.
>> #12
Fai conto che ci sono infiniti boia ognuno con una pistola puntata alla tempia di ognuno degli infiniti prigionieri e nell'esatto istante in cui questi accennano a fare qualcosa di diverso dal respirare o dal dire "bianco" o "nero" quando interrogati gli sparano.
Tanto sono infiniti.
sono 12, e provo a sistemare la cosa così: invece che dare un segnale troppo intuibile lo si da mischiato nel colore del cappello. quando provo a dire il colore del mio cappello (e qui c'è sempre il numero 1 sacrificabile) lo dico con un tono particolare. se lo dico lentamente allora il prigioniero davanti ha un cappello nero, se lo dico velocemente allora quello davanti l'avrà bianco.
>> #15
Sono infiniti, prima o poi i boia se ne accorgono.
>> #16
Cercare logica in questo thread è un suicidio, smetti finché sei in tempo
>> #16
è la risposta ufficiale dell'OP?
ITT: la gente non sa cosa sia un puzzle di logica.
> una prigione con un numero infinito di prigionieri
è una metafora dell'Universo, vero?
>> #18
non sono OP, sono uno che non è in grado di usare la matemagica e quindi va dietro all'altro sasso che cerca di usare espedienti in un indovinello logico
>> #19
La logica è diversa dalla matematica.
>> #22
L'acqua è diversa dal ghiaccio.
Rettifico e amplio: la logica di tutti i giorni è diversa dalla matematica, perché la matematica per non andare matta deve per forza di cose proporre sistemi semplificati.
Ovvero, è inutile cercare di trovare scappatoie logiche da un indovinello matematico perché, essendo un indovinello matematico, è fatto per essere risolto con la matematica ed è futile cercare altre vie.
Tl;dr: Non so abbastanza matematica per risolvere questi indovinelli e mi rode un sacco
"Scappatoie logiche"? Anon, what?
Scappatoie, cavilli, loophole, come li vuoi chiamare.
>> #12
L'idea è che ogni prigioniero può comunicare esattamente un bit di informazione ai prigionieri successivi, quindi codici legati a movimenti, toni di voce o pronunce strane non valgono.
Tra l'altro, forse sono riuscito a trovare una soluzione per la generalizzazione del problema, nel caso in cui i prigionieri siano tutti sordi (o muti, come preferite), e quindi non ci sia informazione che passa "in avanti".
Chiamiamo il bianco 0 e il nero 1, in modo da poter vedere la sequenza dei cappelli come una successione infinita di questi due simboli. Definiamo una relazione di equivalenza sull'insieme di tutte le possibili successioni di 0 e 1, dicendo che due successioni sono equivalenti se sono uguali a meno di un prefisso finito. Per ogni classe di equivalenza scegliamo un rappresentante (e qui entra in gioco l'assioma di scelta).
Ogni prigioniero memorizza questi rappresentanti (evviva i prigionieri a memoria infinita). A questo punto ogni prigioniero, guardando quelli che lo seguono, riconosce la classe di equivalenza a cui appartiene (dato che la conosce tutta tranne un prefisso finito). Inoltre la sequenza effettiva del cappelli può differire dal rappresentante della classe di equivalenza solo per una quantità finita di elementi: se ogni prigioniero suppone che la sequenza dei cappelli sia la rappresentante, ci sarà solo un numero finito di morti.
Chiaramente ci sono un paio di cose che mi convincono poco di questa soluzione come ad esempio
i prigionieri che possono imparare un continuo di successioni numerabili in una notte, ma essendoci di mezzo l'assioma di scelta non mi pare così improbabile.
Ora l'unica cosa è vedere se si riesce a migliorare questa soluzione (ammesso che sia corretta) considerando anche il passaggio di informazioni, magari adottando qualche idea da #11 per riuscire a fare in modo che il numero di "martiri" sia non solo finito, ma anche limitato...
>> #2
Questo è vecchio da morire, ma sempre bellissimo.
