Newsgroup: it.hobby.enigmi
Titolo: Scacchiera e monete.

Un problema che ho trovato in un altro gruppo, mi pare interessante.
Il set-up puo' essere il solito: guardiano(G), 2 prigionieri(P1 e P2),
risolvete il quiz e siete liberi, etc,etc. Il quiz e' questo:
In una stanza c'e' una scacchiera, G lancia una moneta e la piazza come
viene nella prima casella della scacchiera, ripete fino a che tutte le
caselle hanno una moneta che mostra T o C. Poi comunica a P1 una casella
target, P1 esamina la scacchiera e gira una (ed una sola) moneta a sua
scelta (se era T ora mostra C o viceversa) e la rimette esattamente come
era prima (la moneta e' indistinguibile dalle altre per P2). P1 esce da
una porta e poi da un'altra entra P2 (nel senso che non possono
comunicare in alcun modo). P2 osservando la scacchiera deve indovinare
la casella.  G ovviamente spiega il gioca a P1 e P2 e loro possono
mettersi d'accordo su di una strategia.
Quale e' la strategia migliore? Quale e' la probabilita' di successo
usando questa strategia?
 
Ciao,
      Gorgo


scusa ma non basta accordarsi per scegliere la moneta nell'angolo X ad 
esempio o una qualsiasi moneta in una determinata posizione? 


E' il guardiano che sceglie la casella non il prigioniero! 
Ciao,
      Gorgo



Bah!
Visto che non sono loro a scegliere la casella e che non possono comunicare 
se non attraverso la moneta toccata da P1, l'unica via per dare un segnale a 
P2 dovrebbe essere un modo preconcordato di posizionare la moneta 
all'interno della casella.
Ma sicuramente mi sfugge qualcosa... capir� dopo eh eh :-))
Ciao,
E. 

 
Come detto sopra "la rimette esattamente come era prima (la moneta e'
indistinguibile dalle altre per P2)".
 
Ciao,
      Gorgo


pu� tenerla in mano e scaldarla ad esempio? 

 
No, non c'e' trucco, la soluzione e' puramente matematica.  
Ciao,
      Gorgo

 usando questa strategia?
.
.
.
.
.
.
.
.
100%
Una volta stabilito un ordine di lettura (per esempio per righe e poi
per per colonne), la moneta da girare sarà quella seguente la prima
alternanza CT o TC (oppure l'ultima moneta se le prime 63 sono
monotematiche).
Per esempio la moneta X sarà
TTTCX..............
TCX................
CCCCCCTX...........
CTX................
CCCCCCCCCCCCCCCCCCX
TTTTTTTTTTTTTTTTTTX
--
Ciao, Silv:o)

 bello :)
...peccato che non avevo capito che c'era da indovinare la casella
scelta dal guardiano e non la moneta girata.
Ci penso.
--
Silv:o)

       Gorgo
Saluti, Accio.

"Gorgo" <go...@nowhere.invalid> ha scritto nel messaggio 
news:7n7frrF...@mid.individual.net...

Mi sembra un problema di block design.
Proviamo a partire dal basso, ma basso basso: due caselle.
P1 deve riempire una tabella in cui le righe sono le caselle e colonne le 
possibili disposizioni di monete che si pu� trovare di fronte. In ogni 
casella ci mettiamo la disposizione finale, dopo lo scambio di monete (in 
maiuscolo la moneta scambiata).
Questa tabella risolve il gioco:
\ tt|tc|ct|cc
 \--+--+--+--+
1|tC|Cc|cC|Tc|  in questa riga compaiono tc e cc
-+--+--+--+--+
2|Ct|tT|Tt|cT|  in questa riga compaiono ct e tt
-+--+--+--+--+
Quindi P1 � in grado scegliendo la riga giusta di comunicare a P2 la casella 
scelta da G.
Con 3 caselle il massimo che riesco a fare � riempire 20 caselle su 24 senza 
mai piazzare combinazioni uguali su righe differenti; per le ultime 4 non 
posso fare a meno di ingannare il povero P2.
Con 4 invece a mano ho trovato questo bello schema
\ 
tttt|tttc|ttct|ttcc|tctt|tctc|tcct|tccc|cttt|cttc|ctct|ctcc|cctt|cctc|ccct|cccc
 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+1|tttC|Cttc|tCct|ttTc|tcCt|tTtc|Ccct|tccT|cttC|Tttc|cCct|ctTc|ccCt|cTtc|Tcct|cccT| +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+2|ttCt|tCtc|Ctct|ttcT|tctC|Cctc|tTct|tcTc|ctCt|cCtc|Ttct|ctcT|cctC|Tctc|cTct|ccTc| +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+3|tCtt|ttCc|ttcC|Ctcc|Cctt|tctT|tcTt|tTcc|cCtt|ctCc|ctcC|Ttcc|Tctt|cctT|ccTt|cTcc| +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+4|Cttt|tttT|ttTt|tCcc|tTtt|tcCc|tccC|Cccc|Tttt|cttT|ctTt|cCcc|cTtt|ccCc|cccC|Tccc| +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+nella riga 1 compaiono tttc,cttc e le complementari tcct,ccctnella riga 2 compaiono ttct,tctc e le complementari cctc,ctctnella riga 3 compaiono tctt,ttcc e le complementari ctcc,ccttnella riga 4 compaiono cttt,tttt e le complementari tccc,ccccQuindi P1 � ancora in grado scegliendo la riga giusta di comunicare a P2 lacasella scelta da G.La simmetria di sopra mi lascia sperare in qualche generalizzazione per 64righe e 2^64 colonne.--Ciao, Silv:o)


non � G a disporre le monete nelle caselle? P1 deve solo girarne una e a
quanto ho capito G le dispone in modo assolutamente casuale, � cos�? 

Con 4 invece a mano ho trovato questo bello schema
Con questa lunghezza di riga tanto bello non � pi� :)
Lo riformatto.
\ tttt|tttc|ttct|ttcc|tctt|tctc|tcct|tccc|
 +----+----+----+----+----+----+----+----+
1|tttC|Cttc|tCct|ttTc|tcCt|tTtc|Ccct|tccT|
 |----+----+----+----+----+----+----+----+
2|ttCt|tCtc|Ctct|ttcT|tctC|Cctc|tTct|tcTc|
 |----+----+----+----+----+----+----+----+
3|tCtt|ttCc|ttcC|Ctcc|Cctt|tctT|tcTt|tTcc|
 |----+----+----+----+----+----+----+----+
4|Cttt|tttT|ttTt|tCcc|tTtt|tcCc|tccC|Cccc|
 +----+----+----+----+----+----+----+----+
 |cttt|cttc|ctct|ctcc|cctt|cctc|ccct|cccc|
-+----+----+----+----+----+----+----+----|
 |cttC|Tttc|cCct|ctTc|ccCt|cTtc|Tcct|cccT|
-+----+----+----+----+----+----+----+----|
 |ctCt|cCtc|Ttct|ctcT|cctC|Tctc|cTct|ccTc|
-+----+----+----+----+----+----+----+----|
 |cCtt|ctCc|ctcC|Ttcc|Tctt|cctT|ccTt|cTcc|
-+----+----+----+----+----+----+----+----|
 |Tttt|cttT|ctTt|cCcc|cTtt|ccCc|cccC|Tccc|
-+----+----+----+----+----+----+----+----+
-- 
Siv:o) 

 ha scritto nel 
messaggio news:4b0efcbe$0$10444$4faf...@reader2.news.tin.it...

Hai capito bene. Vediamo sempre il caso ipersemplificato.
1) G lancia due monete.
   Le possibili uscite sono tt|tc|ct|cc. Supponiamo esca "tc"
2) G sceglie una casella tra la 1 e la 2. Supponimao scelga la "2"
3) P1 guarda questa tabella
\ tt|tc|ct|cc
 \--+--+--+--+
1|tC|Cc|cC|Tc|
-+--+--+--+--+
2|Ct|tT|Tt|cT|
-+--+--+--+--+
La riga "2" colonna "tc" dice "tT", quindi P1 gira la seconda moneta che da 
c diventa t.
4) P2 vede "tt", controlla sulla tabella e vede che tutti i casi "tt" stanno 
sulla riga "2".
   Non sar� in grado di sapere la moneta che P1 ha girato, ma di sicuro 
azzecca la casella scelta: la "2"!
   In realt� a P2 - ma anche a P1 - non serve la tabella completa: basta la 
composizione delle righe.
In questo caso banale basta forzare la seconda moneta a "T" (o girare la 
prima se la seconda � gi� testa) per comunicare che G ha scelto la seconda 
casella. Al crescere delle dimensioni le strategie si fanno pi� complesse e 
qualche sforzo di memoria bisogner� farlo :)
-- 
Silv:o) 

 posso fare a meno di ingannare il povero P2.
(L'unico mio contributo a questo NG ï¿œ chiedere spiegazioni perchï¿œ non 
capisco :(  )
Scusa, sto cercando di capire lo schema ma davvero non riesco a trovare 
il bandolo. Prendendo un esempio pratico (di tre caselle)...P2 (che 
razza di nome) trova nella scacchiera tre monete C-C-T. Come fa a dire 
qual ï¿œ la moneta a cui ï¿œ stato cambiato il verso e qual ï¿œ la casella di 
riferimento, seguendo uno schema? (poi magari ï¿œ come il trucco del seme 
delle carte della telepatia che era una cavolata e io come al solito non 
ho capito una cippalippa)

 cippalippa)
Purtroppo con tre caselle non viene bene.
Con due ho gi� fatto un esempio nel post precedente (TC e casella 2).
Con 4 lo schema � il seguente:
P1 deve cercare di passare a T1 queste disposizioni a seconda della casella 
di riferimento:
1) TTTC, CTTC, TCCT, CCCT
2) TTCT, TCTC, CCTC, CTCT
3) TCTT, TTCC, CTCC, CCTT
4) CTTT, TTTT, TCCC, CCCC
Ho postato una tabella che dimostra che T1 pu� SEMPRE ricadere in una delle 
sequenze della riga giusta girando una sola moneta, quale che sia la 
disposizione di partenza.
Un esempio a caso: G lancia TCTT e sceglie la casella 4.
P2 gira la seconda casella e P2 vedendo 4 teste capisce.
Ancora a caso: CCTT casella 1.
P2 gira la terza e presenta CCCT a P2 che risolve.
E cos� via.
-- 
Ciao, Silv:o)

 Ho postato una tabella che dimostra che T1 pu� SEMPRE ..
.. che P1 pu� ..
-- 
Silv:o) 

 ha scritto nel messaggio 
news:4b0f0854$0$6826$5fc...@news.tiscali.it...

Ma sicuramente io continuo a capire fischi per fiaschi.
Mi sembra che l'esposto dica che P1 rovescia una moneta, per rimetterla 
subito dopo esattamente come l'ha trovata.
Dunque non sposta nulla: se era T, resta T e se era C resta C
Cos'� che non capisco? 

 Cos'ï¿œ che non capisco? 
All'inizio avevo capito anche io cosï¿œ :(
Penso che per "rimetterla com'era prima" si intenda semplicemente 
"rimetterla in modo da non far capire che ï¿œ stata manipolata in qualche 
modo" (spostandola, scaldandola, colorandola, sputandoci sopra ;) )

 E cosï¿œ via.
Ti ringrazio per la spiegazione! Ho seguito l'esempio che hai fatto 
prima e avendo la capacitï¿œ di astrazione di un macaco psicolabile ho 
dovuto fare la prova con due monete reali :) effettivamente quaglia 
tutto! (della serie, riuscite a elaborare dei ragionamenti che io fatico 
perfino a capire quando mi vengono spiegati di tutto punto :) )


:: ripete fino a che tutte le caselle hanno una moneta che mostra T o C
ma se c'� una sola moneta/casella come fa? non capisco :(

Devo confessare che non ho capito la soluzione di Silvio (i miei neuroni 
stanno forse appassendo), e allora ripropongo questa che da una 
probabilità di salvezza poco maggiore del 75%.
Numerate le caselle da 0 a 63, sia N la casella scelta dal guardiano.
Il prigioniero P1 somma i valori delle caselle contenenti testa, 
trascurando le croci.
Sia S la somma, ed M il valore di S(mod 64)
Dal confronto tra N ed M il prigioniero sceglie la moneta da girare, per 
far si che M diventi uguale ad N..
Faccio un esempio
N=50 la casella scelta dal guardiano
M=47 il valore di S(mod 64)
Girando la moneta il prigioniero deve aumentare S di tre unità, o 
diminuirlo di 61 unità.
Ciò e possibile se si verifica almeno una delle due condizioni:
_La casella 3 è croce
_La casella 61 è testa
Quindi con una probabilità 3/4.
Un piccolo vantaggio rispetto al 75% si ha se già in partenza risulta 
M=N. In quel caso non occorre spostare nessuna moneta, o, se si è 
obbligati a spostarne comunque una, si sposta la moneta della casella 0.
Con alcuni artifizi la probabilità può aumentare ulteriormente, ma non 
sono in grado di quantificarla.
Per esempio, P1 valuta le coppie di caselle simmetriche (1-63) /2-62) 
(3-61) ecc.
Le coppie TT, TC, o CT sono favorevoli, le coppie TC sono sfavorevoli.
I prigionieri possono concordare che se TC sono più frequenti di CT, il 
gioco si inverte, ossia si sommano le croci anziché le teste.
Di più non so.
Paolo 

 modo" (spostandola, scaldandola, colorandola, sputandoci sopra ;) )
Si esatto, avevo anche specificato "se era T ora e' C e viceversa" ma  avrei
dovuto dire "la rimette esattamente DOVE ERA", sorry.
Comunque la strada e' piu' o meno quella che avete intrapreso ma la
soluzione  e' piu' "algoritmica" , ovviamente non si puo' fare una
tabella delle 64! combinazioni di monete.
Ciao,
      Gorgo

 
Intendevo 2^64, ovviamente.....
  Ciao,
        Gorgo

 Paolo
Questo metodo � molto pi� efficace del previsto.
No so spiegarne il motivo, ma evidentemente esiste una correlazione tra 
S(mod 64) e presenza (o assenza) dei bit utili.
Da una simulazione su excel vedo che, se G sceglie celle diverse da quella 
con valore 0 (la prima in alto a sx),  � ***sempre*** presente almeno una 
delle due possibilit� di cambio per portare il modulo della somma al valore 
che identifica la cella di G.
Solo nel caso in cui, invece, G scelga la cella 0, in circa 1/4 dei casi non 
esiste nessuna delle due chances
Quindi 25*63+75*64 casi favorevoli su 64*100 casi possibili
Nel 99,6% dei casi � possibile comunicare a P2 la posizione della cella 
indicata da G
Io non sono in grado di calcolare la percentuale esatta ma ripeto (*brute 
force*) i casi sfavorevoli si attestano intorno a 250/1000, limitatamente ad 
1 caso su 64 (scelta della 0)
Ora tocca ai matematici!! :-)
Ciao,
E. 

 Ho postato una tabella che dimostra che T1 puï¿œ SEMPRE ricadere in una delle 
Se sei in grado di arrivare a 8, la tua soluzione puï¿œ essere combinata 
con quella di Paolo Licheri per arrivare al 100% dei successi.

 con quella di Paolo Licheri per arrivare al 100% dei successi.
No scusa ho sparato una stupidaggine devo pensarci ancora.

Un esempio:
Supponiamo che sia questa la scacchiera ottenuta alla fine dei lanci di 
monetine.
C  T  C  C  T  T  T  T
C  T  C  T  C  T  C  T
T  C  C  T  C  C  T  T
C  T  T  T  T  T  T  C
C  C  C  T  T  T  C  T
T  T  C  C  C  T  T  T
C  C  C  C  T  C  C  C
T  T  T  C  T  C  C  T
e che P1 e P2 abbiano concordato T = acceso e C = spento con questi valori
 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
In tal caso S (somma dei valori corrispondenti a "T") � pari a 1028
e (1028 mod 64) = 4
Cella da         Rovesciando         Rovesciando
comunicare         C -> T              T -> C
                 la moneta di        la moneta di
                   valore              valore
-------------------------------------------------
 0                    60                     3
 1                    61                     2
 2                    62                     1
 3                    63                     0
 4                     0                    63
 5                     1                    62
 6                     2                    61
 7                     3                    60
 8                     4                    59
 9                     5                    58
10                     6                    57
11                     7                    56
12                     8                    55
13                     9                    54
14                    10                    53
15                    11                    52
16                    12                    51
17                    13                    50
18                    14                    49
19                    15                    48
20                    16                    47
21                    17                    46
22                    18                    45
23                    19                    44
24                    20                    43
25                    21                    42
26                    22                    41
27                    23                    40
28                    24                    39
29                    25                    38
30                    26                    37
31                    27                    36
32                    28                    35
33                    29                    34
34                    30                    33
35                    31                    32
36                    32                    31
37                    33                    30
38                    34                    29
39                    35                    28
40                    36                    27
41                    37                    26
42                    38                    25
43                    39                    24
44                    40                    23
45                    41                    22
46                    42                    21
47                    43                    20
48                    44                    19
49                    45                    18
50                    46                    17
51                    47                    16
52                    48                    15
53                    49                    14
54                    50                    13
55                    51                    12
56                    52                    11
57                    53                    10
58                    54                     9
59                    55                     8
60                    56                     7
61                    57                     6
62                    58                     5
63                    59                     4
Per tutte le celle da 1 a 63 almeno una delle 2 possibilit� di cambio � 
possibile.
Non lo �, invece, nel caso in cui la cella da comunicare sia la prima (di 
valore 0).
In quel caso non si pu� cambiare da C a T la moneta di valore 60 (che � gi� 
T) n� cambiare da T a C la moneta di valore 3 (che � gi� C).
Questa configurazione (relativamente sfortunata) capita mediamente una volta 
su 4 ed inficia la validit� del metodo solo se G sceglie la cella 0 (prob. 
1/64)
Nell'altro 75% dei casi tutte le 64 celle possono essere comunicate senza 
problemi.
Ciao,
E. 

 
Aggiungo qualche altra cosa.
Esiste una soluzione che assicura il 100% di probabilita' di rispondere
correttamente e, piu' importante, questa soluzione puo' essere data
succintamente in due, tre righe! Cioe' niente lunghe tabelle o cose del
genere. 
Ciao,
      Gorgo

"Gorgo" ha scritto

Il tutto da subito mi puzzava di codici a correzione di errore, quindi mi 
sono andato a rivedere le vecchie dispense pi� un po' di google per togliere 
la polvere accumulata in qualche (parecchi, ormai) anno.
Per risolvere il quesito userei il codice di Hamming, che � un codice in 
grado di capire grazie a particolari bit di controllo (inseriti di solito 
nelle posizioni 1,2,4,8,16,32) se durante la trasmissione c'� stato UN 
SINGOLO errore.
Prendo la stringa di 64 bit che codifica la disposizione di teste e croci.
Supponiamo che le monete girate da G nelle posizioni di controllo siano 
"TCTTCTT" = 0100100, e che i bit di controllo previsti dal codice di Hamming 
analizzando le altre 57 monete siano invece 0011000. Dal confornto (XOR) tra 
i bit otterrei la posizione della moneta da flippare per ottenere una 
configurazione "legale", ovvero una configurazione in cui le 7 monete di 
controllo "confermano" la disposizione delle restanti 57.
Purtroppo girare questa moneta non sarebbe di nessun aiuto al mio complice, 
perch� non porterebbe nessuna informazione rigurdo la moneta scelta da G.
Invece devo flippare la moneta che � lo XOR tra quella indicata da G 
(supponiamo sia la 15 = 0001111) e lo XOR precedente!
Nel nostro caso otterrei
0100100 (A = monete in posizioni di controllo)
0011000 (B = bits di controllo di Hamming)
0001111 (C = codifica della casella scelta da G)
-------
0110011 (A XOR B XOR C = 51)
Quindi girer� la moneta 51. Il mio complice far� lo XOR tra i 7 bit di 
controllo ricevuti e quelli teorici, ottenendo come risultato proprio 000111 
= 15.
-- 
Ciao, Silv:o) 

 
Si, qualcosa del genere ma si puo' fare piu' semplice.
Ogni casella e' numerata da 0 a 63 (6bit). P2 per individuare la casella
deve fare l XOR bitwise delle caselle che mostrano Testa (o Croce da
decidere preventivamente). P1 per fare in modo che questo avvvenga fa la
stessa cosa e poi gira la moneta che ha settati i bit sbagliati.
Ciao,
      Gorgo

 stessa cosa e poi gira la moneta che ha settati i bit sbagliati.
OK. Ovviamente se P1 gira la moneta suggerita dalla checksum non serve
a molto (P2 si troverebbe una posizione a checksum nulla). Per
scegliere la moneta da girare serve un ulteriore XOR con la posizione
scelta da G. Dopo la rotazione, la nuova checksum indicherà a P2
proprio la posizione obiettivo.
--
Ciao, Silv;o)

 far si che M diventi uguale ad N..
Dove fallisce il tuo metodo? Nel fatto che per la checksum che proponi
(somma modulo 64) le trasformazione T->C e C->T non sono simmetriche.
T->C sulla casella X aumenta di X la checksum, C->T la diminuisce di X
(o l'aumenta del complementare). Per cui se ti serve di aumentare la
checksum di un valore X, devi sperare che la casella X sia C o che la
sua complementare sia testa.
L'operazione "simmetrica" per eccellenza nel mondo booleano e lo XOR.
Quindi sostituendo alla somma modulo 64 lo XOR le cose vanno a posto
da sole.
Ripropongo il metodo solutivo in una maniera forse più chiara:
1) giriamo la moneta nella casella X scelta da G
2) calcolaliamo la checksum facendo lo XOR di tutte le posizioni che
presentano TESTA
3) giriamo la moneta indicata dalla checksum: in questo momento la
checksum e' nulla
4) rimettiamo la moneta nella casella X com'era originariamente: ora
la checksum è proprio X
Ora il nostro compagno avrà davanti una scacchiera con una sola moneta
girata rispetto a quella iniziale, e la checksum gli indicherà proprio
la casella X.
Con il tuo metodo dovremmo sostituire "giriamo la moneta X" con
"aumentiamo di X la checksum" e come hai detto tu la cosa è possibile
solo 3/4 delle volte, per cui il passo 3 non sempre è possibile (l'1 e
il 4 sono solo "matematici" e alla fine si annullano, quindi
chissenefrega se materialmente si possono fare oppure no: e' come
l'unita' immaginaria per risolvere le equzioni di secondo grado).
--
Ciao, Silv:o)

 SINGOLO errore.
Confesso che fin da subito sono andato a vedere la soluzione su Google,
tanto non ci sarei mai arrivato. Segnalo dunque questa pagina:
http://ocfnash.wordpress.com/2009/10/31/yet-another-prisoner-puzzle/
in cui l'autore suggerisce un'implementazione particolarmente semplice
dell'algoritmo, tanto che con un po' di allenamento si potrebbe fare a
mente come gioco di telepatia. E' giusto un suggerimento per le vicine
feste...
Maurizio
-- 
Per rispondermi via e-mail togli l'ovvio.

 feste...
Si puo' fare anche cos�:
Ora che acciamo capito che per ogni disposizione possiamo girare una moneta 
per rendere nullo lo XOR, cerchiamo un modo rapido per trovarla.
La codifica binaria di una casella ci dice nei suoi sei bit se la casella �:
- nelle prime 32 caselle (prime 4 righe) (bit 1 = 0)
- nelle righe 1,2,5,6 (bit 2)
- nelle righe dispari (bit 3)
- nelle prime 4 colonne (bit 4)
- nelle colonne 1,2,5,6 (bit 5)
- nelle colonne dispari (bit 6)
Facendo lo XOR bit a bit delle caselle che contengono Testa, i sei bit 
rappresenteranno la parit� delle Teste nei corrispondenti gruppi. Con tre 
conteggi di parit� individuiamo la riga, con altri 3 la colonna.
Per esempio:
8|00100100
7|01011000
6|10001010
5|11010010
4|11000101
3|00101001
2|10101010
1|11000001
  ABCDEFGH
- nelle prime 4 righe ci sono 13 teste.
- nelle righe 1256 ci sono 14 teste.
- nelle righe dispari ci sono 12 teste.
Per riportare la parit� nelle righe dovremmo girare una moneta che E' nelle 
prime 4, non � nel gruppo 1256 (quindi e' la 3 o la 4), non � dispari, 
quindi una moneta della riga 4. Allo stesso modo troviamo la colonna: non e' 
nelle prime 4, e' nel gruppo ABEF, e' dispari, quindi � la colonna E. La 
moneta da girare e' la E4.
I bit dei sei gruppi risultano 100011 che in binario da 35. La casella H8 � 
la 0=000000, la A1 � la 63=111111, la 35=100011 contando dall'alto a destra 
� proprio la E4.
-- 
Ciao, Silv:o)


a me sembra sempre impossibile, se ho capito le monete sono disposte a caso, 
G indica a P1 quale moneta deve far 'indovinare' a P2 e quindi P1 gira una 
sola moneta della scacchiera a sua scelta; anche in considerazione di quanto 
nel link sopra, come � possibile che P1 possa in questo modo comunicare a P2 
quale moneta � stata scelta da G?
Esempio se la scacchiera vista da P2 � come quella sotto, quale moneta 
sarebbe stata indicata?
XXOXXOXO
OXOXOOXO
XOOXOOOX
OXOOOXOO
XOOOXOXO
XXXOXOXO
OOXOOXXO
XXOXOOXO 

 XXOXOOXO 
Che cosa indicano per te X e O? Supporr� che X sia testa e O croce.
Seguendo lo schema proposto in quella pagina, faccio cos�:
1) conto quante teste ci sono nelle colonne 5-6-7-8; sono 12 (pari)
quindi la casella si trova in una delle altre colonne (1-2-3-4);
2) conto quante teste ci sono nelle colonne 3-4-7-8; sono 13 (dispari)
quindi la casella si trova in una di queste colonne (3-4-7-8);
3) conto quante teste ci sono nelle colonne 2-4-6-8; sono 12 (pari)
quindi la casella si trova in una delle altre colonne (1-3-5-7);
deduco quindi che la casella si trova nella colonna 3.
Poi faccio la stessa cosa con le righe:
1) conto quante teste ci sono nelle righe 5-6-7-8; sono 15 (dispari)
quindi la casella si trova in una di queste colonne (5-6-7-8);
2) conto quante teste ci sono nelle righe 3-4-7-8; sono 12 (pari) quindi
la casella si trova in una delle altre colonne (1-2-5-6);
3) conto quante teste ci sono nelle colonne 2-4-6-8; sono 14 (pari)
quindi la casella si trova in una delle altre colonne (1-3-5-7);
trovo quindi che la casella si trova nella riga 5.
Fine.
Spero che ora sia chiaro.


 XXOXOOXO
P2 avrà di fronte a se una scacchiera che gli indicherà magicamente la
casella obiettivo C2, ed effetivamente abbiamo girato una sola moneta,
la D4 passata da O a x.
Ti ho convinto?
--
Silv:o)

 problemi a capire quale moneta girare.
E poi facevo vedere come P1 avrebbe potuto segnalare a P2 una casella
obiettivo scelta da G.
Ovviamente non avevo capito il punto di vista :(
Poco male: ho comunque fatto vedere come "produrre" la scacchiera.
Maurizio ha giustamente interpretato il post è ha fatto vedere come
"consumare" lo schema costruito.
Non manca più nulla per giocare.
--
Ciao, Silv:o)


grazie provo a rileggerlo un altra decina di volte ^___^ proprio
non mi entra sta cosa, anche perch� se giro una moneta P2 dovr�
fare la checksum considerando il nuovo valore della moneta che io
ho girato, come fa? 


non ci arrivo :( come dicevo a Maurizio, se P1 gira una moneta, come fa P2 a
capire per prima cosa quale ha girato e quindi determinare quale gli sta 
indicando? 

 non capisco � o non � nella riga 4?
E' un refuso, scusa, era ovviamente la 6.
Ma la tua difficolta' non puo' essere tecnica, mi pare sia concettuale.
Quello che cerchiamo di farti capire � che ogni configurazione puo' essere 
codificata con una stringa di sei bit, che � ottenuto facendo lo XOR del 
numero delle teste. Ora, per chi ha dimestichezza con i bit e le operazioni 
binarie, la cosa risulta � molto semplice. Al limite laboriosa, ma semplice.
Il metodo dei tre controlli di parit� per le righe e tre per le colonne non 
e' altro che un metodo grafico per calcolarsi lo XOR, niente di piu'.
Quello che deve essere chiaro e' questo:
"ogni disposizione puo' essere codificata con una stringa di sei bit, ovvero 
con un numero da 0 a 63, ovvero con una casella".
- Qualsiasi disposizione di monete HA LA SUA CASELLA CARATTERISTICA.
In quella del tuo esempio la casella magica era la C5 (terza colonna quinta 
riga).
Se avessimo usto la matematica binaria avremmo trovato che lo XOR delle 
teste dava 010100 (che dividendo in due terzetti torna a dare colonna 010 
riga 100, e a ben vedere 010-100 codifica anche la sequenza delle 6 parit� 
calcolate nel metodo grafico, PDP-DPP).
Altre due cose devono esserti chiare, altrimenti non ne esci. Sono due casi 
particolari della regola che dice che se giriamo una moneta X la nuova 
posizione caratteristica sar� lo XOR della vecchia posizione con X.
- Se in una qualsiasi disposizione giriamo proprio la moneta che sta nella 
casella caratteristica, otteniamo una posizione la cui casella 
caratteristica � la casella 0 (A1 con la convenzione utilizza). In pratica 
facciamo lo XOR di due numeri uguali e si annullano tutti e sei i bit.
- Se in una disposizione che ha casella caratteristica 0 ruotiamo la moneta 
della casella X, la posizione raggiunta avr� come casella caratteristica 
proprio X.
Se e' chiaro questo, allora e' chiara anche la strategia.
P1 DEVE PRODURRE UNA DISPOSIZIONE LA CUI CASELLA CARATTERISTICA SIA QUELLA 
SCELTA DA G.
P2 CALCOLA LA CASELLA CARATTERISTICA E TROVA QUELLA SCELTA DA G.
Ho mostrato un metodo facilissimo per ottenenere lo scopo prefissato da P1.
1) giro la moneta nella casella G
2) calcolo la casella caratteristica della scacchiera con la G girata
3) giro la moneta nella casella cos� calcolata.
Ora deve esserti chiarissimo qual e' la casella caratteristica in questo 
momento!
4) rimetto a posto la moneta G.
Anche adesso ti deve essere chiaro qual e' la casella caratteristica!
Ti faccio un esempio 4X4 che � piu' semplice (1=Testa):
0101
1011
1001
1100
Casella da comunicare: B1
passo 1) P1 gira la B1 (mentalmente se non vuole irritare G, fisicamente se 
G non lo vede)
0101
1011
1001
1000
passo 2) calcolo della casella caratteristica.
..01  .1.1
..11  .0.1
..01  .1.1
..00  .1.0
Pari  Pari
Siccome � gi� tutto pari, la colonna caratteristica NON E' nelle ultime 2 e 
NON E' pari, quindi e' la prima.
0101   0101
1011   ....
....   1001
....   ....
Disp   Pari.
Per rendere pari la prima somma dobbiamo scegliere una delle ultime 2 righe 
ma NON una riga pari altrimenti scombineremmo la seconda somma che e' gi� 
pari. La riga quieni � la terza e dunque la casella cartteristica � la A3.
Ci potevamo anche arrivare analizzando la sequenza PPDP ottenuta (0010 = 
colonna 00 riga 10 o direttamente casella 0010=2 che � la terza casella a 
partire dalla casella 0 che � A1).
Quindi P1 gira la moneta nella casella A3 (la indico con la o piccola)
0101
o011
1001
1000
Son sicuro che adesso la caratteristica e' nulla, ma controllo.
..01  .1.1
..11  .0.1
..01  .1.1
..10  .1.0
Pari  Pari.
0101   0101
0011   ....
....   1001
....   ....
Pari   Pari.
E' tutto pari, quindi prima riga e prima colonna. E' normale che sia tutto 
pari, ho scelta A3 apposta!
Ora rimetto a posto la moneta B1
0101
o011
1001
1100
Devo calcolare la casella caratteristica dopo quest'ultima rotazione o ti 
fidi che sia la B1?
-- 
Ciao, Silv:o)

 indicando?
Attenzione. Nessuno ha detto che P2 puo' capire quale moneta ha girato P1!
Deve solo indovinare quella che gli sta indicando, ovvero quella scelta da 
G.
Il punto e' proprio che P1 non sceglie la casella da girare per comunicare 
"direttamente" qualcosa a P2, ma solo per forzare la checksum.
Con il trucco della moneta girata e rimessa a posto, e' chiaro che P1 
sceglie semplicemante la casella che gli annulla la checksum prima di 
rimettere a posto la moneta-obiettivo.
-- 
Silv:o) 


mi fido ma :( sembra pi� difficile di quello delle carte, magari
mi � sfuggito un qualche particolare e mi sto incasinando da solo 


incredibile, forse sto cominciando a capire ^____^ grazie, mi resta il 
dubbio
che se gira una moneta e P2 non sa quale ha girato per comunicargli quella
scelta da G, allora non cambia tutta la scacchiera e quindi la conta dei 1?
Se ho capito P1 gira una moneta in modo da cambiare la somma delle monete
di un certo tipo, diciamo testa o 1 ok. Ma se gira una moneta allora la 
somma
� gi� stata cambiata appunto dalla moneta girata, no? 

 generalmente? Posso leggere qualche nozione sul web?
Il nome "casella caratteristica" me lo sono inventato io. La definizione 
l'abbiamo data molte volte:
E' lo XOR di tutte le caselle che contengono TESTA.
Per esempio, se ci fossero tutte croci e solo 3 teste nelle caselle 
(A3-A4-H7) come si calcolerebbe la caratteristica?
- Numeriamo le caselle da 0 a 63
- Codifichiamo ogni casella con la sua rappresentazione binaria:
00 = 000000 = A1 = (0,0) (colonna-riga)
01 = 000001 = A2 = (0,1)
02 = 000010 = A3 = (0,2)
03 = 000011 = A4 = (0,3)
..
08 = 000111 = B1 = (0,7)
09 = 001000 = B2 = (1,0)
10 = 001001 = B3 = (1,1)
..
31 = 011111 = D8 = (4,7)
32 = 100000 = E1 = (5,0)
..
61 = 111101 = H6 = (7,5)
62 = 111110 = H7 = (7,6)
63 = 111111 = H8 = (7,7)
- Facciamo lo XOR delle codifiche delle tre caselle Testa
000011
001001
111101
------
110111
Come avrai capito lo XOR da 1 se ci sono un numero dispari di 1, 0 
altrimenti.
quindi XOR(000011,001001,111101)=110111 che � la codifica della casella 6,7 
(la F8 della scacchiera).
Un metodo semplice per calcolare lo XOR senza dover passare per le codifiche 
delle singole caselle � mostrato nel link postato da Maurizio.
Se guardi lo stralcio di codifica che ho postato, noterari che solo le 
seconde 32 caselle, quelle delle colonne 5-6-7-8 hanno il primo bit a 1.
Il secondo bit a 1 ce l'hanno le caselle dalle colonne 2-3-6-7, il terzo bit 
a 1 ce l'hanno una colonna si e una no, ovvero le colonne 1-3-5-7.
Stessa cosa per le righe con gli altri 3 bit, l'ultimo dei quali come vedi � 
1 per le righe dispari. Da queste considerazione la regola con sei conteggi 
di parit� (tre per la colonna e tre per la riga) derivi i sei bit dello XOR.
Ora che abbiamo capito come si calcola la caratteristica, dovrebbe essere 
chiaro come fare a cambiarla:
In una disposizione a caratteristica X, girare la moneta Y ha l'effetto di 
cambiare la caratteristica da X a (Z = XOR Y).
Con questo abbiamo detto tutto.
- Ogni posizione ha il suo XOR
- Possiamo ottenere qualsiasi XOR cambiando la moneta opportuna.
Per esempio, nella posizione con 3 teste appena analizzata (che abbiamo 
visto avere caratteristica F8), quale moneta dobbiamo girare per ottenere 
come caratteristica C2?
Sfruttiamo la propriet� dello XOR:
A XOR (A XOR B) = (A XOR A) XOR B = 0 XOR B = B
Questo dimostra che per passare da una posizione a caratteristica A ad una 
posizione a caratteristica B la moneta da girare � la (A XOR B).
Nel nostro caso sarebbe la moneta (F8 XOR C2) = 110111 XOR 010010 = 100101 = 
E6
Basta dunque girare la moneta E6 da croce a testa per ottenere come 
caratteristica proprio C2.
Se sei scettico fai la prova:
000011
001001
111101
100101
------
010010 = C2
Concludendo, dati:
A = caratteristica della disposizione casuale generata da G.
B = casella scelta da G
La strategia � semplice:
- P1 deve gira la moneta nella casella (A XOR B)
- P2 calcola la carateristica della posizione che sar� proprio B.
Spero ora di averti chiarito tutti i dubbi.
Se la casella scelta � uguale alla caratteristica iniziale A, allora la 
casella da girare sar� (A XOR A) = 0, ovvero la A1 che ha la caratteriestica 
di lasciare inalterato lo XOR. In quella casella particolare, che ci sia 
testa o croce non cambia nulla.
Se hai capito fin qui puoi anche vedere che il trucco che suggerivo, ovvero 
calcolare la caratteristica della posizione considerando la moneta B 
invertita rispetto alla realt�, fa risparmiare un'operazione di XOR.
Per quanto riguarda gli ambiti di utilizzo di questi strumenti, il 
principale � senza dubbio la teoria dei codici 
(
http://it.wikipedia.org/wiki/Teoria_dei_codici
).
Nel nostro gioco P1 introduce un opportuno "errore" di un bit nella 
trasmissione dell'informazione (la posizione iniziale) per codificare il bit 
scelto da G.
-- 
Ciao, Silv:o) 

 somma � gi� stata cambiata appunto dalla moneta girata, no?
Non ho ben capito la domanda, mi sembra la stessa di prima. Spero che la 
risposta sopra copra anche questa :)
-- 
Silv:o)

 ..
..
07 = 000111 = A8 = (0,7)
08 = 001000 = B1 = (1,0)
09 = 001001 = B2 = (1,1)
..
Il resto mi pare corretto.
-- 
Ciao, Silv:o) 

 non mi entra sta cosa
Provo a sintetizzare: il primo prigioniero calcola una casella usando
questo metodo MA DOPO AVER RIGIRATO LA CASELLA SCELTA DAL CARCERIERE
(anche mentalmente, senza farlo per davvero). A questo punto il primo
prigioniero RIGIRA LA MONETA CHE STA NELLA CASELLA CALCOLATA ed esce. 
Il secondo prigioniero rif� il calcolo CON LE CASELLE CHE VEDE e come
per magia trover� proprio come risultato la casella scelta dal
carceriere. Provare per credere!
Il perch� la cosa funzioni te lo ha spiegato Silvio. Con una scacchiera
8x8 fare i calcoli a mente in fretta non � facile. Il gioco riesce molto
meglio con una scacchiera 4x4: ho fatto una prova con mio figlio (13
anni) e non ha avuto difficolt� a farlo. Durante le feste penso che
proporremo il giochino per divertire un po' gli amici...



non ho speranze, sono spacciato :( magari
provare con insiemi pi� piccoli di 8x8 potrebbe
essere una buna idea, grazie ^___^ 

 Spero ora di averti chiarito tutti i dubbi.
quindi in una scacchiera 3x3 diciamo
0X0
00X
0XX
se G segnala quella nel centro dovrei cambiare la posizione
nel seguente modo per indicarla a P2?
0X0
000
0XX


mi sembra di capire che il sistema � speculare, in questo
senso, fin qui (se corretto) ci arrivo; nella realt� sarebbe
poi possibile di fare a mente tutti quei calcoli? 

 0XX
Per questo tipo di giochi � necessaria una scacchiera di ordine 2^N.
Questo per garantire che il risultato dello XOR di un qualsiasi gruppo di 
caselle rappresenti sempre una casella della scacchiera.
Con 9 caselle saresti costretto a codificare le caselle con 4 bit (3 bit 
bastano fino a 8 caselle, 4 fino a 16) ma le sequenze da 9 a 15 non 
rappresenterebbero caselle valide:
0 = 0000 (A1)
1 = 0001 (A2)
2 = 0010 (A3)
3 = 0011 (B1)
4 = 0100 (B2)
5 = 0101 (B3)
6 = 0110 (C1)
7 = 0111 (C2)
8 = 1000 (C3)
9 = 1001 (???)
..
15= 1111 (???)
Veniamo al tu tentativo di soluzione.
Sembrerebbe che tu abbia fatto lo XOR della 4 caselle che hanno testa
0011 (B1)
0101 (B3)
0110 (C1)
0111 (C2)
---------
0111
Ed avendo trovato C2 come checsum della scacchiera (suppongo tu abbia fatto 
cos�) hai girato la casella C2.
Ma ti avevamo detto che lo XOR lo dovevi fare DOPO AVER GIRATO LA MONETA 
NELLA CASELLA OBIETTIVO B2, oppure - ma � lo stesso - dovevi fare un 
ulteriore XOR tra il risultato delle caselle Testa e la casella obiettivo:
0011 (B1)   /|
0101 (B3)  / |--. caselle
0110 (C1)  \ |--' testa
0111 (C2)   \|
0100 (B2)  <|=== casella obiettivo
---------
0011
Quindi la casella da girare NON E' la C2 (che � la checksum della 
scacchiera) ma la B1 (che � lo XOR tra la checksum della scacchiera e la 
casella obiettivo)!
Resta per� il fatto che il risultato dello XOR poteva venire maggiore di 8, 
nel qual caso non avresti potuto girare un bel niente � avresti passato il 
resto della vita in prigione. Questo per tornare alla considerazione che il 
gioco funziona solo con le potenze di 2.
Ho passato un bel po' di tempo a rispondere ai tuoi post; ti hanno suggerito 
un link molto ben fatto, ti ho abbiamo fatto vedere come codificare le 
caselle, come funziona lo XOR, come farlo graficamente contando le teste che 
stanno nella met� pari, nei quarti pari, negli ottavi pari sia per righe che 
per colonne.
Al di la del fatto che lo faccio per passione, il minimo che mi potrei 
aspettare � che tu facessi delle domande puntuali su cosa non ti � chiaro.
L'impressione che dai � di non metterci la stessa passione ed attenzione, 
spero di sbagliare.
Secondo me se rileggi con un minimo di attenzione in pi� tutto il materiale 
ne vieni a capo.
-- 
Silv:o) 


:-( sabato mi rileggo il 3d e ti faccio sapere 

Maurizio Frigeni ha scritto:

Ho iniziato a leggere la soluzione soltanto ora, devo ancora 
impadronirmene pienamente, ma che succede se puta caso la casella 
indicata e' proprio quella caratteristica della posizione data ?
Cioe' se la scacchiera cosi come e' gia indica la casella da indovinare ?
frengo

 Cioe' se la scacchiera cosi come e' gia indica la casella da indovinare ?
Giri la moneta nella casella 0 e la scacchiera continuer� ad indicare la 
stessa casella.
Quella casella ha tutti i bit a 0 e quindi non cambia lo XOR.
-- 
Silv:o)