Il direttore di un carcere comunica a due prigionieri che faranno il seguente gioco, i quali avranno una notte di tempo per accordarsi su una strategia e dopo di che non potranno più comunicare.
Il direttore posizionerà una chiave dentro una casella a caso di una scacchiera 8x8 situata in una stanza isolata. La chiave ovviamente non si vede. Dopodiché prenderà 64 monete identiche e una ad una le lancerà, con probabilità 1/2 esce testa e con probabilità 1/2 esce croce, una volta che lo stato della moneta è determinata la posizionerà sulla prima casella senza moneta. Ripete questa cosa fino a quando su ogni casella c'è una moneta. Ricapitolando la situazione è la seguente: una scacchiera 8x8, una chiave dentro una qualunque casella scelta a caso, e su ogni casella una moneta che indicherà o testa o croce a caso con probabilità 1/2, tutte le variabili aleatorie sono ovviamente indipendenti.
Finito il tempo a disposizione per accordarsi su una strategia, i due prigionieri non potranno più comunicare e a questo punto il prigioniero 1 entrerà nella stanza in cui c'è la scacchiera osservandola per la prima volta, il direttore gli comunicherà la posizione della chiave e il prigioniero 1 dovrà cambiare lo stato di una moneta a sua scelta (una testa renderla croce, o una croce renderla testa). Poi il prigioniero 1 esce ed entra il prigioniero 2, i due non possono comunicare in nessun modo. Il prigioniero 2 osservando per la prima volta la scacchiera, dovrà indicare una delle 64 caselle. Se il prigioniero 2 indicherà la casella con la chiave i due prigionieri sono liberi di andare, altrimenti vengono giustiziati.
Come fanno i prigionieri a liberarsi?