Prigionieri e monete

[Vincent46]

Ci sono due prigionieri, A e B, di fronte a una stanza chiusa. Il carceriere (un po' sadico, tanto per cambiare) propone loro il seguente gioco per guadagnarsi la liberertà: dapprima, A entra nella stanza, dove c'è un certo numero di monete disposte in fila su un tavolo, che mostrano testa oppure croce. Il carceriere gliene indica una, dopodiché A deve voltare una e una sola delle monete sul tavolo (cioé farla passare da testa o croce o viceversa). Infine, A esce dalla stanza e B vi entra. I prigionieri vincono se B riesce a indovinare la moneta indicata ad A dal carceriere. Ovviamente non è permessa nessuna comunicazione fra i prigionieri durante lo svolgimento del gioco.

Come al solito, A e B possono mettersi d'accordo su una strategia di gioco prima di intraprendere la partita. Dimostrare che esiste una strategia vincente se e solo se il numero di monete sul tavolo è una potenza di 2.

[axpgn]

Avrei trovato uno schema con quattro monete ...

[dan952]

C'entrano qualcosa i numeri binari?

[Settevoltesette]

con 3 monete esiste una strategia vincente

[Vincent46]

"dan95":C'entrano qualcosa i numeri binari?

yes! almeno per la direzione del "se".

"Settevoltesette":con 3 monete esiste una strategia vincente

No... ricorda che A deve necessariamente girare una moneta.

[dan952]

La butto lì...

Se ci sono $2^n$ monete allora abbiamo $2^(2^n)$ numeri binari corrispondenti, per esempio, se le monete sono 4 avremo 16 possibili configurazioni (numeri binari)

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Ora i due prigionieri si accordano sul fatto che 0=testa e 1=croce, a questo punto i $2^(2^n)$ numeri binari vengono suddivisi in $2^(2^n-n)$ stringhe lunghe $2^n$ numeri e ogni numero della stringa viene fatto identificare ad un numero da 1 a $2^n$ (senza ripetizioni) in modo che cambiando un solo 0 o 1 in un numero binario appartenente ad una stringa possono ottenere un un numero binario appartenente ad un'altra stringa che identifica un qualsiasi numero da 1 a $2^n$.

[Vincent46]

"dan95":La butto lì...

Se ci sono $2^n$ monete allora abbiamo $2^(2^n)$ numeri binari corrispondenti, per esempio, se le monete sono 4 avremo 16 possibili configurazioni (numeri binari)

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Ora i due prigionieri si accordano sul fatto che 0=testa e 1=croce, a questo punto i $2^(2^n)$ numeri binari vengono suddivisi in $2^(2^n-n)$ stringhe lunghe $2^n$ numeri e ogni numero della stringa viene fatto identificare ad un numero da 1 a $2^n$ (senza ripetizioni) in modo che cambiando un solo 0 o 1 in un numero binario appartenente ad una stringa possono ottenere un un numero binario appartenente ad un'altra stringa che identifica un qualsiasi numero da 1 a $2^n$.

Uhm, non so se ho capito bene... Non dovresti comunque dimostrare che le configurazioni si incastrano bene? Cioé che per ogni $n$ e $m$, si può passare da una configurazione associata alla moneta $n$ a una associata alla moneta $m$ girando una sola moneta?

[dan952]

Sì...ecco perché ho scritto "La butto lì", ci penso con più calma perché adesso come adesso non mi viene la dimostrazione.

[dan952]

Penso...

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...

[nino_12]

Mi pare lo stesso quiz:

http://www.trekportal.it/coelestis/show ... hp?t=27747

[Vincent46]

"dan95":Penso...

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...

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?):

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.

[dan952]

Ti faccio un esempio con 4 monete

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

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_12]

"Vincent46":
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]

"dan95":Ti faccio un esempio con 4 monete

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

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

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:

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:

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.

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

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]

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

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!

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.

[Vincent46]

Beh, il problema è che i carcerieri sono dispotici e i prigionieri non sono in posizione di potere. Quindi si può tentare di tutto, ma nessuno ti assicura che lui reagirà bene! Però hai ragione, vale comunque la pena tentarci nel caso in cui le monete sul tavolo non siano esattamente una potenza di due.