10 Bäume

Informatik - ein Rätsel? Nein, die Informatik ist kein Rätsel, sondern sie kann uns dabei helfen, Rätsel zu lösen.

Schauen wir uns hierzu die Fragestellung mit den Baumreihen auf der Karte an, so erkennen wir schnell, dass die fünf Baumreihen nicht unabhängig von einander sein können, da dann zwanzig Bäume nötig wären. Die Baumreihen müssen sich also Bäume teilen.

Pentagramm1

Da fünf Baumreihen mit jeweils vier Bäumen gefunden werden sollen, ist es in jedem Fall sinnvoll, mit einer davon anzufangen.

 

 

 

Pentragramm2

 

Eine zweite Baumreihe muss mindestens einen Baum der ersten Reihe wieder verwenden, kann aber keine zwei wieder verwenden, denn sonst wäre es dieselbe.

 

 

Pentagramm3

 

Um die dritte Baumreihe möglichst sparsam zu Ende zu bringen, sollte sie sich mit beiden bereits existierenden Reihen jeweils einen Baum teilen. Auch in diesem Fall sollte es jeweils nur genau ein Baum sein, da sie sonst mit einer der beiden anderen Reihen identisch wäre.

 

Pentagramm4

 

 Da bereits neun Bäume gepflanzt wurden, bleibt nur noch genau ein Baum übrig für die letzten beiden Reihen. Da wir insgesamt vier Bäume für eine Reihe brauchen, müssen wir mindestens drei aus bereits existierenden Reihen nehmen. Indem wir die bereits gesetzten Bäume geschickt verschieben, können wir drei aus drei verschiedenen Reihen so positionieren, dass wir die vierte Reihe durch Hinzufügen eines einzigen Baums finden können.

 

Pentragramm

 

Nun steht uns kein weiterer Baum mehr zur Verfügung, es fehlt aber noch eine letzte Reihe. Diese müssen wir also durch Verwenden von vier schon gepflanzten Bäumen anlegen. Erfreulicherweise ist dies möglich, und wir sehen, dass wir eine Lösung für das Rätsel gefunden haben.

 

 

Wenn Sie das interessiert hat, dann fragen Sie sich nun vielleicht:
- Gibt es noch mehr Lösungen?
- Wie sieht es aus, wenn Baumreihen fünf oder sechs Bäume enthalten sollen?
- Gibt es ein allgemeines "Rezept", mit dem sich alle Rätsel dieses Typs lösen lassen?

Solche "Rezepte" werden in der Informatik Algorithmen genannt. Die Entwicklung neuer Algorithmen und die Untersuchung bereits bekannter sind wichtige Forschungsthemen. Bespielsweise ist die Vorgehensweise, die wir verwendet haben, ein sogenanntes Greedy-Verfahren, da in jeden Schritt "gierig" das Bestmögliche getan wird. Dieses Verfahren ist bei Weitem nicht bei jeder Aufgabe zielführend. Deshalb hat die Informatik ein reichhaltiges Repertoire an - zum Teil sehr unterschiedlichen - Techniken entwickelt, mit denen sich vielfältige Probleme lösen lassen. Das Spektrum reicht dabei von der Optimierung von Geschäftsprozessen über wissenschaftliche Simulationen bis hin zu Computerspielen.