Photo:
MIRROR ONLINE
Munich is the third largest city in Germany.
According to official figures, on February 28, 2022, the city had exactly 1,563,723 inhabitants.
Maybe a few more have come along in the meantime.
It is quite possible that the population has also fallen somewhat since then.
Many people from Munich have friends who also live in Munich.
We do not know how many of the approximately 1.5 million inhabitants this applies to and how many friends each of these people has.
They should prove that there are at least two people from Munich who have the same number of friends in Munich.
Note: Friendships are always meant to be reciprocal.
For the solution, we use a method that also makes it easy to show that at least two people live in Berlin who have the same amount of hair on their heads: the so-called
drawer principle
.
We do not know the exact population of Munich.
It doesn't matter either, as we shall see shortly.
Suppose
n people
live in Munich .
A person can have between
0 and n-1 friends
in the city.
So there are
n
different numbers of friends possible.
Actually there are only
n-1
!
We have to distinguish two cases:
There is at least one person who is friends with all other people from Munich.
Then there can be no Munich man or woman who is without a friend.
So at most n-1 different numbers of friends are possible – between 1 and n-1.
There is not a single person who is friends with all other people from Munich.
Then nobody has n-1 friends.
In this case, too, at most n-1 different numbers of friends are possible - between 0 and n-2.
But if
n people
from Munich can only have
n-1 different numbers of friends
, there must be at least two people who have the same number of friends.
This is the drawer principle.
We imagine that there are n-1 drawers.
Each drawer has a number of friends on it, each one has a different number.
Everyone from Munich then throws a piece of paper into the drawer with the number on it that corresponds to the number of his or her friends.
Because n people throw their name slips in at most n-1 different drawers, at least two slips end up in at least one drawer.
I discovered this beautiful combinatoric problem in the book "The Secret of the Twelfth Coin" by Albrecht Beutelspacher.
In case you missed a mystery from the past few weeks, here are the most recent episodes:
Which number comes next?
The perfect seating arrangement for world explainers
Searched for sum of angles
Mysterious phone numbers
Looking for a cheap chain
How big is the blue area?
Get there quickly
Cutting pizza for professionals
Toss coin, win bet
The stingy king
