-5
$\begingroup$

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

Why is this true?

$\endgroup$

closed as off-topic by Travis, 3SAT, Morgan Rodgers, Harish Chandra Rajpoot, jameselmore Feb 9 '16 at 17:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Travis, 3SAT, Morgan Rodgers, Harish Chandra Rajpoot, jameselmore
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Because $3 \cdot 12 = 36 < 40$. $\endgroup$ – martini Feb 9 '16 at 13:54
  • $\begingroup$ But wouldn't that statement be equivalent to saying that "Given 40 people, at least 3 of them were born in the same month of the year"? $\endgroup$ – CSstudent Feb 9 '16 at 13:56
  • $\begingroup$ Even ‘at least one of them was born the same month of the year’… $\endgroup$ – Bernard Feb 9 '16 at 14:00
  • $\begingroup$ It's called the pigeonhole principle. If you have $N$ objects and $M$ bins with $N>nM$ then there must be some bin with at least $n+1$ objects in it. $\endgroup$ – Gregory Grant Feb 9 '16 at 14:03
  • $\begingroup$ Ah, I see. Thank you! $\endgroup$ – CSstudent Feb 9 '16 at 14:05
2
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Very detailed and informative. Thank you. $\endgroup$ – CSstudent Feb 9 '16 at 14:48
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Assuming three people, then there could not be any more than 3, because if there were, then the population would have be over 40. Right? $\endgroup$ – CSstudent Feb 9 '16 at 13:57
  • $\begingroup$ If there are at most three people born in any month, then the number of people is at most $3 \cdot 12 = 36$, contrary to assumption. $\endgroup$ – N. F. Taussig Feb 9 '16 at 13:58
  • $\begingroup$ So then the statement is false? Given a population of 40 people, there can only be 3 people who were born in the same month. If there were 4 people born in the same month, the population would have to be over 48. Is that correct? $\endgroup$ – CSstudent Feb 9 '16 at 14:00
  • $\begingroup$ I should have said a contradiction, rather than contrary to assumption. I supposed that there was no month that had four people born in that month, which meant that at most three people were born in the same month. That led me to the contradiction that there were at most $36$ people, contrary to the known fact that there are $40$ people. Hence, there is at least one month in which at least $4$ people were born. $\endgroup$ – N. F. Taussig Feb 9 '16 at 14:03
  • $\begingroup$ Oh! I see now. Thank you! $\endgroup$ – CSstudent Feb 9 '16 at 14:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.