Warum Mathematik glücklich macht: 151 verblüffende Geschichten (German Edition)

verformelte Redeweise ist es aber zugegebenermaßen, mit geringen Wertungen für Verständlichkeit und Amusement. Eine amüsantere Darstellung nehmen wir jetzt vor. Sie versucht sich mit metaphorischen Mitteln den Weg in die Köpfe des Publikums zu bahnen. Aus Gründen, die gleich klar werden, bezeichnen wir das Resultat als den Heiratssatz.
    Eva möchte natürlich Adam heiraten, Romeo seine Julia, Napoleon die Josephine und Barbie den Ken, obwohl sie auch gefallen an Hänsel findet. Auf den hat aber Gretel ein Auge geworfen. Allerdings: Gegen Ken hätte sie auch nichts und erst recht nicht gegen Romeo, aber Adam lässt sie kalt. Ein komplexes Gefüge von positiven und negativen Beziehungen mit vielen interessanten Fragen. Nur eine davon ist diese: Wenn in einer Gruppe von Frauen und Männern jede der Frauen eine gewisse Teilmenge der Männer als heiratsfähig einschätzt, unter welchen Bedingungen ist es dann möglich, dass eine jede von ihnen einen von ihr als heiratsfähig eingeschätzten Mann ehelichen kann?
    Das ist ein Zuordnungsproblem, von denen es in unserem Alltag sehr viele von exakt derselben Struktur gibt: Zuordnungen von Jobs mit bestimmten Anforderungen auf Jobsuchende mit bestimmten Qualifikationen. Zuordnungen von Hotels mit bestimmten Leistungsprofilen auf Urlauber mit bestimmten Ansprüchen usw. Eine wichtige Frage in Anwendungen lautet, wann vollständige Zuordnungen möglich sind. Diese Frage hat 1935 Philip Hall, damals noch Teil der Jungmathematiker-Avantgarde, mit obigem Satz beantwortet.
    Umgedeutet hat man es dabei mit dem folgenden Beziehungsgeflecht zu tun. Grundstrukturen sind eine Menge von Damen D und eine Menge von Herren H. Jeder Dame d, also jedem Element von D, ist eine Gruppe von Herren zugeordnet, also eine Teilmenge F(d) von H. Das sind die von der Dame d als heiratsfähig eingestuften Herren. Nennen wir die Zuordnung d → F(d) für alle Damen d aus der Menge D kurz Freundschaftssystem und speziell F(d) die Menge der Freunde der Dame d. Die Funktionen h von der Menge D in die Menge H nennen wir Heiratssysteme, speziell ist h(d) der Mann, den die Dame d heiratet. Heiratssysteme sind also Massenhochzeiten. Wir gehen dabei von Monogamie aus. Zwei verschiedene Damen können nicht denselben Herrn heiraten, zwei verschiedene Herren können nicht dieselbe Dame heiraten.
    Wir sagen ferner, das Heiratssystem h: D → H ist mit dem Freundschaftssystem F verträglich, wenn jede Dame einen ihrer Freunde heiraten kann. Verträglichkeit in dieser Sprachregelung erfordert, dass stets h(d) ein Element von der Menge F(d) ist. Außerdem sagen wir noch: Das Freundschaftssystem erfüllt die Party-Bedingung, wenn auf keiner von einigen Damen mit allen ihren Freunden veranstalteten Party Herrenmangel herrscht, d.h., es gibt stets mindestens so viele Männer wie Frauen auf der Party. Der freudianische Hauptinhalt der Party-Bedingung: Für alle möglichen m hat jede Gruppe von m Damen zusammengenommen mindestens m Freunde. Diese Sicht des Zuordnungsproblems als Heiratsszenario hat unschätzbare kognitive Vorteile.
    Held honoris causa. Unser Theorem-Sommelier Philip Hall hat bewiesen, dass es dann und nur dann ein mit dem Freundschaftssystem verträgliches Heiratssystem gibt, anders gesagt, eine vollständige Zuordnung, wenn die Party-Bedingung erfüllt ist.
    Wir versuchen zu verstehen, warum. Zunächst ist klar, dass die Party-Bedingung für eine vollständige Zuordnung eine conditio sine qua non darstellt. Doch wenn sie erfüllt ist, ist dies umgekehrt auch ausreichend?
    Der Beweis verläuft mit Induktion nach der Anzahl n der Frauen. Für den Fall n = 1 ist die Party-Bedingung offensichtlich ausreichend. Beim Induktionsschluss unterscheidet man zwei Fälle. Kennen je k Frauen für k von 1 bis n mindestens k + 1 Junggesellen, dann können wir als Zeremonienmeister ein beliebiges Paar verheiraten und die verbleibenden unverheirateten Frauen und Junggesellen erfüllen trotz des Fehlens eines Junggesellen nach wie vor die Party-Bedingung. Also können auch die verbleibenden k – 1 Frauen nach Voraussetzung mit k – 1 Junggesellen verheiratet werden. Dieser erste Schritt bringt uns ins Basislager für unsere Gipfelambitionen.
    Es folgt das zweite Teilstück des Aufstiegs zum Beweis. Gibt es andererseits eine Gruppe von k < n Frauen, die insgesamt nur genau k Junggesellen kennen, so lassen sich diese nach der Voraussetzung im Induktionsschluss verheiraten. Nun müssen die verbleibenden Frauen noch mit