Die Zahl mit 10 Stellen

CAU-Karte-Raetsel-10

Die gesuchte Zahl wird manchmal auch als "magische Folge" bezeichnet. Eine magische Folge ist allgemein eine Zahlenfolge, wobei die erste Zahl die Gesamtzahl der Nullen in dieser Folge angibt, die zweite Zahl die Gesamtzahl der Einsen in dieser Folge, und so weiter. Gesucht ist also eine magische Folge mit zehn Zahlen.

Um das Problem zu lösen, ist es hilfreich zunächst einmal mit kleineren Folgen anzufangen. Dabei kann festgestellt werden, dass das systematische Auffinden solcher Folgen nicht ganz einfach ist, weil die Werte an einer bestimmten Stelle die Werte an einer anderen Stelle beeinflussen. Bevor du weiterliest, solltest du vielleicht einmal versuchen, eine magische Folge mit drei Ziffern zu finden.



Nichts gefunden?
Dies ist auch nicht verwunderlich, denn so eine Folge gibt es nicht.
Zum Glück gibt es eine Folge mit vier Ziffern:

1,2,1,0

Dies ist eine magische Folge, denn sie enthält:

Anzahl: Ziffer
1       Null
2       Eins
1       Zwei
0       Drei

Es gibt aber noch eine magische Folge mit vier Ziffern: 2,0,2,0

Anzahl: Ziffer
2       Null
0       Eins
2       Zwei
0       Drei

Diese Folgen scheinen wirklich Magie zu sein, denn zum Beispiel gibt es eine Folge mit fünf Ziffern, aber keine mit sechs Ziffern.

Wie kommen wir aber an unsere Folge mit zehn Ziffern?

Wir könnten ausprobieren oder raten, aber dies ist wirklich sehr mühsam. Wenn man einfach alle Zahlen ausprobiert, kann es schon recht lange dauern. Alleine für vier Ziffern gibt es schon zehntausend Möglichkeiten, und bei zehn Ziffern sind es schon zehn Milliarden Möglichkeiten!

Für eine Informatikerin oder einen Informatiker ist dies aber kein Problem. Wir haben ja Computer, und die können ja schnell rechnen. Computer sind ideale Werkzeuge, um viele Möglichkeiten stupide auszuprobieren. Wenn Menschen für langweilige Berechnungen keine Lust haben, benutzen sie Computer. Dafür wurden Computer
ursprünglich erfunden, auch wenn man heute vieles andere mit ihnen macht, wie Musik hören, Filme gucken,...

Aber zurück zu unserem magischen Rätsel. Wir könnten ein Programm schreiben, das einfach alle Zahlenfolgen nacheinander aufzählt und dabei probiert, ob dies eine magische Folge ist.
Dieser Test ist recht einfach, und wenn der Computer schnell genug ist, könnte dies klappen. Nehmen wir an, wir schreiben ein schnelles Programm, mit dem der Computer in jeder Sekunde eine Million Zahlenfolgen überprüfen kann. Dann könnten wir die zehn Milliarden möglicher Folgen mit zehn Ziffern in weniger
als drei Stunden überprüfen. Dies ist zwar nicht superschnell, aber ganz ok. Wir könnten ja nebenbei einen Spielfilm gucken...

Wenn wir aber eine magische Folge mit 20 Zahlen suchen, dann wird es schwierig: wenn wir mit unserem Computer eine Million Folgen pro Sekunde überprüfen, würde es über drei Millionen Jahre dauern, alle Folgen mit 20 Zahlen durchzutesten!

Da Informatikerinnen und Informatiker so viel Zeit auch nicht haben, überlegen sie sich in so einem Fall andere Methoden, damit Computer solche Probleme schneller lösen können. Es gibt tatsächlich manchmal schwierige Probleme, die in akzeptabler Zeit nicht exakt lösbar sind. Unser Rätsel ist aber sehr schnell lösbar, wenn man geeignete Programmiersprachen und ein paar gute Ideen verwendet. Wenn du ein Beispiel sehen will, wie dies gehen kann, dann schaue auf die folgende Webseite:

http://www-ps.informatik.uni-kiel.de/smap/smap.cgi?43

Hier findest du ein Programm, dass dieses Rätsel löst (einfach den Knopf "Run" betätigen, und nach kurzer Zeit erscheint im Fenser unter "Execution result" die Lösung). Und dieses Programm ist recht schnell. Man kann damit z.B. eine magische Folge mit 100 Zahlen in weniger als einer Sekunde finden! Hierzu muss man nur die Zahl "10" in der letzten Programmzeile (im linken Fenster "Source code") durch die Zahl 100 ersetzen und wieder "Run" drücken.

Man muss also nicht Millionen Jahre warten, wenn man die richtigen Methoden benutzt. Nicht verzweifeln, wenn man das Programm nicht versteht. So etwas erlernt
man im Informatikstudium in Kiel. Nach dem Bachelor weiß man, wie man so etwas programmiert.

Übrigens: das Programm ist in der Programmiersprache "Curry" geschrieben, die auch in Kiel mitentwickelt wird, und die Webseite wurde von einem Kieler Studenten im Rahmen seiner Bachelorarbeit entwickelt. Wer also Lust hat, kann so etwas auch im Rahmen des Informatikstudiums in Kiel entwickeln.