Man kann die Aufgabe vergleichen mit der Lokalisierung eines Bitfehlers in einem Datenstrom.
Die Hamming-Codierung ist eine gute Möglichkeit dazu.
Der Datenstrom sind die Münzen: Je nachdem, ob Kopf oder Zahl oben liegt, entsprechen Sie Null oder Eins.
Das gesuchte Feld ist die Stelle eines Bitfehlers.

Beim Hamming-Code werden Parity-Bits bestimmter Bereiche berechnet und ergeben so ein Parity-Wort (mehrere Bits, hier sechs).
Der erste Spieler kann eine Münze so umdrehen, dass das Parity-Wort anschließend die Nummer des Feldes ergibt, das der zweite Spieler erraten muss.
Mit sechs Bit funktioniert das hier für jede beliebige Konstellation von Münzen und das geht so:

1. Nummeriere alle Schachbrettfelder von Null (!) bis 63 in binärer Schreibweise: 000000, 000001, 000010, ..., 111110, 111111
2. Berechne für jede der sechs Stellen der Feldnummern ein Parity-Bit wie folgt:
1. Auf allen Feldern, deren Feldnummer an der jeweiligen Stelle eine Eins haben, zähle die Münzen, die "Zahl" (entsprechend Eins) zeigen!
2. Diese Anzahl modulo Zwei ergibt das Parity-Bit an dieser Stelle.
   (Mit anderen Worten: Wenn die Anzahl "Zahl" auf diesen Feldern ungerade ist, ist das Parity-Bit an dieser Stelle Eins, sonst Null.)
3. Berechne die Nummer des Feldes, dessen Münze du umdrehst, indem du die XOR-Verknüpfung bildest zwischen dem so entstandenen Parity-Wort und der Nummer des Feldes, das der zweite Gefangene erraten soll!
   (Die XOR-Verknüpgung ergibt ein Wort, das an den Stellen eine Eins hat, an denen die beiden Operanden unterschiedliche Bits haben. An den Stellen, an denen die Operanden gleiche Bits haben, hat die XOR-Verknüpgung eine Null. Biespiel: 0011 XOR 0101 = 0110
4. Drehe die Münze, die auf der so berechneten Feldnummer liegt!

Der zweite Gefangene berechnet dann auf dieselbe Weise wie Schritt 1 und 2 das Parity-Wort.
Das Ergebnis ist die Nummer des Feldes, das er erraten soll!
(Das Umdrehen der Münze führt dazu, dass das Parity-Wort beim ersten Gefangenen ein anderes ist als beim zweiten. - Außer wenn die Münze auf Feld Null umgedreht wurde. Dann waren in o.g. Schritt 3 das Schlüsselfeld und das Parity-Feld gleich und deswegen das XOR-Ergebnis 000000.)

Der Grund, warum sich das so ergibt liegt darin, dass die XOR-Verknüpfung umkehrbar ist: A XOR B = C ⇔ A XOR C = B

Interessant an diesem Rätsel ist, dass es nur für Schachbrettgrößen funktioniert, bei denen die Kantenlänge eine Zweierpotenz ist.

Hier gibt es eine Excel-Datei, mit der man diese Rechnung nachvollziehen kann.