Die Erdős-Zahl

Das Problem der letzten Woche wurde auf sehr raffinierte Weise von einer Leserin gelöst, die ihren Kommentar leider später wieder gelöscht hat. Sehen wir uns an, wie die ungarischen Mathematiker Paul Erdős und Georges Szekeres, regelmäßige Mitarbeiter und Co-Autoren des Erdős-Szekeres-Theorems , es seinerzeit angegangen sind. Sie gingen vom Schubfachprinzip aus und dachten daran, die Menge der ersten 2n Zahlen {1, 2, …, 2n} in n Teilmengen aufzuteilen, sodass – wenn man n + 1 Zahlen aus der ursprünglichen Menge nimmt – mindestens zwei davon in derselben Teilmenge liegen. Wären diese Teilmengen also so beschaffen, dass für zwei beliebige Zahlen in derselben Teilmenge eine ein Vielfaches der anderen wäre, wäre die ursprüngliche Aussage bewiesen.

Zu diesem Zweck werden die n Teilmengen als Schnittmengen der Menge {1, 2, …, 2n} mit den folgenden Mengen definiert: {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, wobei jedes Element das nächste seiner Teilmenge teilt und zudem jede Zahl in der ursprünglichen Menge {1, 2, …, 2n} eindeutig als (2m-1) x 2ᴷ geschrieben werden kann, also zu einer dieser Mengen gehört. Eine etwas komplexe Erklärung, die Bretos Bursó wie folgt zusammenfasst:

Jede natürliche Zahl ist das Produkt eines geraden und eines ungeraden Teils (das Produkt ihrer Primfaktoren ist 2 und das ihrer ungeraden Primfaktoren). Haben zwei verschiedene Zahlen den gleichen ungeraden Teil, so ist eine von ihnen ein Vielfaches der anderen (die Zahl, die öfter durch 2 teilbar ist als die andere, ist ein Vielfaches der anderen). Die n + 1 Zahlen, die wir betrachten, haben n mögliche ungerade Teile (1, 3, 5..., 2n-1), also gibt es mindestens zwei mit dem gleichen ungeraden Teil.

Und wenn man von Erdős und der Zusammenarbeit zwischen Mathematikern spricht, darf die Erdős-Zahl nicht fehlen. Der produktive ungarische Mathematiker hatte nicht weniger als 509 direkte Mitarbeiter, deren Erdős-Zahl (nE) 1 ist; diejenigen, die mit einem dieser 509 Mitarbeiter zusammenarbeiteten, aber nicht direkt mit Erdős, haben eine nE von 2 (das sind mehr als sechstausend) und so weiter.

Was könnte Ihrer Meinung nach Ihre Erdős-Zahl sein, wenn Sie eine Ferm-Schätzung verwenden? Ich würde mich mit einer vernünftigen Näherung zufrieden geben. (Tipp: Wenn Sie diesen Abschnitt regelmäßig lesen, wird es viel einfacher.)

Die Erdős-Szekeres-Vermutung

Der oben erwähnte Satz von Erdős-Szekeres darf nicht mit der gleichnamigen Vermutung verwechselt werden.

Der Satz besagt, dass für jedes Paar natürlicher Zahlen (ganzzahlige und positive) r und s jede Folge mit einer Länge gleich oder größer als (r-1)(s-1) + 1 eine monoton zunehmende Teilfolge der Länge s oder eine monoton abnehmende Teilfolge der Länge r enthält.

Es klingt kompliziert, aber ein einfaches Beispiel verdeutlicht das Konzept: Für r = 3 und s = 2, also (r-1)(s-1) + 1 = 3, hat jede Permutation dreier Zahlen entweder eine aufsteigende Teilfolge der Länge drei oder eine absteigende Teilfolge der Länge zwei. Betrachten wir die sechs möglichen Permutationen der Zahlen 1, 2 und 3 (und schreiben wir die Folgen vereinfacht):

• 123 hat eine zunehmende Teilfolge der Länge drei in sich: 123
• 132 hat eine abnehmende Teilfolge der Länge zwei: 32
• 213 hat eine abnehmende Teilfolge der Länge zwei: 21
• 231 hat zwei abnehmende Teilfolgen der Länge zwei: 21 und 31
• 312 hat zwei abnehmende Teilfolgen der Länge zwei: 31 und 32
• 321 hat drei abnehmende Teilfolgen der Länge zwei: 32, 31 und 21

Wie würden Sie den Beweis dieses Theorems anhand des Schubfachprinzips angehen? (Ich verlange keinen strengen Beweis, sondern nur einen Angriffsplan.)

Die Erdős-Szekeres-Vermutung ist eine Verallgemeinerung des „Happy-End-Problems“, das Erdős so nannte, weil es zur Heirat seines Freundes und Mitarbeiters Georges Szekeres mit der australischen Mathematikerin Esther Klein führte. Aber das ist ein anderer Artikel.