Können wir vier Blätter in die Mitte geben? Dann würden immerhin noch drei Blätter für die Außenpunkte übrig bleiben. Aber wir wissen, dass jeder Außenpunkt zwei Blätter benötigt – mindestens! Das geht sich nicht aus – wir können also nicht mehr drei Blätter an den mittleren Stammpunkt hängen.

Würden wir jetzt fortfahren, dann würde uns ein Baum mit Dreierkette entgehen! Wie kann das denn sein? Sehen wir uns noch einmal den vorigen Baum (Verteilung 2 und 3 und 2) an: Die 3 Punkte am mittleren Stammpunkt verwenden wir allesamt als Blätter. Es spräche aber nichts dagegen, nur einen der Punkte direkt an den Stammpunkt anzuschließen (im Bild unten habe ich ihn grau dargestellt) und ihm dann die zwei bleibenden Blätter anzuhängen. Auf diese Weise erhalten wir schließlich unseren neunten (zugegeben recht schwierig zu findenden) Baum.

Keine Frage, wie es jetzt weitergeht: Eine Viererkette bildet den Stamm, daher gibt es diesmal zwei äußere und zwei innere Stammpunkte. Da jeder äußere Stammpunkt mindestens zwei Blätter benötigt und jeder innere mindestens einen, geht es sich exakt aus mit unseren sechs Blättern. Es gibt also nur eine Möglichkeit – (2 und 1 und 1 und 2) – und die ist nicht wirklich verzwickt zu finden. Damit sind es schon 10 Bäume:

Bäume mit Dreier- oder Vierer-Kette

Bäume mit Dreier- oder Vierer-Kette

Was passiert, wenn unsere Stammkette aus noch mehr als nur vier Punkten besteht? Probieren wir es einfach einmal mit fünf aus: In dem Fall gibt es zwei äußere und drei innere Stammpunkte, was bedeutet: Wir benötigen sieben Blätter. Die haben wir aber nicht – uns bleiben ja nur mehr fünf Stück übrig. Mit noch längeren Stammketten brauchen wir es dann gar nicht erst versuchen: Es bleibt also bei unseren 10 nicht-isomorphen, homöomorph irreduziblen Bäumen vom Grad 10. (Anmerkung: Es ist Zufall, dass es genau 10 Bäume vom Grad 10 gibt. Es existieren beispielsweise 5 solche Bäume vom Grad 9 und 14 Bäume vom Grad 11.)

Bleiben wir aber realistisch: Echte MIT-Professoren hätten dieses Rätsel mit Sicherheit noch schneller gelöst als wir gerade eben. Daniel Kleitman, der mathematische Berater des Films, hat sich da offensichtlich einen Spaß mit seinem Publikum erlaubt. Die Figuren, die Will an die Tafel kritzelt, wirken eindrucksvoll und komplex und lassen das Publikum darum an den teuflischen Schwierigkeitsgrad der Aufgabe glauben.

Uns wird also ein leichtes Rätsel als äußerst schwer verkauft. Aber mal ehrlich: Es war die einzige Möglichkeit! Wie viele mathematische Rätsel gibt es denn, an denen MIT-Professoren zwei Jahre lang zu knabbern hätten, die sich aber recht anschaulich auf einer Gangtafel lösen lassen? Wenn es überhaupt solche Rätsel gibt – ich bezweifle es – dann sind sie unglaublich schwer zu finden.

Jedenfalls ist es ein hochinteressantes Thema, das uns „Good Will Hunting“ näherbringt. Einerseits haben wir so die Graphentheorie kennengelernt – ein Teilgebiet der Mathematik, dem wir jeden Tag begegnen, auch wenn wir es nicht unbedingt merken: Jede Straßenkarte, jeder U-Bahn-Plan basiert auf den Ideen, die Leonard Euler schon vor rund 300 Jahren hatte. Und andererseits haben wir dieses Rätsel gelöst – ein Rätsel für Jedermann und für überall, wo man Zettel und Stift zur Hand hat. Einem Phänomen, das in der Mathematik generell häufig ist, begegnet man auch hier: Nur weil etwas wahnsinnig kompliziert klingt, heißt das nicht, dass es sich nicht doch als einfach herausstellen kann.

Wen jetzt jedenfalls die Begeisterung übermannt hat, kann die nächsten Hürden auf sich nehmen: Grad 11, Grad 12, etc. Wer aber die infernale Herausforderung sucht, kann sich dem Grad 3 widmen. Warum? – Sehen Sie selbst!

1 / 2 / 3 / 4

Kommentare (26)

  1. #1 CM
    26. September 2014

    Habe mich sehr amüsiert – schön geschrieben! Und ich habe mich daran erinnert gefühlt:

  2. #2 Lisa Leander
    26. September 2014

    Ich mag den Film sehr gern und erinnere mich gut an die Szene mit den vielen “Böbbels” (Blättern) an der Tafel. Toll zu erfahren, was dahinter steckt, und dass es eigentlich so einfach ist! Vielleicht sollte es ein Insider-Witz für Mathematiker sein 😉

  3. #3 Dampier
    26. September 2014

    Schöner Artikel! Wie spannend Mathematik sein kann, habe ich erst spät durch solche gelungenen Populärwissenschaftlichen Darstellungen erfahren, in der Schule hat mich das völlig überfordert. Aber vielleicht hatte ich damals einfach andere Dinge im Kopf 😉

    Nun ja, Mathematiker werde ich in diesem Leben nicht mehr, aber ich freue mich immer über so spannende Enblicke.

    Kleiner Kritikpunkt: die farbigen Punkte sind praktisch nicht zu erkennen, das sieht alles schwarz aus. Die Erklärung funktioniert aber trotzdem.

    Den Film fand ich eher langweilig.

    grz
    Dampier

  4. #4 Alderamin
    26. September 2014

    Ich finde den Artikel auch so gut wie perfekt. Unterhaltsam geschrieben, was zum Mitdenken, Bilder sind dabei. Einer meiner Favoriten (deren es fünfe gibt).

  5. #5 Florian Freistetter
    26. September 2014

    Der Artikel gefällt mir auch sehr gut! Stellenweise hätte ich mir ein klein wenig mehr Ausführlichkeit gewünscht. Aber bei so einem abstrakten Thema ist es immer schwer und die allgemeinverständliche Umsetzung ist hier mehr als gut gelungen!

  6. #6 Paul Busse
    26. September 2014

    Ein sehr guter Artikel. Als Elektrotechniker bin ich schon etwas mit Graphentheorie in Kontakt gekommen, auch wenn Bäume bei uns eher selten vorkommen, weil da kein Strom fließt. Aber auch ohne mein Vorwissen denke ich wäre der Artikel verständlich gewesen. Ein interessantes und komplexes Thema wurde hier sehr gut erklärt.

    Was die abschließende Frage angeht. Ein Baum vom Grad 3 mit den genannten Eigenschaften kann nicht existieren, oder? Die 3 Punkte liegen immer in einer Reihe, wobei der mittlere Knoten den Grad 2 hat und damit homöomorph reduzibel wäre. Richtig?

  7. #7 Bullet
    26. September 2014

    … und die einzige Methode, die Reduzibilizierbarkeit aufzuheben, wäre die Kreis- (na ja, eher die Dreieck-)struktur. Hilft auch nich … 🙁

  8. #8 Lukas Prader
    26. September 2014

    Vielen Dank für die vielen Rückmeldungen! Ehrlich gesagt hätte ich nicht gedacht, dass jemand den Artikel zu Ende liest, so lang wie der ist …

    @CM: Ja, das Video kannte ich, und ehrlich gesagt bin ich genau so auf dieses Thema gekommen. 😉

    @Lisa Leander: Ich glaube auch, dass es ein Insider-Witz ist. Bei den Simpsons kommen solche Witze auch sehr oft vor (Simon Singh hat dazu ein ganz gelungenes Buch geschrieben.

    @Dampier: Ja, ich muss gestehen, die Punkte sind wirklich schlecht unterscheidbar. Ich wollte eher “langweilige” Farben nehmen, damit es nicht so grell wirkt, was nun aber zur schlechten Sichtbarkeit geführt hat.

    @Alderamin/Florian Freistetter: Danke für das Lob! 🙂 Mein Ziel war es eben, dieses so gut wie unbekannte Thema interessant zu verkaufen. Wenn das ein Mathematiker liest, wird er es sicherlich auf zu kitschig/ungenau finden, aber es soll ja auch keine Forschungsarbeit sein.

    @Paul Busse/Bullet: Es freut mich sehr, dass Sie sich darüber Gedanken gemacht haben: Tatsächlich gibt es keinen solchen Baum vom Grad 3. Entweder hätte man sonst einen Kreis (kein Baum –> verboten), oder man hätte einen Punkt mit genau zwei Verbindungen, was ja auch verboten ist. 😉

  9. #9 Fliegenschubser
    26. September 2014

    Ein sehr guter Artikel!

  10. #10 Chaaron
    26. September 2014

    Der Artikel ist sehr interessant und verständlich geschrieben. Selbst ich habe das kapiert, aber in einer Klausur gäbe es trotz richtiger Lösung nicht die tolle Punktzahl…
    Leider genügt es den Mathematikern nicht, wenn man etwas aufmalt.
    Die Frage ist: wie berechnet man das Ganze?

  11. #11 Chaaron
    26. September 2014

    Öhm, ich meine natürlich die volle Punktzahl, auch wenn diese dann toll ist…

  12. #12 Realistischer
    26. September 2014

    Um auch was kritisches anzumerken: die 2 angegebenen Regeln für Graphen, dass alle Punkte zusammenhängen müssen und sich keine Linien überkreuzen dürfen — das gilt nicht für Graphen allgemein sondern beschreibt den Spezialfall der zusammenhängenden planaren Graphen.

  13. #13 Lukas Prader
    26. September 2014

    @Fliegenschubser/Chaaron: Vielen Dank für das Lob! Tatsächlich gibt es (wie für das meiste in der Mathematik) eine Formel, mit der man die Anzahl der Bäume berechnen kann.
    [siehe dazu: https://amininima.wordpress.com/2013/05/12/not-that-good-will-hunting/ ]

    @Realistischer: Vielen Dank für die Korrektur, das war mir nicht bekannt. In diesem Rahmen habe ich “Graph” quasi als Vereinfachung für die von Ihnen genannten “zusammenhängenden planaren Graphen” genannt.

  14. #14 DerMannMitHut
    26. September 2014

    @Chaaron: Ich würde in einer Klausur die volle Punktzahl geben. Denn es ist auch ein gültiger mathematischer Beweis, wenn man offensichtlich alle Möglichkeiten durchgeht und zeigt, warum es keine weiteren Möglichkeiten geben kann.

    Dafür braucht man keine Formel. Formeln werden in der Mathematik zwar gerne verwendet, aber nur um komplizierte Sachverhalte einfach und kompakt darzustellen (auch wenn das für den Laien oft anders wirkt).

  15. #15 rolak
    26. September 2014

    Ich nehme an, Sie haben bereits alles verstanden

    Auch noch ein Hellseher… 😛

    Ein großer Dom

    Der Königsberger Dom. Mit Kants Grab. Eine der (für mich) Muß-Anlaufstellen in der viel zu schmal bemessenen Freizeit in dem einwöchigen Aufenthalt damals ’97. Vier Verwandte mit angeheuertem Kleinbus auf den Spuren der Vorfahren im Umland. Versunken im Übungsgebiet (geschickt am 1.Mai besucht..) – sowohl das Bauernhöfli, fast alles vom nahegelegenen Dorf und auch fast ich. In einer harmlosen Panzerspur-Pfütze, die sich als oberste Schicht einer anderthalb Meter tiefen Schlammkuhle entpuppte. Amüsierte die Mitreisenden königsberglich – schwupps, sackt er weg, schwupps, steigen die Arme mit Brieftasche und Kamera zum Himmel 😉

    Achten wir auf den grünen Punkt!

    Der so ungemein geschickt getarnt ist…

    grau dargestellt

    den würde ich ohne Kontext nur mit Farbwert-Analyse finden.

    Bei der Programmierung haben wir es ja mehr mit den Gärtnern zu tun – Bäume hegen und pflegen, Neues dazugesellen, bei Bedarf beschneiden, Reste entsorgen. Unabhängig davon ist der Artikel flott geschrieben, Interesse weckend und die Problematik umfassend beschreibend.

  16. #16 Lukas Prader
    26. September 2014

    @rolak: Vielen Dank für das humorvolle Feedback und die Anekdote! Ja, die Farbwahl bei den Punkten ist ungünstig gewählt. Wenn man auf die Bilder klickt, erhält man eine vergrößerte Ansicht – und da sind (zumindest meiner Meinung nach) die Farben besser unterscheidbar.

  17. #17 PDP10
    26. September 2014

    @Lukas Prader:

    “und da sind (zumindest meiner Meinung nach) die Farben besser unterscheidbar.”

    Ähm … naja … auf meinem Laptop-Display Grau und nicht-ganz-grau-irgendwie-blau … 🙂

    Aber ansonsten: wirklich schöner Artikel!

    Ich liebe dieses Graphentheorie Zeugs (auch wenn ich bei den richtig abstrakten Untiefen total passen musste), weil man da mit ein paar Zeichnungen wunderschön komplexe Sachverhalte erklären kann.

    Und das hast du hier ziemlich gut gemacht.

  18. #18 rolak
    26. September 2014

    auf die Bilder klickt

    Mit kleinem Finger ganz links unten im Barré, also ctrl-shift. Dann gehts (nur hier?) in einem neuen Tab auf, der auch den Fokus bekommt, ohne daß ich den Kontext (Text) aus dem direkten Zugriff verliere.

    Beide Punkte sind ja auch im Text beschriebenen und eindeutig identifizierbar – doch beim grünene vermeine ich nur nach intensivem Starren einen Unterschied auszumachen, nicht festhaltbar. Bei der gößeren Variante wars eindeutig. Beim Anderen half nicht einmal das.. kann klarerweise auch an der aktuellen Brillen-Monitor-Kombi liegen. Kleiner Check: Putzen bringt nix. Immer noch sehe ich verschiedene Variationen von Anthrazit herumtanzen. Und zwar mehr als zwei, nicht sehr hilfreich – vielleicht hast Du ja ne schöne neue optische Täuschung gebastelt.

  19. #19 Lukas Prader
    26. September 2014

    @PDP10: Vielen Dank für das Lob! Beim Verfassen hat mich selbst überrascht, wie praktisch und vor allem wie lebensnah die abstrakte Graphentheorie sein kann. Aber das ist ja das Tolle an Mathematik: Sehr viele Menschen haben Angst vor ihr (das lernen sie in der Schule), obwohl sie unser Freund und Helfer ist – keineswegs unser Feind.

  20. #20 Peroppi
    27. September 2014

    Ein echt schöner Artikel. Hab ihn spontan komplett durchgelesen obwohl ich eigentlich gar keine Zeit hatte 😀

    Ich mag den Stil, die Dinge zu erklären, sehr natürlich trotz aller Lockerheit gut strukturiert. Was Graphen sind, war mir klar, aber diese Aufgabe und auch die speziellen Attribute kannte ich nicht. Mit der Erklärung habe ich alles sofort verstanden, obwohl ich auch nur schwarze Punkte gesehen hab 😉 Interessant, jetzt als ich die Kommentare überflogen habe ist mir aufgefallen dass da ja doch blaue, graue und grüne sind – aber nur wenn ich schräg auf mein Laptopdisplay schaue.

  21. #21 Chemiker
    27. September 2014

    Ganz großes Plus! Richtig gut geschrieben und verständlich, auch ohne daß man den Film gesehen hat.

  22. #22 Lukas Prader
    27. September 2014

    @Peroppi/Chemiker: Vielen Dank für das Lob! Jetzt habe ich mir das mit den Punkten noch einmal bewusst angeschaut und tatsächlich: Wenn man den Bildschirm weit nach hinten klappt, sieht man nur schwarze Punkte. Deswegen ist es mir wohl nicht aufgefallen, ich habe ihn viel schräger nach vorne.
    Und ich glaube gar nicht wirklich, dass der Film notwendige “Vorkenntnis” für den Artikel ist. Es geht ja vor allem um das Rätsel und weniger um die Handlung.

  23. #23 Pterry
    27. September 2014

    schöner Artkel. ich habe nach dem Lesen heute darüber nachgedacht, wo sowas Anwendungen finden könnte. mit dem U-Bahn-Plan-Beispiel hatte ich das Problem, dass da ja auch “Punkte” also Stationen wegfallen, wenn da keine andere Linien schneiden. Und ich bin beim Nachdenken bei Twitter (und dann bei Mindmaps) gelandet: ich fände es sehr interessant, Tweets und ihre Replies mal von der oben-unten-Reihenfolge weg darzustellen (seitlich z.B.). Da können bestimmt auch schöne Bäume wachsen 🙂

  24. #24 Lukas Prader
    27. September 2014

    @Pterry: Das mit dem “Punkte wegfallen” (bzw. dass sie homöomorph irreduzibel sein müssen) gilt ja nicht für alle Graphen, sondern hier nur für die Bäume im Rätsel.
    U-Bahn-Pläne und alle anderen Pläne von Verkehrsmitteln sind also schon Anwendungen von Graphen. Mindmaps auch, klar. Jede Hierarchie (z.B. Position der Arbeiter in einer Firma, die Einteilung der Zahlenmengen), oder allgemein jeder Plan (z.B. wie der Briefträger jeden Tag geht) ist eine Anwendung von Graphen.

  25. #25 Michael
    Hamburg
    28. September 2014

    Toller Artikel, und: Nein: Auch ich, als Mathematiker fand ihn weder “kitschig” noch “ungenau”.
    Daher Danke, vor allem auch für den Schluss!

  26. #26 Lukas Prader
    30. September 2014

    @Michael: Vielen Dank für das Lob! Das freut mich natürlich besonders, wenn er sogar bei Mathematikern gut ankommt.