In Kooperation mit

Job & Karriere

Rätsel der Woche Welches Wort hat Stefan ausgewählt?

Aus einem dicken Wörterbuch hat sich Stefan ein Wort herausgesucht. Anke möchte es mit möglichst wenigen Versuchen erraten. Wie sollte sie dabei vorgehen?
Foto: Michael Niestedt / DER SPIEGEL

Bevor es um das Wörterbuchrätsel geht, noch eine kurze Anmerkung zum Rätsel aus der vergangenen Woche. Ein Quadrat sollte in vier gleichschenklige Dreiecke zerschnitten werden. Ich hatte drei Lösungen vorgegeben – und mehrere Leser haben mir eine weitere Zerlegung geschickt. Vielen Dank! Sie ist nun Teil des Lösungstextes.

Nun aber zum neuen Rätsel: Anke und Stefan haben sich ein Wortsuchspiel ausgedacht. Dazu benutzen sie ein Wörterbuch mit 262.143 verschiedenen Einträgen. Diese sind alphabetisch sortiert.

Stefan sucht sich aus dem Buch ein Wort heraus, ohne dass Anke sehen kann, welches Wort es ist und in welchem Teil des Buches es steht.

Anke soll das Wort nun mit möglichst wenigen Versuchen erraten. Sie darf immer nur ein Wort nennen – und Stefan sagt ihr dann, ob es das gesuchte Wort ist oder ob das gesuchte Wort im Wörterbuch weiter vorn steht oder weiter hinten. 

Wie viele Versuche braucht Anke, bis sie das gesuchte Wort mit Sicherheit genannt hat?  

Zur Lösung bitte nach unten scrollen!

Foto:

Michael Niestedt/ DER SPIEGEL

Lösung

Anke muss höchstens 18 Wörter nennen, bis sie das richtige gefunden hat.

Sie benutzt dabei einen sogenannten binären Suchbaum . Dabei halbiert sie, vereinfacht gesagt, die Anzahl der infrage kommenden Wörter bei jedem Schritt.

Im ersten Schritt stehen alle 262.143 Wörter zur Auswahl. Anke wählt das Wort, das im Wörterbuch genau in der Mitte steht. Also das Wort an Position 131.072. Davor stehen 131.071 Wörter – und danach ebenfalls.

Im günstigsten Fall hat sie zufällig das Wort erwischt, das sich Stefan ausgesucht hat. Wir müssen aber vom ungünstigsten Fall ausgehen. Und in diesem Fall sagt Stefan, das Wort stehe im Alphabet davor oder danach.

Anke weiß dann, dass sie unter 131.071 Wörtern weitersuchen muss, die im Alphabet aufeinanderfolgen. Sie wählt wieder das Wort genau in der Mitte – also das an Position 65.536. Davor stehen 65.535 Wörter – danach folgen ebenfalls 65.535. Und wieder sagt Stefan, ob sich sein gewählter Begriff im Alphabet davor oder danach befindet – oder ob Anke zufällig das Wort gefunden hat.

Diese Strategie nutzt Anke, bis nur noch drei aufeinanderfolgende Wörter zur Auswahl stehen. Sie nimmt wieder das in der Mitte stehende und kann nach der Antwort von Stefan das Wort nennen, das dieser sich herausgesucht hat. Insgesamt benötigt Anke dafür maximal 18 Schritte – siehe folgende Tabelle:

Dieses binäre Suchverfahren kann auch bei vielen anderen, ähnlich strukturierten Problemen angewandt werden. Etwa beim Rätsel vom einzufangenden Löwen – eine Knobelei, mit der sich der Fields-Medaillengewinner Peter Scholze als Kind beschäftigt hat.

Aber ist das Verfahren auch optimal? Ankes Strategie funktioniert und führt in höchstens 18 Schritten zum Ziel. Das bedeutet jedoch nicht, dass es keine andere Strategie gibt, die mit weniger Schritten auskommt. Wir können jedoch leicht zeigen, dass Ankes Vorgehen die beste Strategie ist.

Dabei fangen wir von hinten an – mit dem letzten Schritt: Ich darf ein Wort nennen, wie viele Wörter kann ich damit mit Sicherheit erraten? Genau eins.

Der nächste Schritt: Ich darf zweimal ein Wort nennen – wobei Stefan nach dem ersten Wort sagt, ob das gesuchte Wort im Alphabet davor steht oder danach – oder ob man zufällig das richtige Wort geraten hat. Aus wie vielen Wörtern findet man in zwei Schritten mit Sicherheit das gesuchte Wort?

Wir wissen: Beim letzten Schritt darf nur noch ein Wort übrig sein. Also muss beim Schritt davor, hier dem ersten Schritt, das Ergebnis "ein Wort" lauten. Das klappt, wenn drei Wörter gegeben sind und Anke das mittlere wählt. Nicht jedoch mit vier Wörtern. Denn dann müsste Anke eines der vier Wörter raten - und es ist möglich, dass nach Stefans Antwort zwei Wörter übrig bleiben. Also ist drei die maximale Wortanzahl bei zwei Schritten.

Hat Anke drei Schritte, dürfen nach dem ersten Schritt höchstens drei Wörter übrig bleiben. Die maximal mögliche Anzahl gegebener Worte ist dann sieben (2*3 + 1), wobei die 1 für das Wort in der Mitte zwischen den 2*3 = 6 Wörtern steht. Bei acht Wörtern reichen drei Schritte nicht in allen Konstellationen aus. Die Argumentation ist dabei wie oben: Es kann passieren, dass nach dem Nennen eines Wortes vier Wörter übrig bleiben – zu viele für die verbleibenden zwei Schritte.

Wir sehen: Mit jedem zusätzlichen Schritt erhöht sich die mögliche Wortzahl von w auf 2*w + 1. Daraus können wir leicht eine Formel für die Anzahl der Wörter ableiten, wenn die Schrittzahl n gegeben ist. Diese lautet 2n - 1.

Mit einem Schritt (n=1) können wir

2n - 1 = 21 - 1 = 1

Wort erraten. Mit zwei Schritten sind es

2*(21 - 1) + 1 = 22 - 1 = 3

Mit n Schritten sind es 2n - 1. Mit 18 Schritten lässt sich deshalb ein Wort aus maximal 218 - 1 Wörtern erraten - und 218 - 1 entspricht genau der Zahl der Wörter in dem Wörterbuch, nämlich 262.143.

Sollten Sie ein Rätsel aus den vergangenen Wochen verpasst haben – hier sind die jüngsten zehn Folgen:

Anzeige
Dambeck, Holger

Kommen drei Logiker in eine Bar...: Die schönsten Mathe-Rätsel (Aus der Welt der Mathematik, Band 3)

Verlag: KiWi-Taschenbuch
Seitenzahl: 240
Für 9,99 € kaufen
Produktbesprechungen erfolgen rein redaktionell und unabhängig. Über die sogenannten Affiliate-Links oben erhalten wir beim Kauf in der Regel eine Provision vom Händler. Mehr Informationen dazu hier

Korrektur: Die Fragestellung wurde so präzisiert, dass das Nennen des gesuchten Wortes im letzten Schritt eindeutig als Versuch zählt - so wie in der Tabelle. In einer früheren Version dieses Artikels wurde zudem im Text als Lösung 19 Wörter angegeben. Die korrekte Zahl lautet, wie in der Tabelle genannt, 18 Wörter.

Die Wiedergabe wurde unterbrochen.