La chiave dentro la scacchiera.

[3m0o]

Il direttore di un carcere comunica a due prigionieri che faranno il seguente gioco, i quali avranno una notte di tempo per accordarsi su una strategia e dopo di che non potranno più comunicare.
Il direttore posizionerà una chiave dentro una casella a caso di una scacchiera 8x8 situata in una stanza isolata. La chiave ovviamente non si vede. Dopodiché prenderà 64 monete identiche e una ad una le lancerà, con probabilità 1/2 esce testa e con probabilità 1/2 esce croce, una volta che lo stato della moneta è determinata la posizionerà sulla prima casella senza moneta. Ripete questa cosa fino a quando su ogni casella c'è una moneta. Ricapitolando la situazione è la seguente: una scacchiera 8x8, una chiave dentro una qualunque casella scelta a caso, e su ogni casella una moneta che indicherà o testa o croce a caso con probabilità 1/2, tutte le variabili aleatorie sono ovviamente indipendenti.
Finito il tempo a disposizione per accordarsi su una strategia, i due prigionieri non potranno più comunicare e a questo punto il prigioniero 1 entrerà nella stanza in cui c'è la scacchiera osservandola per la prima volta, il direttore gli comunicherà la posizione della chiave e il prigioniero 1 dovrà cambiare lo stato di una moneta a sua scelta (una testa renderla croce, o una croce renderla testa). Poi il prigioniero 1 esce ed entra il prigioniero 2, i due non possono comunicare in nessun modo. Il prigioniero 2 osservando per la prima volta la scacchiera, dovrà indicare una delle 64 caselle. Se il prigioniero 2 indicherà la casella con la chiave i due prigionieri sono liberi di andare, altrimenti vengono giustiziati.

Come fanno i prigionieri a liberarsi?

[Quinzio]

Testo nascosto, fai click qui per vederlo

Direi direi ... direi che si puo' fare in questo modo:
ogni casella ha associata la sua posizione scritta in binario, quindi da $000000$ a $111111$.
Prendo i numeri binari delle caselle dove ci sono sopra le croci.
Faccio l'XOR logico (bit a bit) dei numeri presi.
Faccio l'XOR del risultato con il numero della casella della chiave.
Col nuovo risultato giro la moneta nella corrispondente posizione (non importa se e' testa o croce).
Fin qui e' quello che fa il prigioniero 1.
Il prigioniero 2 fa l'XOR di tutti i numeri delle caselle con le croci e quella e' la posizione della chiave.

Piu' formalmente il prigioniero 1 fa questo calcolo:
$$r = k \otimes \left( \bigotimes_{i=0}^{63} c_i\ i \right)$$
dove $k$ e' la posizione della chiave,
$c_i = 1$ se nella casella $i$ c'e' una croce, altrimenti $c_i = 0$
$\otimes$ e' l'XOR

Facendo l'XOR sia a destra che a sinistra dell'uguale prima con $r$ e poi con $k$,
tenendo conto che $x \otimes x = 0$, si ottiene
$$k = r \otimes \left( \bigotimes_{i=0}^{63} c_i\ i \right)$$
e questa e' la situazione che trova il prigioniero 2.

PS. Ovviamente al posto delle croci vanno bene anche le teste. Non ha importanza che le caselle siano numerate sequenzialmente. I due prigionieri potrebbero anche mettersi d'accordo per una numerazione arbitraria della scacchiera e funzionerebbe ugualmente, basta che ogni casella abbia il suo numero univoco.
Questo mette al riparo dal problema della rotazione della scacchiera. Infatti i due prigionieri non devono guardare la scacchiera con la stessa orientazione, va bene qualsiasi orientazione, siccome posso scambiare liberamente i numeri.
L'importante e' che i due prigionieri si accordino sulla stessa numerazione ponendosi davanti alla scacchiera.

Anzi, non e' neanche importante che i 2 prigionieri si mettano d'accordo se usare le teste o le croci.
Siccome
$$ \bigotimes_{i=0}^{63} i = 0$$
$$ \bigotimes_{i=0}^{63} c_i\ i + \bigotimes_{i=0}^{63} \bar c_i\ i = 0$$
$$ \bigotimes_{i=0}^{63} c_i\ i = \bigotimes_{i=0}^{63} \bar c_i\ i $$
non e' necessario accordarsi se usare testa o croce.
$\bar x$ e' la negazione logica di $x$.

[3m0o]

Mi sembra funzionare

Nuova domanda: Stesso problema, ora la scacchiera (non necessariamente quadrata) possiede \(n\) caselle. Per quali \(n\) i prigionieri hanno una strategia sicuramente vincente?

[Quinzio]

Nuova domanda: Stesso problema, ora la scacchiera (non necessariamente quadrata) possiede \(n\) caselle. Per quali \(n\) i prigionieri hanno una strategia sicuramente vincente?

Testo nascosto, fai click qui per vederlo

Si, in effetti la disposizione delle celle non ha importanza, potrebbe essere anche un fila singola di celle.
Comunque il numero di celle deve essere un $2^n$, altrimenti la moneta da girare potrebbe essere su una cella che non esiste.

[3m0o]

Testo nascosto, fai click qui per vederlo

Allora sì, ma la ragione che hai detto non è quella, perché il tuo ragionamento dimostra soltanto che la tua strategia funziona per un numero \(2^n\) di celle, ma chi ti dice che non esiste un'altra strategia che risolve il problema per un altro numero di celle?

[Quinzio]

Testo nascosto, fai click qui per vederlo

Non ho la dimostrazione, ma penso che non ci siano altri modi. O meglio, altri modi sono delle rivisitazioni dell'XOR.
Anche usare l'aritmetica modulo $n$ porta subito a un fallimento.
Non saprei.

[3m0o]

Indizio:

Testo nascosto, fai click qui per vederlo

Beh sicuramente, indipendentemente dal codice utilizzato dai due prigionieri, il secondo quando entra ha solo le informazioni delle teste e delle croci, degli \(0\) e degli \(1\), che vede sulla scacchiera, quindi questa deve indicare una casella della scacchiera. Quindi se esiste una strategia vincente, il primo prigioniero, da un qualunque stato iniziale (qualunque casella) cambiando un solo bit, deve poter raggiungere qualunque altro stato (casella)... ma questo è possibile solo se