Prigionieri e monete

[Vincent46]

Penso...

Testo nascosto, fai click qui per vederlo

Siccome per n >2 vale $2^(2^n-n)>2^n$, i $2^(2^n-n)$ blocchi contengono ciascuno $2^n$ numeri binari, ognuno dei quali codifica uno ed un solo numero (posizione della moneta) tra 1 e $2^n$. Ora, siccome il numero dei blocchi è maggiore del numero di possibili posizioni delle monete che possono essere scelte posso associare ad un binario $b_0$ che codifica un numero tra $1$ e $2^n$ di un blocco $m$ un binario $b_1$ di un'altro blocco $n$ ottenuto dal primo cambiando un 1 o 0 che codifica un altro numero $1$ tra $2^n$, poi un binario $b_2$, $b_3$ e così via fino a $b_{2^n}$ ... non so se mi sono spiegato bene...

Testo nascosto, fai click qui per vederlo

Premesso che non penso di aver capito bene l'idea è di partizionare l'insieme dei numeri binari ammissibili in classi di equivalenza che contengono un binario per ogni blocco, e tali che gli elementi di suddetta classe differiscano fra loro di uno e un solo bit?

nino_: sì, ma così non vale comunque non mi pare di aver visto la soluzione in quel topic, o sbaglio?

Hint (hintone?):

Testo nascosto, fai click qui per vederlo

Numerare le monete sul tavolo con i numeri binari. Utilizzare una particolare operazione che prenda i numeri associati alle monete che mostrano testa e mi restituisca un altro numero binario.

[dan95]

Ti faccio un esempio con 4 monete

Testo nascosto, fai click qui per vederlo

Configurazioni (testa=0 croce=1)	n° moneta scelta
0000	1
0001	2
0010	3
0011	4
0100	1
0101	2
0110	3
0111	4
1000	4
1001	3
1010	2
1011	1
1100	4
1101	3
1110	2
1111	1

Per esempio supponiamo che le monete all'inizio siano disposte come la configurazione 0000 (tutte teste) e la guardia indichi la moneta n° 4, al prigioniero basterà voltare la prima moneta facendo diventare la configurazione 1000 che nella tabella corrisponde alla 4° posizione

[nino_]

nino_: sì, ma così non vale comunque non mi pare di aver visto la soluzione in quel topic, o sbaglio?

Sì, che c'è

http://www.trekportal.it/coelestis/show ... stcount=26

[Vincent46]

Ti faccio un esempio con 4 monete

Testo nascosto, fai click qui per vederlo

Configurazioni (testa=0 croce=1)	n° moneta scelta
0000	1
0001	2
0010	3
0011	4
0100	1
0101	2
0110	3
0111	4
1000	4
1001	3
1010	2
1011	1
1100	4
1101	3
1110	2
1111	1

Per esempio supponiamo che le monete all'inizio siano disposte come la configurazione 0000 (tutte teste) e la guardia indichi la moneta n° 4, al prigioniero basterà voltare la prima moneta facendo diventare la configurazione 1000 che nella tabella corrisponde alla 4° posizione

Testo nascosto, fai click qui per vederlo

ok, così funziona, ma hai la certezza che anche nel caso generale le configurazioni siano tutte collegate "bene"?

nino_: mi sembra inutilmente complicato; la soluzione che ho io ci assomiglia ma si spiega in tre righe... inoltre manca l'altra implicazione!

[Vincent46]

Hint per il viceversa:

Testo nascosto, fai click qui per vederlo

equivalentemente, bisogna dimostrare che, se c'è soluzione, allora il numero di monete $k$ divide il numero totale di configurazioni $n = 2^k$. Se così non fosse, il numero medio di configurazioni associate a ogni moneta sarebbe un numero non intero, e...

[Vincent46]

Soluzione:

Testo nascosto, fai click qui per vederlo

Se ci sono $2^k$ monete, a ogni moneta si associa un numero binario da $0$ in su. Il primo prigioniero entra e fa la somma bitwise modulo due (anche detta xor) dei numeri associati alle sole monete che mostrano testa. A prescindere dalla configurazione, è possibile passare da un qualsiasi binario ammissibile a un altro voltando una sola moneta.

Per il viceversa, è equivalente dimostrare che il numero di configurazioni $2^k$ dev'essere multiplo del numero di monete $k$. Se così non fosse, a ogni moneta sarebbe associata una media di $x$ configurazioni, con $x$ non intero. Quindi esiste una moneta che ha associate $y$ configurazioni, con $y$ intero minore di $x$. Ognuna di queste $y$ configurazioni è raggiungibile da esattamente $k$ configurazioni, ovvero quelle che vi differiscono per una e una sola moneta. Ma $k*y < 2^k$, e perciò esistono configurazioni non raggiungibili.

[andomito]

La soluzione proposta presuppone che l'unica informazione che possa essere trasferita è la sequenza testa-croce della serie di monete.
Il testo del quesito, peraltro, non specifica che il carceriere risistema le monete ben benino prima di far entrare il secondo prigioniero, e quindi permette qualche margine ulteriore di trasferimento di informazioni che potrebbe essere utilmente sfruttato.

Testo nascosto, fai click qui per vederlo

La configurazione "testa" può infatti essere interpretata in più modi (diciamo 4: naso rivolto a destra, a sinistra, verso il prigioniero o in direzione opposta) e quella "croce" pure (almeno due per la croce greca [+ e x]; e 4 per la croce latina). I ragionamenti fatti, pertanto, potrebbero essere riformulati avendo a base non i numeri binari, ma quelli ottuagesimali (si dice così?) aumentando il numero di configurazioni risolvibili. [NB per la soluzione non importa l'orientamento]
Comunque, se fossi uno dei prigionieri, adotterei una soluzione molto più semplice: girerei la moneta indicata dal carceriere con una mano imbrattata di sporcizia.

[andomito]

per completare l'idea del precedente post...e indovinare sempre senza sporcarmi le mani

Testo nascosto, fai click qui per vederlo

Come detto, con il sistema binario posso individuare precisamente la posizione nelle prime $2^k$ monete, accettando una sconfitta certa nel caso il carceriere scelga la moneta nelle ulteriori $n-2^k$ monete. Statisticamente ciò significa mediamente una sconfitta ogni 4 partite (circa).
Ma se nel voltare la moneta posso cambiarne l'orientamento (far indicare alla faccia o alla base della croce un punto cardinale a mia scelta) vuol dire che (sempre fissando l'attenzione sulle prime $2^k$ monete) posso modificare anche il criterio di parità NESO (nord est sud ovest) di esse. A questo punto posso concordare con l'altro prigioniero che NE corrisponde alle prime $2^k$ monete, SO a quelle successive e indovinare sempre.
Per fissare le idee , associo un numero a ogni punto cardinale (NESO -> 2 4 1 3) faccio la somma di tali numeri nelle prime $2^k$ monete. Se ho modificato l'orientamento delle moneta voltata in modo che tale somma è pari vuol dire che la moneta scelta è tra le prime $2^k$, se la somma è dispari vuol dire che alla posizione trovata con il criterio testa-croce devo aggiungere $2^k$ posizioni.

... e mi avanza anche un bit di informazione con il quale posso scambiare informazioni aggiuntive con l'altro prigioniero. Che lusso!

[Vincent46]

per completare l'idea del precedente post...e indovinare sempre senza sporcarmi le mani

Testo nascosto, fai click qui per vederlo

Come detto, con il sistema binario posso individuare precisamente la posizione nelle prime $2^k$ monete, accettando una sconfitta certa nel caso il carceriere scelga la moneta nelle ulteriori $n-2^k$ monete. Statisticamente ciò significa mediamente una sconfitta ogni 4 partite (circa).
Ma se nel voltare la moneta posso cambiarne l'orientamento (far indicare alla faccia o alla base della croce un punto cardinale a mia scelta) vuol dire che (sempre fissando l'attenzione sulle prime $2^k$ monete) posso modificare anche il criterio di parità NESO (nord est sud ovest) di esse. A questo punto posso concordare con l'altro prigioniero che NE corrisponde alle prime $2^k$ monete, SO a quelle successive e indovinare sempre.
Per fissare le idee , associo un numero a ogni punto cardinale (NESO -> 2 4 1 3) faccio la somma di tali numeri nelle prime $2^k$ monete. Se ho modificato l'orientamento delle moneta voltata in modo che tale somma è pari vuol dire che la moneta scelta è tra le prime $2^k$, se la somma è dispari vuol dire che alla posizione trovata con il criterio testa-croce devo aggiungere $2^k$ posizioni.

... e mi avanza anche un bit di informazione con il quale posso scambiare informazioni aggiuntive con l'altro prigioniero. Che lusso!

Testo nascosto, fai click qui per vederlo

Purtroppo sono speciali monete matemagiche, in cui "testa" e "croce" sono rappresentate rispettivamente da una faccia rossa e una blu. Il carceriere controlla ogni mossa del prigioniero, e se se si accorge di qualche trucchetto sporco... beh, non finisce bene né per A né per B
Però bel tentativo!

[andomito]

Suppongo che sporcare, disallineare, graffiare, scaldare .. la moneta che si gira sia inteso come giocare sporco, e in effetti il carceriere se ne può accorgere abbastanza facilmente.
Ma anche prolungare ad arte (ad esempio due ore), da parte di A, la scelta della moneta da girare ?
Così B potrebbe orientarsi tra le prime $2^k$ monete o le restanti considerando quanto tempo dopo A viene chiamato.
Se il gioco è una tantum il carceriere non può protestare (nelle regole non ha dato ad A un tempo limite, anzi gli ha implicitamente detto di scegliere con attenzione), e verosimilmente non può neanche accorgersene. Solo se il gioco si ripete e A impiega tempi molto diversi a scegliere, alla lunga il carceriere capirà il trucco.

... sì, lo so, dirai che in ogni caso A è chiamato alle otto del mattino e B alle otto di sera, per rispettare il presupposto che i prigionieri non possono scambiarsi altre informazioni, ma (come la precisazione che testa e croce sono in realtà due colori) mi sa tanto di provvedimento che il carceriere può aver preso solo dopo essere stato fregato in passato da qualche scaltra coppia di prigionieri.
Quindi eviterò di postare ulteriori idee su come contrabbandare il bit in più che mi serve per risolvere sempre il problema, per evitare di dare dritte ad eventuali carcerieri in lettura.