01.06.21

Das Schachbrett-Rätsel – Lösung

Vorletzte Woche haben wir euch ein Rätsel vorgestellt und gefragt, ob ihr es schafft, dieses zu lösen.

 

An alle die es selbst geschafft haben an dieser Stelle einen herzlichen Glückwunsch!

Hier findet ihr nun die korrekte Lösung:

Lösung Schritt 1

Fangen wir erst einmal klein an: mit einem „Schachbrett“ aus zwei Feldern. Dieselben Regeln, aber viel übersichtlicher.

Informatiker haben es gerne binär, also ist Kopf jetzt 1 und Zahl 0. Zwei Felder sind zwei Bits. Wir vereinbaren folgendes: Das zweite Bit gibt an, welches Feld das „Schlüsselfeld“ ist. Ist es das erste (für Informatiker: 0-te) Feld, drehen wir die Münze des zweiten Feldes auf Zahl (=0); ist es das zweite (für Informatiker: 1-te) Feld, drehen wir die Münze des zweiten Feldes auf Kopf (=1). Wenn diese Münze bereits mit der richtigen Seite nach oben zeigte, drehen wir einfach die Münze auf dem ersten Feld um, denn wir müssen ja genau eine Münze umdrehen.

 

Wie groß (in Bits) ist die Information, die wir hier übermitteln müssen? Genau: 1 Bit, denn damit kann man nach vorheriger Einigung sagen, welche Münze auf dem Schlüsselfeld liegt. Für ein Bit reichen zwei Münzen, weil man eine umdrehen muss.

 

Die ganze Lösung

 

OK, das war einfach. Man kann jetzt per Induktion zeigen, dass man für n Bit an Informationen immer 2 hoch n Münzen braucht. (Und auch, dass es nur funktioniert, wenn die Gesamtzahl der Felder 2 hoch irgendetwas ist.) In unserem Fall brauchen wir 6 Bit und dafür 2 hoch 6 = 64 Münzen.

Aber wir machen nicht mathematisch induktiv weiter, sondern konkret.

 

Zählen wir alle Felder auf dem Schachbrett von 0 bis 63 durch (0 links oben, 63 rechts unten).

Wir benennen die Spalten von links nach rechts wie bei Schachbrettern üblich von „a“ bis „h“ und die Zeilen von unten nach oben (!) mit „1“ bis „8“.

Jetzt schauen wir uns die einzelnen Bits der Zahlen 0 bis 63 der Reihe nach an.

 

Alle Zahlen, bei denen das erste Bit (000001) gesetzt ist (also die ungeraden: 1, 3, 5…), liegen auf dem Schachbrett in den Spalten „b“, „d“, „f“ und „h“ wie unten eingefärbt. Die anderen Spalten beinhalten die Zahlen, bei denen dieses Bit nicht gesetzt ist (also die geraden Zahlen).

 

 

Alle Zahlen, bei denen das zweite Bit (000010) gesetzt ist (2, 3, 6, 7 usw.) liegen in den Spalten „c“, „d“ sowie „g“, „h“.

 

 

 

Und so geht es weiter: Alle Zahlen, bei denen das dritte Bit (000100) gesetzt ist (4, 5, 6, 7, 12, 13…)  liegen in der rechten Hälfte (Spalten e, f, g, h) des Schachbretts, die, bei denen das Bit nicht gesetzt ist, in der linken.

Beim vierten Bit (001000) wechseln wir von den Spalten zu den Zeilen, denn alle Zahlen, bei denen dieses Bit gesetzt ist, liegen in den Reihen „1“, „3“, „5“ und „7“ (von unten nach oben gezählt).

Wenn das fünfte Bit (010000) gesetzt ist, beschreibt das auf dem Schachbrett alle Felder der Reihen „1“, „2“ sowie „5“ und „6“.

Wenn das sechste Bit (100000) gesetzt ist, beschreibt das auf dem Schachbrett die untere Hälfte (Reihen 1-4) des Schachbretts.

 

Du – der erste Gefangene – weißt, welches das Schlüsselfeld ist. Du zählst nun alle Münzen auf den Feldern, die zu „Bit 1“ gehören (also Spalten „b“, „d“, „f“ und „h“). Wenn diese Zahl gerade ist, dann ist das Ergebnis 0, sonst 1. Dieses „Bit-1-Ergebnis“ des Schachbretts schreibst du auf.

Jetzt zählst du alle Münzen auf den Feldern, die durch Bit 2 markiert sind und „Kopf“ zeigen, und bekommst dein „Bit-2-Ergebnis“ des Schachbretts. So geht es weiter, bis du alle 6 Ergebnisse hast. Das ist eine Zahl mit 6 Bit, also zwischen 0 und 63. Wir nennen sie „6-Bit-Zustand“ des Schachbretts.

Wir können also jeder der 18 Trillionen Möglichkeiten, wie die Münzen liegen können, eine Zahl zwischen 0 und 63 zuordnen.

 

Was bringt uns das? Wie kannst du jetzt eine Münze drehen, so dass aus dem aktuellen „6-Bit-Zustand“ der Zustand wird, der das Schlüsselfeld angibt?!

Wenn man weiß, wie es geht, ist das recht einfach. Wir müssen dafür die Bit-Operation „XOR“ (exklusives Oder) anwenden. Dabei wird aus zwei Bits ein Ergebnis berechnet: Nur wenn beide Bits unterschiedlich sind, kommt „1“ heraus, sind sie gleich, dann „0“.

Nehmen wir an, das Schlüsselfeld ist Feld 7 (000111) und der aktuelle 6-Bit-Zustand gemäß obiger Zählweise ist 43 (101011), dann wenden wir der Reihe nach XOR auf die Bitfolge 000111 und 101011 an, setzen also die unterschiedlichen Bits auf 1 und erhalten 101100 (44) und drehen die Münze auf Feld 44 um. Ermittelt unser Kumpane nach obiger Zählweise wieder den „6-Bit-Zustand“, bekommt er 7 heraus, das Schlüsselfeld!!

 

Sonderfall am Rande: Auch hier kann es wie beim Beispiel mit zwei Feldern natürlich vorkommen, dass der 6-Bit-Zustand des Schachbretts schon korrekt ist. Du musst auch dann eine Münze umdrehen, was tun? Dasselbe wie oben: Du wendest dann beim „6-Bit-Zustand“ des Schachbrett XOR auf dieselbe Zahl an. Da dann kein Bit abweicht, bekommt man 0 heraus. Das heißt, das Feld 0 kann man drehen und wenden wie man will, es hat keine Auswirkungen auf das Ergebnis.

 

Wer das noch genauer nachvollziehen möchte, für den gibt es diese ausführlichen und sehr lesens- bzw. sehenswerten Erklärungen:

 

https://www.youtube.com/watch?v=as7Gkm7Y7h4

https://datagenetics.com/blog/december12014/index.html.

 

 

Wir hoffen euch hat das Rätseln so viel Spaß gemacht wie uns

 

Euer Faktor Zehn-Team

XS
SM
MD
LG
Share
Sprachauswahl Icon
We noticed your browser language is not German.
Do you want to switch to English?