Given any 40 people, at least four of them were born in the same month of the year

Question

Given any 40 people, at least four of them were born in the same month of the year.

Why is this true?

Answer 1

Given any $40$ people, at least four of them were born in the same month of the year.

The the phrase "at least four of them were born in the same month of the year" means just that there is some subset of four people out of the $40$ who share a common birth month. It does not mean that everyone belongs to some clique of four people with the same birth month.

The usual proof of this uses a version of the so-called Pigeonhole Principle. The idea is that if you have $n$ holes and can only put $k$ pigeons in each hole, the total number of pigeons you can put in the holes is $nk$.

We consider each month to be a "hole" and each person to be a "pigeon" in the "hole" named by the month they were born in. The question is, is it possible to assemble a group of $40$ people without ever putting a fourth person into any of the holes?

Of course it's easy to arrange it so that we do have four people who were born in the same month of the year, if we can pick whomever we want to be in the group. Just interview people until you find four with birthdays in January, then add any other $36$ people.

But if you are trying not to have any subset of four people who have the same birth month, then once you have three people born in any particular month you cannot accept any more from that month. Once you have three birthdays in March, for example, you cannot let in any more. You can only take other months.

Once you have added the $36$th person to the group, one of the following two things has happened:

1. For each of the $12$ months, you have $3$ people born in that month;
2. You already have at least four people born in the same month (for example, you might have $5$ July birthdays, or $4$ in September).

So when you add a $37$th person to the group, either you are in case 1, and no matter who you choose and what their birth month is, you already have three people born in that month and the new person makes four, or you are in case 2 and already have four people born in the same month.

Some related groups sizes are:

• $4$ is the minimum number of people in your group in order for it to be possible to have at least four born in the same month.
• $36$ is the maximum number of people in your group if you do not have four people born in the same month. (There is no group of more than three born in the same month.)
• $37$ is the minimum number of people in your group in order for it to be necessary to have at least four born in the same month.
• $48$ is the maximum number of people in your group in order for it to be possible to have no group of more than four born in the same month.

Answer 2

Hint: Suppose otherwise. Then at most three people are born in each of the twelve months of the year. What can you conclude?