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.

[Bokonon]

A favore del carceriere, faccio notare che nessuno gli vieta di girare nuovamente la moneta una volta che A è uscito