Ich liebe Mathematikrätsel! Ich liebe es zu knobeln, eine Lösung zu suchen und dann das schöne Gefühl, das Rätsel gelöst und die Aufgabe gänzlich verstanden zu haben.

Wenn auch du solche Knobeleien magst oder dich mal an in neues Gebiet wagen möchtest (wer weiss, vielleicht findest du ja auch grossen Gefallen daran!), habe ich hier ein kleines Rätsel für dich. Ich werde zunächst die Lösung noch nicht publizieren, um dir Zeit zu geben, selbst darauf zu kommen oder zumindest die ersten Schritte selbst zu finden.

Die Dracheninsel

Auf einer Insel leben Drachen, wobei es solche mit blauen und solche mit roten Augen gibt. Keiner der Drachen kennt seine eigene Augenfarbe und es gibt auch keine Möglichkeit, sie zu erkennen (Drachen schauen grundsätzlich in keine Spiegel oder Wasserpfützen). Es gibt nun zwei Regeln:

1. Wenn ein rotäugiger Drache erfährt, dass er rote Augen hat, muss er in der darauffolgenden Nacht auf das Festland auswandern.
2. Die Drachen sprechen nie über Augenfarben. Es wäre ein schreckliches Verbrechen, einem Mit-Drachen seine Augenfarbe zu verraten (ein rotäugiger Drache müsste ja dann die Insel verlassen).

Der verhängnisvolle Besuch

Eines Tages kommt ein Forscher auf die Insel. Die Drachen sehen das Forschungsschiff schon von Weitem kommen und versammeln sich alle ausnahmslos in der Bucht, um den Besucher willkommen zu heissen. Als das Schiff in der Bucht einläuft und der Forscher die Drachen versammelt sieht, ruft er entzückt aus “Oh! Hier gibt es rotäugige Drachen!”. Da alle Drachen versammelt sind, hören alle diesen Ausruf.

Obwohl er keinem der Drachen persönlich gesagt hat, er habe rote Augen, wandern einige Zeit später alle rotäugigen Drachen auf das Festland aus.

Warum?

Tipp

Überlege dir zunächst, was passiert, wenn nur ein rotäugiger Drache auf der Insel lebt. Wie sieht das Szenario aus mit zwei rotäugigen Drachen? Wie mit drei?

Lösung

Die Aufgabe lässt sich mittels einer Beweismethode lösen, die sich vollständige Induktion nennt.

Vollständige Induktion

Bei der vollständigen Induktion geht es darum, dass etwas für alle natürlichen Zahlen (1,2,3,…) wahr sein muss, wenn es für 1 wahr ist und sich Folgendes zeigen lässt: Ist die Aussage für eine beliebige natürliche Zahl n wahr, dann ist es auch für die darauf folgende Zahl n+1 wahr.

Warum gilt die Aussage dann für ALLE natürlichen Zahlen? Weil wir konkret gezeigt haben, dass es für 1 gilt. Und weil es dann auch für die darauf folgende Zahl gilt, also für 2. Und dann für die darauf folgende, also 3. Und deshalb für 4, für 5, 6, 7, usw.

Die beiden Teile der vollständigen Induktion werden Induktionsverankerung (zeigen, dass es für 1 gilt) und Induktionsschritt (zeigen, dass es für n+1 gilt, wenn es für n gilt) genannt.

Beispiel

Für interessierte Leser zeige ich hier ein Beispiel, wie vollständige Induktion in der Mathematik verwendet wird. Machen dir die Formeln Angst, kannst du diesen Abschnitt auch einfach überspringen (oder du nutzt die Gelegenheit, die deiner Angst zu stellen und liest ihn dennoch durch :oP ).

Das klassische Beispiel ist die Formel für den Wert der Summe aller Zahlen von 1 bis n.

Die Formel lautet so: 1+2+3+…+(n-1)+n = n*(n+1) / 2

Die Summe aller natürlichen Zahlen von 1 bis 7 etwa ist, weil n=7 ist,
7*(7+1) / 2 = 7*8/2 = 28.

Um zu zeigen, dass diese Formel für jedes n gilt, benutzen wir vollständige Induktion.

Induktionsverankerung:
Zunächst zeigen wir mit der Induktionsverankerung, dass die Formel für n=1 gilt.

Die Summe aller Zahlen von 1 bis 1 ist natürlich einfach 1. Setzen wir n=1 in die Formel ein, so erhalten wir 1*(1+1)/2 = 2/2 = 1. Das heisst, wir erhalten 1=1, was korrekt ist.

Wir können auch noch weiter gehen und zeigen, dass die Formel für n=2 immer noch stimmt.

1+2 = 3 erhalten wir beim Summieren und mit der Formel 2*(2+1)/2 = 2*3/2 = 3, stimmt also auch.

Induktionsschritt:
Nun zum spannenden Teil des Beweises. Nehmen wir an, die Formel gilt für ein beliebiges n. Jetzt müssen wir zeigen, dass es auch für n+1 gilt.

Wir sind also interessiert an der Summe aller Zahlen von 1 bis n+1, wobei wir die Summe aller Zahlen von 1 bis n kennen. Schreiben wir nun

1+2+3+…+n+(n+1),

so wissen wir, dass die Formel für 1+2+3+…+n gilt und können sie insetzen. Wir erhalten also

n*(n+1)/2 + (n+1) (nennen wir diesen Term X).

Das Ziel ist nun, diesen Term so umzuformen, dass am Schluss die Formel für n+1 rauskommt, nämlich

(n+1)*((n+1)+1)/2 = (n+1)*(n+2)/2.

Starten wir bei dieser Zielformel und multiplizieren die rechte Klammer (n+2) aus:

(n+1)*(n+2)/2 = ((n+1)*n + (n+1)*2) / 2

Diesen Bruch können wir aufteilen in zwei Summanden, wobei jeder Bruch den Teiler erbt

= (n+1)*n / 2 + (n+1)*2 / 2

Der rechte Summand lässt sich mit 2 kürzen, wobei dann nur noch n+1 übrig bleibt. Also

= (n+1)*n / 2 + (n+1).

Ein Blick auf obigen Term X zeigt uns, dass wir genau das erhalten haben, was wir wollten. Somit ist die Formel bewiesen!

Lösung: Vollständige Induktion für das Rätsel

Das Rätsel der Dracheninsel lässt sich mit vollständiger Induktion lösen. Falls du die Lösung noch nicht selbst gefunden hast, kannst du es jetzt nochmals selbst mit vollständiger Induktion versuchen!

Für alle anderen, die die Lösung nun gerne lesen möchten – voilà:

Was wollen wir überhaupt zeigen? Die Behauptung ist folgende: Wenn eine gewisse Anzahl n rotäugiger Drachen auf der Insel lebt und alle Drachen wissen, dass es mindestens einen rotäugigen Drachen gibt (daraus folgt sofort, dass n mindestens 1 sein muss), so werden alle Drachen mit roten Augen auswandern müssen.

Beginnen wir also mit dem Induktionsschritt: n=1, es lebt also nur ein Drache mit roten Augen auf der Insel. Wir wollen nun zeigen, dass er durch den Forscher erfährt, dass er selbst rote Augen hat und deshalb auswandern muss. Bevor der Forscher auf die Insel kommt, kennt er seine Augenfarbe nicht. Er kennt nur diejenige aller anderen Drachen, da er diese ja sieht. Weil er der einzige Drache mit roten Augen ist, sieht er bei allen anderen Drachen nur blaue Augen.

Nachdem der Forscher gesagt hat, es gäbe Drachen mit roten Augen auf der Insel, gibt es für ihn nur eine einzige Schlussfolgerung: Er selbst muss dieser Drache sein, denn die anderen haben ja blaue Augen. Er wandert also in der darauffolgenden Nacht aus.

Um besser zu verstehen, warum der Induktionsschritt funktionieren wird, zeige ich hier noch auf, was mit zwei rotäugigen Drachen passiert (n=2).

Beide Drachen wissen, dass es rotäugige Drachen auf der Insel gibt, denn sie sehen ja ihren Kollegen mit den roten Augen. Sie wissen aber nicht, dass sie selbst auch rote Augen haben. Aus der Sicht eines dieser Drachen könnte es auch einfach einen rotäugigen Drachen geben.

Nachdem der Forscher seine folgenschwere Bemerkung gemacht hat, denkt sich jeder der beiden rotäugigen Drachen: „Der arme Kollege, er muss in der nächsten Nacht auswandern!“

Was passiert aber in dieser Nacht? Nichts! Denn jeder der beiden Drachen geht davon aus, dass der andere Drache auswandern muss und nicht er selbst (denn er weiss ja nicht, welche Augenfarbe er selbst hat). Als am nächsten Morgen noch alle Drachen da sind, also alle blauäugigen Drachen, der eine Kollege mit den roten Augen und man selbst, gibt es wieder nur eine Schlussfolgerung: „Wenn der rotäugige Kollege nicht ausgewandert ist, heisst das, dass er sich nicht sofort selbst angesprochen fühlte, weil er einen anderen Drachen mit roten Augen sieht. Also muss ich selbst rote Augen haben!“ Nun wissen beide Drachen von sich selbst, dass sie rote Augen haben und wandern in der nächsten Nacht zusammen aus.

Was ist bei drei Drachen (n=3)? Genau, jeder der Drachen mit roten Augen sieht die beiden anderen rotäugigen Drachen und denkt sich, dass sie nach der ersten Nacht gemerkt haben werden, dass es zwei Drachen sind und nicht einer und sie auswandern müssen. Als die beiden nach der zweiten Nacht noch da sind, wird jedem dieser drei Drachen klar, dass er also auch selbst rote Augen haben müssen. Zu dritt wandern sie in der dritten Nacht aus.

Induktionsschritt:
Nun sind wir bereit für den Induktionsschritt. Bei n+1 rotäugigen Drachen erwartet jeder dieser Drachen, nach oben erklärtem Schema, dass nach n Nächten jeder seiner n rotäugigen Kollegen gemerkt haben muss, dass er selbst rote Augen hat und sie dann auswandern müssen. Doch weil das eben jeder dieser Drachen denkt, sind sie alle nach n Nächten noch da – und schliessen daraus, dass sie selbst auch rote Augen haben müssen. Nach n+1 Nächten also wandern sie alle gemeinsam aus.

Schlusswort

Mathematisch, hoffe ich, ist nun alles klar. Wie sieht es aber mit der Intuition aus? Schwierig, nicht wahr? Wir haben es da mit einer philosophischen Frage zu tun. Denn ab zwei Drachen mit roten Augen weiss ja jeder Drache auf der Insel, dass es Drachen mit roten Augen gibt. Was ändert sich also mit der Bemerkung des Forschers? Man könnte meinen, nichts! Doch offensichtlich ist dem nicht so. Denn was neu ist, ist das Wissen, dass es alle wissen und das Wissen, dass alle wissen, dass es alle wissen usw.

Jeder der Drachen weiss nun, dass es alle wissen. Hat einer rote Augen, so wartet er darauf, dass seine rotäugigen Kollegen nach n Schritten selbst wissen, dass sie rote Augen haben. Passiert nichts, so weiss er, dass er selbst auch auswandern muss. Vor dem Besuch des Forschers wussten zwar alle, dass auf der Insel Drachen mit roten Augen leben, doch sie alle konnten getrost im Glauben leben, selbst blaue Augen zu haben. Keiner der Drachen hat erwartet, dass etwas passieren muss, weshalb es auch keinen Moment geben konnte, an dem er bemerkt hatte, dass das Erwartete nicht passiert ist. Deshalb hat sich keinem von ihnen seine Augenfarbe offenbart und sie konnten alle gemeinsam auf der Insel leben.