I carcerati e il lancio della moneta.

[Studente Anonimo]

Due carcerati, il 378 ed il 459, entrambi in carcere per truffa ed entrambi amanti del gioco d'azzardo, decidono di giocarsi le rispettive 20 sigarette giornaliere con testa e croce. Il gioco funziona così: Nei giorni pari il 378 lancia la moneta e il 459 scommette sul risultato. Se il 459 indovina guadagna 2 sigarette da 378. Se il 459 sbaglia allora deve dare 2 sigarette al 378. Il lancio della moneta viene fatto in tutto per 3 volte. Nei giorni dispari invece i ruoli s'invertono.
I due prigionieri sono in celle separate, non si vedono ma possono comunicare a voce e passarsi le sigarette da un piccolo pertugio nel muro della dimensione giusta.

Nessuno dei due carcerati si fida dell'altro, come possono fare in modo che il gioco sia equo? Ovvero che entrambi abbiano \( 1/2\) di probabilità di vincere ad ogni lancio di moneta?

Dopo una settimana il direttore del carcere scopre che i due giocano d'azzardo nel suo carcere e gli impedisce di comunicare dopo aver fatto chiudere la fessura nel muro. Nonostante ciò i due carcerati corrompono un secondino, dandogli ciascuno 5 sigarette. La guardia farà da tramite sia per le sigarette sia per comunicare le relative scommesse e i risultati sul lancio della moneta. Questa volta i due carcerati, non solo continuano a non fidarsi l'uno dell'altro, ma temono entrambi che la guardia comunichi dei risultati fasulli ad entrambi e si tenga tutte le sigarette. Come fanno questa volta i carcerati a fare in modo che il gioco sia equo?

[gabriella127]

"3m0o":Va bene accetto la tua soluzione, e quella di Hydro naturalmente!

Edit: ti faccio notare che anche il primo problema si può risolvere senza che la comunicazione avvenga nello stesso istante

Ci penserò appena ho un momento di calma, al momento ho troppe interferenze di altre cose che mi deconcentrano... Ma vi dico un'idea.

L'idea che mi viene immediata è che in questo caso la strategia deve abbracciare più di un giorno, non può essere relativa a un singolo lancio (ricordo chei giorni pari il primo detenuto lancia la moneta, e nei giorni dipari si inverte, a qualcosa deve servire). Caso mai una strategia di due giorni, e che preveda che il regolamento dei pagamenti in sigarette avvenga solo alla fine, e non giocata per giocata.
Se l'idea può servire e qualcuno ci pensa al posto mio, mi risparmio la fatica .
Se no poi ci penserò meglio.

[Studente Anonimo]

@gabriella127

Pensaci pure con calma, ma di nuovo i giorni pari e dispari era solo per abbellire la storiella
La strategia è relativa al singolo lancio!

[gabriella127]

Be' mi sono fatta confondere da quello, pensavo che se c'era doveva servire a qualcosa, che ci doveva essere una strategia complessiva. Ci ripenso allora!

[Studente Anonimo]

Se qualcuno volesse degli indizi su come ho fatto io. ATTENZIONE INDIZIO:

Indipendentemente da chi parla per primo, se l'informazione che dice è chiara l'altro ha una strategia dominante.
Se chi scommette dice la sua scommessa l'altro può mentire e dire sempre l'opposto.
Se chi lancia dice il risultato del lancio per primo, beh... l'altro può mentire e dire di aver scommesso su quello che è uscito.
L'indizio che mi sento di dare è il teorema fondamentale dell'aritmetica

[hydro1]

Ok, propongo un'altra soluzione puramente teorica, così tanto per divertimento.

Se $A$ è quello che lancia la moneta e $B$ è quello che scommette, si gioca così. $A$ sceglie una chiave pubblica $(n,d)$ come in RSA, ovvero $n$ è prodotto di due primi grandi e $d$ è coprimo con $\varphi(n)$. Adesso lancia la moneta e poi comunica a $B$ la chiave pubblica e il risultato cifrato del lancio. Ora $B$ sceglie come scommettere (come abbiamo già detto sceglie testa/croce 50-50)e comunica ad $A$ la scommessa. Infine, $A$ comunica a $B$ la chiave privata. Adesso nessuno può barare perchè: $B$ non può ricavare la chiave privata perchè è difficile, quindi non può sapere qual è il risultato del lancio; $A$ non può mentire sulla chiave privata $e$ perchè $B$ può verificare facilmente se $ed\equiv 1\mod n$ oppure no.

[Studente Anonimo]

Hydro

Con una variazione della tua risposta è quello che ho trovato io come soluzione alla seconda domanda, ti lascio pensare come modificare la tua risposta in modo appropriato in modo tale che funzioni per la seconda domanda. Io per la risposta alla prima domanda ho fatto diversamente ma come hai fatto te funziona perfettamente.

Do la mia soluzione alla prima domanda

Supponiamo che \(A\) lancia la moneta e \(B\) scommette. Si mettono d'accordo che se un intero \(n\) si fattorizza in un numero pari di numeri primi distinti allora il risultato è croce, mentre se \(n\) si fattorizza in un numero dispari di primi distinti allora il risultato è testa (ad esempio).
\(A\) lancia la moneta (oppure no) e poi sceglie \(k\) numeri primi molto grandi, diciamo \(p_1,\ldots,p_{k} \), dove \(k \equiv 0 \mod 2 \) se vuole comunicargli croce mentre \(k \equiv 1 \mod 2 \) se vuole comunicargli testa. Dunque \(A\) trasmette \(n\) a \(B\), dove
\[ n= \prod_{j=1}^{k} p_j \]
A questo punto per \(B\) è difficile trovare la fattorizzazione di \(n\) e scommette (lanciando una moneta) su testa o croce. \(A\) gli comunica quindi i primi \(p_1,\ldots,p_{k} \) e \(B\) può verificare facilmente che effettivamente
\[ n= \prod_{j=1}^{k} p_j \]
inoltre verifica la parità di \(k\) e quindi nessuno può più mentire.

[Studente Anonimo]

Ricordo che la domanda 2 è la seguente

"3m0o":
[quote="3m0o"]
Dopo una settimana il direttore del carcere scopre che i due giocano d'azzardo nel suo carcere e gli impedisce di comunicare dopo aver fatto chiudere la fessura nel muro. Nonostante ciò i due carcerati corrompono un secondino, dandogli ciascuno 5 sigarette. La guardia farà da tramite sia per le sigarette sia per comunicare le relative scommesse e i risultati sul lancio della moneta. Questa volta i due carcerati, non solo continuano a non fidarsi l'uno dell'altro, ma temono entrambi che la guardia comunichi dei risultati fasulli ad entrambi e si tenga tutte le sigarette. Come fanno questa volta i carcerati a fare in modo che il gioco sia equo?

Per questo forse è bene aggiungere, che evidentemente i detenuti decidono la loro strategia comunicando direttamente tra loro prima che il carcere gli impedisca di comunicare, altrimenti la guardia potrebbe chiaramente interferire nella comunicazione della strategia.
[/quote]
Pseudo indizio:

Diciamo che i due carcerati sono \(A\) e \(B\) e la guardia è \(C\). Il problema adesso è che non solo \(A\) (rispettivamente \(B\)) deve capire se \(B\) gli ha mentito (risp. \(A\)), ma dev'essere pure certo che \(C\) non altera il messaggio inviato da \(B\) (risp. da \(A\)).

[Studente Anonimo]

Soluzione alla domanda 2

I due carcerati \( A \) e \(B\) scelgono entrambi due numeri primi molto grandi e li tengono segreti, diciamo che \(A\) sceglie \(p_A, q_A \) e \(B\) sceglie \(p_B\) e \( q_B\). Sia \(X=A,B\), entrambi si calcolano \( n_X = p_X q_X \), e \( \varphi(n_X) \). Entrambi poi scelgono \(e_X < \varphi(n_X) \) tale che \( \operatorname{gcd}(e_X,\varphi(n_X) ) = 1 \) e successivamente calcolano \( d_X \) tale che \( d_X e_X \equiv 1 \mod \varphi(n_X) \).

Entrambi ora hanno una chiave pubblica \( (n_X,e_X) \) ed una privata \( (n_X,d_X)\). Entrambi si comunicano le rispettive chiavi pubbliche prima che gli venga impedito di comunicare.

A questo punto, supponiamo che \(A\) lancia la moneta e \(B\) scommette. Ovvero \( A \) dice un intero \(m\) che se si fattorizza in \(k\) primi distinti. Se \( k \equiv 1 \mod 2 \) allora il risultato del lancio è testa, altrimenti è croce.

Solo che questa volta \(A\) non comunica \(m_A\) ma utilizza la propria chiave privata per criptare \(m_A\) nel seguente modo: \( m_1 := m_A^{d_A} \mod n_A \). A questo punto utilizza la chiave pubblica di \(B\) per criptare \(m_1\) ed ottenere \(c_A := m_1^{e_B} \mod n_B \).
A questo punto \(A\) comunica \(c_A\) alla guardia \(C\), il quale se è onesto dice \(c_A\) a \(B\), se altera il messaggio invece trasmette \(\tilde{c}_A\) a \(B\).
Analogamente \(B\) lancia una moneta ed in base al risultato scommette se è testa o croce. A dipendenza del risultato a cui vuole scommettere sceglie \(k\) primi distinti che non contengo la cifra zero, \(p_1,\ldots,p_k\), dove la parità di \(k\) indica il risultato della scommessa e forma il numero \(m_B:= p_1 0 p_2 0 \ldots p_{k-1} 0 p_k 0 \prod_{j=1}^{k} p_j \). Con una procedura analoga a quella di \(A\), \(B\) dapprima cripta il messaggio \(m_B \) con la sua chiave privata ottenendo \( m_2 := m_B^{d_B} \mod n_B\) e poi cripta \(m_2\) con la chiave pubblica di \(A\) ottenendo \(c_B := m_2^{e_A} \mod n_A \).
Poi comunica a \(C\) il messaggio \(c_B\).

Se \(C\) è onesto allora passa \(c_B\) ad \(A\) e passa \(\tilde{c}_B\) a \(A\).

Ora \(A\) controlla la scommessa di \(B\). Per farlo prende il numero comunicatogli da \(C\) e fa la procedura inversa usa la sua chiave privata per decifrare \(c_B\), dovrebbe ottenere \(m_2 = c_B^{d_A} \mod n_A \). E poi usa la chiave pubblica di \(B\) per verificare \(C\) non ha alterato il messaggio \( m_B = m_2^{e_B} \mod n_B \).
A questo punto se \(A\) ottiene un numero della forma
\[ m_B = a_1 0 a_2 0 \ldots a_k 0 a_{k+1} \]
controlla che
\[ a_{k+1} = \prod_{j=1}^{k} a_j \]
se non ottiene un numero della forma di cui sopra o se
\[ a_{k+1} \neq \prod_{j=1}^{k} a_j \]
allora \(C\) ha alterato il messaggio. Se \(C\) non ha alterato il messaggio sempre con la stessa procedura comunica i numeri primi a \(B\). \(B\) può verificare in modo analogo ad \(A\), sia per \(m_A\) sia per i primi trasmessi che il messaggio non è stato alterato da \(C\).

[axpgn]

Per 20 sigarette? Naaaaaa!

[Studente Anonimo]

[gabriella127]

@3m0o

Dovevi specificare meglio il testo del problema:
"Due dottori di ricerca in matematica, detenuti per avere rubato galline per sopravvivere in attesa di concorsi all'università, fanno il seguente gioco etc. etc."

[axpgn]

[Studente Anonimo]

"gabriella127":@3m0o

Dovevi specificare meglio il testo del problema:
"Due dottori di ricerca in matematica, detenuti per avere rubato galline per sopravvivere in attesa di concorsi all'università, fanno il seguente gioco etc. etc."

Vabbé (vabbè?!)... dottori in matematica è un po' esagerato
Mmmh, dici che in futuro mi toccherà rubare galline per sopravvivere?

[gabriella127]

'Furto di galline' è nel curriculum di qualunque ricercatore che si rispetti.

[Studente Anonimo]