Indovinare il bit casuale con una precisione del 100% [chiusa]

C'è in realtà una soluzione che avrà sempre successo: il programma A indovina l'opposto del valore che riceve, il programma B indovinerà lo stesso valore di quello che riceve.

Puoi anche pensarlo in questo modo: A suppone che riceveranno numeri diversi; B pensa di ricevere lo stesso. Uno di questi è destinato a essere corretto. Se guardi la seguente tabella (r per ricevere, g per ipotesi), vedrai che A o B ha sempre ragione (* denota risposta corretta):

rA | rB | gA | gB
0     0    1    0*
0     1    1*   1
1     0    0*   0
1     1    0    1*

Dal momento che questa sembra una domanda trabocchetto, ecco una risposta a un trucco (cioè è "barare").

Lascia che il programma A faccia quanto segue:

• Se riceve uno 0, emette "1" ed esce.
• Altrimenti, loop per sempre, fino a quando non viene ricevuto un segnale "Ctrl-C", nel qual caso il programma emette "0" ed esce.

Lascia che il programma B faccia quanto segue:

• Se riceve uno 0, emette "0" ed esce.
• Altrimenti, loop per sempre, finché non viene ricevuto un segnale "Ctrl-C", nel qual caso il programma emette "1" ed esce.

Analisi:

• Se entrambi i programmi ottengono uno 0, il programma B emette "0", che è corretto - > win.
• Se il programma A ottiene uno 0 e il programma B ottiene un 1, allora il programma A emette "1", che è corretto - > win.
• Se il programma A ottiene un 1 e il programma B ottiene uno 0, quindi programma A cicli per sempre mentre il programma B emette "0" (che è sbagliato); a un certo punto, l'operatore che esegue l'esperimento perde la pazienza, digita Ctrl-C nel terminale che esegue il programma A, e vede "0" che è una risposta corretta - > win.
• Se entrambi i programmi ottengono un 1, entrambi i programmi si arrestano per sempre. L'operatore tenta di uccidere entrambi con Ctrl-C, a quel punto il programma A emette 0 e il programma B emette 1; il secondo è corretto - > win.

E voilà! una strategia vincente al 100%.

Modifica: e se dimentichi l'intera cosa "aspetta fino a Ctrl-C", allora ottieni essenzialmente la risposta di @ Helm, che è corretta e molto meno complicata. L'unico punto di quel processo di attesa è di ottenere un canale laterale in base al quale un programma non solo può indovinare il valore, ma anche "sapere" che ha indovinato il valore (che comunque non fa parte della sfida).

Hai ragione. Il più vicino che potresti ottenere sarebbe il 75% di probabilità che almeno uno di essi sia corretto, con entrambi i computer che indovinano sempre la negazione dell'altro.

Poiché si tratta di guerra dell'informazione, mi chiedo se sono consentiti scenari con "barare". Potrebbe esserci un artefatto di livello di sistema che i programmi possono controllare dopo che il numero casuale è stato generato o uno dei programmi potrebbe collegarsi a quel processo, monitorarlo.

I requisiti dicono che i programmi sono isolati l'uno dall'altro, ma non necessariamente su sistemi separati. Potresti essere in grado di rilevare o influenzare il valore seme utilizzato dall'altra applicazione anche se entrambi si trovano sullo stesso sistema. Se stai scrivendo entrambe le applicazioni, potresti fare in modo che ciascuna applicazione stampi il valore e lasciare che l'altro sistema legga quel valore. Anche se queste sono su caselle separate, potresti teoricamente proporre una soluzione che utilizzava un tipo di monitoraggio termico o acustico .

Penso che la parola "indovinare" sia un espediente, non puoi avere alcuna certezza se stai solo indovinando. Questa domanda sembra più un modo di pensare a diversi modi di infrangere l'influenza del sistema e anche di capire come influenzare o prevedere i valori casuali.

NO non è possibile indovinare un bit generato a caso, con una precisione del 100%, si avrà ragione in media la metà delle volte.

Modifica: sono d'accordo che ho torto, ho letto la domanda come solo possedere uno dei programmi. Se possiedi entrambi, ognuno sarà corretto metà della volta, quindi in media sempre.