>> #29
[Insert fancy mathematics joke here]

Il tentativo mio e di un mio amico. Fair warning: è un po' tecnica, ma ho tentato di renderla rigorosa.


Mi servono un po' di nozioni preliminari prima di affrontare il problema vero e proprio.
--------------------------------------------------------
Dato che userò sempre i simboli 0 e 1 per indicare i colori bianco e nero, chiamo X l'insieme delle stringhe binarie infinite, ossia di tutte le possibili configurazioni di colori dei prigionieri.
Definisco la "distanza di Hamming" H(x,y) tra due stringhe x e y come il numero di bit-flip necessari per passare dall'una all'altra, se questo numero è finito.
Considero ora la famiglia di operatori F = {f_k} definiti da X a X, dove f_k flippa il k-esimo bit e lascia il resto immutato; allora {id,f_k} è un gruppo abeliano con l'operazione di composizione (id è la mappa che non fa niente).
Chiamo G la somma diretta di tutti questi gruppi; ossia, G con l'operazione di composizione è il gruppo degli operatori che flippano un numero finito di bit.
G agisce a sinistra su X, partizionandolo in orbite. Chiamo π la proiezione canonica da X allo spazio delle orbite X/G, e noto che per x, y in X, πx = πy sse H(x,y) è un numero finito. Per l'assioma della scelta, esiste un sottoinsieme di X/G, diciamo Y, che contiene esattamente un rappresentativo di ciascuna orbita (notare che Y è necessariamente non numerabile).
Chiamo r la biiezione da X/G in Y che manda un'orbita nel suo particolare rappresentativo, e chiamo p la mappa rπ seguita dall'inclusione di Y in X. In particolare, H(x,px) è ben definito per ogni x in X.
--------------------------------------------------------
Ora torniamo al problema di prigionieri. Prima di essere messi in fila per l'esecuzione, i prigionieri si accordano sulla scelta dell'insieme Y. Dopo essere stati messi in fila, il prigioniero #0 osserva la stringa di colori davanti a sé — chiamiamola A — e calcola H(A,pA), che per definizione di p è un numero finito. Dopodiché, il prigioniero dichiara il colore corrispondente a H(A,pA) modulo 2. Il prigioniero #0 si è sacrificato per fornire questa informazione a ogni giocatore.

Ora dimostrerò per induzione che ogni altro prigioniero avrà salva la vita; a questo fine, chiamo E(k) l'enunciato: "Nel momento in cui viene interrogato il prigioniero #k, per ogni r ≥ k il prigioniero #r conosce tutti gli elementi di A fino al (k-1)-esimo e dall'(r+1)-esimo in poi, nonché il valore di H(A,pA) mod 2.".

E(k-1) -> E(k) (passo induttivo): per ipotesi, il prigioniero #(k-1) conosce tutti gli elementi di A tranne il (k-1)-esimo. Allora, può formare le stringhe B e C ottenute da A mettendo come (k-1)-esimo elemento 0 e 1, rispettivamente, e una tra queste due sarà uguale ad A. Inoltre, per definizione di p, si ha che pB = pC = pA. Per determinare quale tra B e C sia la sequenza giusta, il prigioniero calcola H(B,pB) (= H(B,pA)) e H(C,pC) (= H(C,pA)), e per definizione di H e p questi due numeri sono finiti e differiscono di 1. Ma allora, estraendo il modulo 2 di questi numeri e confrontandolo con il valore noto di H(A,pA) mod 2, il prigioniero determina con certezza se sia B = A o C = A, e quindi quale sia il proprio colore.
Quando lo dichiara, ha salva la vita e al tempo stesso comunica a tutti i giocatori davanti a sé il valore del (k-1)-esimo elemento, che è l'unico che mancava loro per soddisfare l'enunciato E(k).

E(1) (base dell'induzione): quando viene interrogato il prigioniero #1, tutti i prigionieri conoscono tutti gli elementi di A successivi al proprio perché li vedono davanti a sé. Conoscono inoltre H(A,pA) mod 2 perché è stata loro comunicata dal prigioniero #0.

Come di può vedere dalla dimostrazione, questa strategia consente di salvare tutti i prigionieri tranne al più il #0.

Implementate l'output per il TEX, per favore.

>> #31
Sticazzi. Niente da dire, ben fatto.

> Facciamo un gioco.
> Io genero due numeri (reali), non vi è dato sapere come, e ve ne mostro uno, non vi è dato sapere in base a cosa.
> Il vostro obiettivo è ora indovinare se il numero coperto è maggiore o minore di quello che vedete. In tal caso vincete.
> Scopo di questo problema è trovare un metodo per vincere a questo gioco con una probabilità strettamente maggiore del 50%.
> Questo metodo esiste (io posso confermarlo).

Al solito, se avete delle idee, buttate tutto sotto spoiler per permettere anche agli altri di partecipare. Buon lavoro!

Immagino che questi numeri vengono mostrati su fogli o carte?

>> #35
Non è particolarmente importante, ma si può immaginare che i due numeri siano su due carte coperte sul tavolo, e una venga scoperta.

Quindi le carte sono tutte perfettamente uguali e non offrono indizi, giusto?
Quando mostri un numero può variare il tuo tono di voce o la tua espressione?

È possibile ripetere il gioco più volte (a fissata regola di scelta dei numeri) o esiste una strategia vincente a priori?

>> #37
Credo che Square abbia in mente una soluzione come si deve, non un trucchetto.

>> #37
Il tutto potrebbe benissimo essere effettuato da un computer, o da qualcuno che non conosce i numeri, non c'è nessun tipo di trucco.

>> #38
Si gioca un round solo, e la strategia deve garantire già qui una probabilità di vincere favorevole (strettamente maggiore del 50%), niente approcci statistici.

Tra l'altro questo enigma è un famoso paradosso, dato che sembra chiedere di ottenere dell'informazione dal nulla.

Ho bisogno di un chiarimento su "non vi è dato sapere come": c'è un tetto o i numeri possono essere grandi a piacere?

>> #40
No, possono essere grandi (o piccoli) a piacere, a priori sai solo che sono due numeri reali.

>> #34
C'era un video di numberphile su sta cosa uscito qualche mese fa!
Lascio il link cosi se lo vede solo chi vuole spoilerZ:
https://www.youtube.com/watch?v=ud_frfkt1t0

>> #42
L'ho guardato ma c'è una cosa che non ho capito: con che criterio scegli la distribuzione da cui pescare K se non sai a priori come sono stati scelti A e B? Se la risposta è "una distribuzione piatta su tutti i reali", il criterio, per quanto interessante, è del tutto inapplicabile; se invece la risposta è "una gaussiana centrata sulla probabile media di A e B", non è comunque applicabile perché non conosci né la media né la deviazione dei due numeri...

>> #43
La cosa divertente è proprio che non avendo informazione, il nuovo numero puoi generarlo come ti pare. Vuoi usare il tuo numero preferito? Il numero di atomi di cui è composto il tuo corpo? La costante di gravitazione universale? Vanno tutti bene, perché comunque ci sarà una probabilità non nulla che quel numero finisca nell'intervallo tra i due numeri che ho generato io.
Non ho guardato il video (mi fido di Numberphile), qui viene discusso il "da dove diavolo viene quell'informazione che ci permette di avere più del 50% di probabilità?".

>> #45
Capito, alla fine è un concetto simile al paradosso di Monty Hall: la probabilità extra deriva dal poter "aprire una delle porte" prima di dare la risposta definitiva, no?