Lieber Erdling,
spielst Du auch gerne? Rudi hat mal wieder ein Quirk-Blatt im Garten gefunden.
Gesucht ist eine ganze Zahl zwischen 1 und 1000. Ihr dürft maximal 10 Ja-Nein-Fragen stellen, um sie zu finden.
Frage 1:
Hmm, nur 10 Fragen. Das sind nicht viele. Wenn wir nacheinander fragen würden: „Ist die gesuchte Zahl die 1?“ oder „Ist es die 2?“ oder „Ist es die 3?“ und so weiter, dann bräuchten wir im schlimmsten Fall 999 Fragen, bevor wir die gesuchte Zahl kennen würden. Wie sollen da nur 10 Fragen reichen?
Wir lehnen uns in unseren Gartenschaukelstühlen zurück und beißen in unsere Schokokuchenstücke. Mmmhhh, lecker! „Wenn wir wenigstens wüssten, ob es eine große oder eine kleine Zahl ist.“, murmelt Rudi. „Ja. Dann lass uns doch einfach mal danach fragen. Aber was heißt hier eigentlich große oder kleine Zahl?“, murmel ich zurück. Wir grübeln kurz, aber eigentlich ist die Antwort schnell klar. Wir sollten die Zahlen von 1 bis 1000 in zwei möglichst gleich große Teile aufteilen:
• die Zahlen von 1 bis 500 und
• die Zahlen von 501 bis 1000.
Das sind dann jeweils noch 500 Zahlen. Immer noch viel, aber auf jeden Fall besser, als die 1000 Möglichkeiten, die wir momentan zur Auswahl haben. Jetzt müssen wir nur noch wissen, in welcher Hälfte sich die gesuchte Zahl ist. Wir schreiben also auf das Quirkblatt:
Frage 1: Ist die Zahl kleiner oder gleich 500?
Und plopp! Weg ist es. Und im Sternenglitter segelt auch schon ein neues Blatt herunter.
Die gesuchte Zahl ist kleiner oder gleich 500. Ihr dürft noch maximal 9 Ja-Nein-Fragen stellen, um sie zu finden.
Frage 2:
Super. Mit nur einer Frage haben wir 500 mögliche Zahlen aussortiert und wissen jetzt, dass die gesuchte Zahl zwischen 1 und 500 liegt. Doch was nun? Schaukelnd mampfen wir weiter an unserem Schokokuchen. „Wenn wir wenigstens wüssten, ob es eine große oder eine kleine Zahl ist.“, murmelt Rudi schon wieder. „Drache Rudi! Das ist es!“ Wir sollten die verbliebenen Zahlen wieder in zwei möglichst gleich große Portionen aufteilen:
• die Zahlen von 1 bis 250 und
• die Zahlen von 251 bis 500.
Das sind dann jeweils noch 250 Zahlen. Wir schreiben auf das Quirkblatt
Frage 2: Ist die Zahl kleiner oder gleich 250?
Plopp, Glitter, neues Blatt.
Die gesuchte Zahl ist kleiner oder gleich 250. Ihr dürft noch maximal 8 Ja-Nein-Fragen stellen, um sie zu finden.
Frage 3:
Na, jetzt haben wir einen Plan, wie wir weiter vorgehen können. Mit unseren Fragen halbieren wir möglichst jedes Mal die Anzahl der Möglich-keiten. Mehr können wir bei Ja-Nein-Fragen ja wohl auch nicht erhoffen.
Frage 3: Ist die Zahl kleiner oder gleich 125?
Plopp, Glitter, neues Blatt.
Die gesuchte Zahl ist größer als 125. Ihr dürft noch maximal 7 Ja-Nein-Fragen stel-len, um sie zu finden.
Frage 4:
Gut. Die gesuchte Zahl ist also eine der 125 Zahlen zwischen 126 und 250. Puh. Wo ist denn da jetzt die Mitte, die wir zum aufteilen benötigen? Achja! Das ist doch genau so, als wenn man den Notendurchschnitt in der Schule ausrechnet, oder?!
(126+250):2 = 188
Unsere zwei Teile sind sind diesmal nicht gleich groß:
• die 63 Zahlen von 126 bis 188 und
• die 62 Zahlen von 188 bis 250.
Wir schreiben also:
Frage 4: Ist die Zahl kleiner oder gleich 188?
Ja. Also liegt die gesuchte Zahl zwischen 126 und 188.
Frage 5: Ist die Zahl kleiner oder gleich 157?
Nein. Demnach liegt die gesuchte Zahl zwi-schen 158 und 188.
Frage 6: Ist die Zahl kleiner oder gleich 173?
Ja. Verbleiben die 16 Zahlen zwischen 158 und 173. Jetzt wird es etwas komplizierter:
(158+173):2 = 165,5
Das ist keine ganze Zahl. Sollen wir nun 165 oder 166 zum aufteilen verwenden, damit die beiden Teile möglichst gleich groß sind? Puh. Ob wir aufrunden oder abrunden sollten, lässt sich hier aber glücklicherweise schnell herausfinden. Wir zählen einfach mal! Es liegen 16 Zahlen zwischen 158 und 173. Jeder Haufen sollte also nach Aufteilung 8 Zahlen enthalten, also:
• die 8 Zahlen von 158 bis 165 und
• die 8 Zahlen von 166 bis 173.
Demnach sollten wir abrunden.
Frage 7: Ist die Zahl kleiner oder gleich 165?
Nein. Verbleiben die 8 Zahlen zwischen 166 und 173.
Frage 8: Ist die Zahl kleiner oder gleich 169?
Ja. Damit sind nur noch 4 Zahlen übrig: 166, 167, 168 und 169.
Frage 9: Ist die Zahl kleiner oder gleich 167?
Ja. Nur noch 2 Zahlen übrig: 166 und 167.
Frage 10: Ist die Zahl kleiner oder gleich 166?
Nein. Also muss es die 167 sein!
Antwort: Die gesuchte Zahl ist 167.
Plopp. Und ganz viel bunter Glitzer. Und wir genießen unsere letzten Stücke Schokokuchen und den leckeren Kakao.
Ganz liebe Grüße,
Deine 3,7
PS: Angeblich kennen Mathematiker diese Halbierungsidee schon. Sie nennen diese Suchstrategie binäre Suche, wobei das „binär“ wohl vom lateinischen „bini“ für „je zwei“ kommt.
