Mathematik raffiniert Das Schubfachprinzip

Für manch schwieriges Problem haben Mathematiker eine elegante Lösung: das Schubfachprinzip. Auf den ersten Blick erscheint die Methode schlicht - doch zwei Beispiele zeigen, wie mächtig sie tatsächlich ist.

Schrank mit Schubfächern
Getty Images / iStockphoto

Schrank mit Schubfächern

Von


Der 1996 verstorbene ungarische Mathematiker Paul Erdös erzählte Kollegen immer wieder von einem Buch, in dem Gott die perfekten mathematischen Beweise gesammelt habe. Er sagte auch, man müsse sich nicht zu Gott bekennen, als Mathematiker solle man jedoch an die Existenz des Buches glauben.

Eine Beweistechnik, die laut Erdös unbedingt in das Buch aufgenommen werden sollte, ist das Schubfachprinzip. Der Ungar konnte das Buchprojekt selbst leider nicht umsetzen. Doch 1998 schließlich, zwei Jahre nach seinem Tod, veröffentlichten zwei Berliner Mathematiker, Martin Aigner und Günter Ziegler, die Sammlung schöner Beweise, von dem der Ungar immer gesprochen hatte.

Dem Schubfachprinzip widmen Aigner und Ziegler gleich mehrere Seiten im 1998 erstmals erschienenen "BUCH der Beweise". Die folgenden drei Beispiele illustrieren, wie die Methode funktioniert.

Haarige Berliner

Das erste Beispiel stammt nicht aus dem Buch von Aigner und Ziegler, sondern aus einer Knobelaufgabe, die auf SPIEGEL ONLINE als Rätsel der Woche erschienen ist

Beweisen Sie, dass es mindestens zwei Berliner gibt, die exakt gleich viele Haare auf dem Kopf haben.

Hinweis: Zwei Berliner mit Glatze sollen nicht als Lösung gelten. Gesucht sind Menschen, die tatsächlich Haare auf dem Kopf haben.

Für die Lösung brauchen wir nur zwei Zahlen zu kennen:

  • Wie viele Menschen leben etwa in Berlin? Es sind 3,5 Millionen.
  • Wie viele Haare hat ein Mensch auf dem Kopf? Eine Internetrecherche ergibt Werte von 100.000 bis 150.000 und als Obergrenze 200.000.

Würden in Berlin weniger als 200.000 Menschen leben, könnte theoretisch jeder eine andere Anzahl von Haaren haben - von 1 bis 200.000. Weil es aber mehr als drei Millionen Einwohner sind, muss es mindestens zwei Berliner mit identischer Haaranzahl geben (es gibt sogar noch einige mehr).

Das Haarbeispiel zeigt anschaulich, wie das Schubfachprinzip funktioniert: Wir wollen n Objekte über m Schubfächer verteilen. Wenn es mehr Objekte als Schubfächer gibt, also n > m gilt, muss es mindestens ein Schubfach existieren, in dem zwei Objekte liegen.

Im "BUCH der Beweise" finden sich mehrere schöne Beweise Eigenschaften natürlicher Zahlen, die das Schubfachprinzip nutzen. Zwei davon möchte ich hier vorstellen.

Kein gemeinsamer Teiler

Gegeben sind die natürlichen Zahlen von 1 bis 2n, wobei auch n eine natürliche Zahl > 0 ist. Wir wählen davon n+1 Zahlen zufällig aus. Dann muss es unter den n+1 Zahlen zwei geben, die keinen gemeinsamen Teiler haben.

Der Beweis dafür ist sehr einfach: Es muss unter den n+1 Zahlen zwei geben, die sich nur um 1 unterscheiden. Und diese beiden Zahlen haben dann zwangläufig keine gemeinsamen Teiler. Denn alle Teiler der kleineren Zahl können keine Teiler der um 1 größeren sein.

Eine Zahl teilt die andere

Ein ganzes Stück raffinierter ist der folgende Beweis. Gegeben sind wieder die natürlichen Zahlen von 1 bis 2n, wobei auch n eine natürliche Zahl > 0 ist. Wir wählen davon wiederum n+1 zufällig aus. Dann muss es unter den ausgewählten Zahlen immer zwei geben, von denen eine die andere teilt.

Für den ungarischen Mathematiker Paul Erdös war dieses Problem die ideale Einstieg in ein Gespräch über Mathematik. Er stellte es gern jungen Mathematikern - etwa beim Abendessen.

Die Lösung ist raffiniert und kurz zugleich: Wir können jede der n+1 zufällig ausgewählten Zahlen z schreiben in der Form

z = m*2k

Wobei m eine ungerade Zahl ist zwischen 1 und 2n-1. Weil wir n+1 Zahlen zufällig ausgewählt haben, es aber nur n verschiedene ungerade Zahlen zwischen 1 und 2n-1 gibt, müssen zwei der n+ 1 Zahlen den gleichen ungeradzahligen Faktor m besitzen.

Dann ist die kleinere der beiden Zahlen zwangläufig ein Teiler der größeren Zahl, denn die größere Zahl m*2a ist ein Vielfaches der kleineren m*2b . a und b sind dabei natürliche Zahlen und es gilt a>b.

Mehr zum Thema


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.