In Kooperation mit

Job & Karriere

Rätsel der Woche Viele Freunde sollt ihr sein

In München leben mehr als 1,5 Millionen Menschen. Beweisen Sie, dass es mindestens zwei Einwohner gibt, die gleich viele Freunde in der Stadt haben.
Foto:

SPIEGEL ONLINE

München ist die drittgrößte Stadt Deutschlands. Laut offiziellen Angaben hatte die Stadt am 28. Februar 2022 genau 1.563.723 Einwohner. Vielleicht sind in der Zwischenzeit auch noch einige dazugekommen. Gut möglich, dass die Einwohnerzahl seitdem auch etwas gesunken ist.

Anzeige
Dambeck, Holger

Blind Date mit zwei Unbekannten: 100 neue Mathe-Rätsel (Aus der Welt der Mathematik, Band 4)

Verlag: KiWi-Taschenbuch
Seitenzahl: 256
Für 11,00 € kaufen
Produktbesprechungen erfolgen rein redaktionell und unabhängig. Über die sogenannten Affiliate-Links oben erhalten wir beim Kauf in der Regel eine Provision vom Händler. Mehr Informationen dazu hier

Viele Menschen aus München haben Freunde, die ebenfalls in München leben. Für wie viele der rund 1,5 Millionen Einwohner das gilt und wie viele Freunde jede einzelne dieser Personen hat, wissen wir nicht.

Sie sollen beweisen, dass es mindestens zwei Personen aus München gibt, die gleich viele Freunde in München haben.

Hinweis: Freundschaften sollen immer wechselseitig sein.

Bei der Lösung nutzen wir eine Methode, mit der sich auch leicht zeigen lässt, dass in Berlin mindestens zwei Personen leben, die gleich viele Haare auf dem Kopf haben: das sogenannte Schubfachprinzip.

Wir kennen die genaue Einwohnerzahl Münchens nicht. Sie ist auch egal, wie wir gleich sehen werden. Angenommen, in München leben n Menschen. Eine Person kann zwischen 0 und n-1 Freunde in der Stadt haben. Es sind also n verschiedene Anzahlen von Freunden möglich.

Tatsächlich sind es aber nur n-1!

Wir müssen zwei Fälle unterscheiden:

  1. Es gibt mindestens eine Person, die mit allen anderen Menschen aus München befreundet ist. Dann kann es keinen Münchner und keine Münchnerin geben, die ohne Freund ist. Also sind höchstens n-1 verschiedene Anzahlen von Freunden möglich – zwischen 1 und n-1.

  2. Es gibt keine einzige Person, die mit allen anderen Menschen aus München befreundet ist. Dann hat niemand n-1 Freunde. In diesem Fall sind ebenfalls höchstens n-1 verschiedene Anzahlen von Freunden möglich – zwischen 0 und n-2.

Wenn nun aber n Menschen aus München nur n-1 verschiedene Anzahlen von Freunden haben können, muss es mindestens zwei Personen geben, die gleich viele Freunde haben.

Dies ist das Schubfachprinzip. Wir stellen uns vor, dass es n-1 Schubfächer gibt. Auf jedem Schubfach steht eine Freundeanzahl, auf jedem eine andere. Jeder Münchner und jeder Münchnerin wirft dann einen Zettel in das Schubfach, auf dem die Zahl steht, die der Anzahl seiner oder ihrer Freunde entspricht. Weil n Personen ihre Namenszettel in höchstens n-1 verschiedene Schubfächer werfen, landen in mindestens einem Schubfach mindestens zwei Zettel.

Entdeckt habe ich dieses schöne Kombinatorikproblem im Buch »Das Geheimnis der zwölften Münze« von Albrecht Beutelspacher.

Sollten Sie ein Rätsel aus den vergangenen Wochen verpasst haben – hier sind die jüngsten Folgen:

Anzeige
Dambeck, Holger

Kommen drei Logiker in eine Bar...: Die schönsten Mathe-Rätsel (Aus der Welt der Mathematik, Band 3)

Verlag: KiWi-Taschenbuch
Seitenzahl: 240
Für 9,99 € kaufen
Produktbesprechungen erfolgen rein redaktionell und unabhängig. Über die sogenannten Affiliate-Links oben erhalten wir beim Kauf in der Regel eine Provision vom Händler. Mehr Informationen dazu hier