19
$\begingroup$

How should I begin solving this? I know that for months, there are 12, and 3 people from a small group suppose to have birthdays in the same month.

Do I just multiply $12\times 3 = 36$ people?

Or do I use "$\lceil x \rceil$"?

$\endgroup$
15
  • 8
    $\begingroup$ Calculate the number of people required to make each month "containing" exactly $2$ people, then add $1$ person (thus guaranteeing one month "containing" $3$ people). $\endgroup$ May 8, 2016 at 16:06
  • 2
    $\begingroup$ If you are the same person who posted this other Pigeonhole Principle problem, you should merge your accounts. $\endgroup$ May 8, 2016 at 21:28
  • 2
    $\begingroup$ A little off-topic comment: this kind of question should include at least a word "any" (group), one can select a group of three twin childs born on may 9th: choose any three (not a joke) of them, and all of them have birthday in may. So the answer is 3 :-) $\endgroup$
    – z100
    May 9, 2016 at 13:28
  • 3
    $\begingroup$ Something about the wording of the question in the title makes me think that it has no answer. There is no way to "guarantee" anything without some kind of constraint. There is no constraint in the question, so to me it sounds like a statistical inference, and since the birthdays of people in general are not correlated, there is no way to guarantee anything. You could poll 1000 people on the street and they might all be born in the same month. You could ask 3 and they might all be born in the same month. How do you make a guarantee? $\endgroup$
    – user317457
    May 9, 2016 at 20:40
  • 1
    $\begingroup$ I'll put what @nocomprende wrote in other words: How do we know from the problem statement that, for example, the people don't all have the same birthday? $\endgroup$ May 9, 2016 at 21:09

5 Answers 5

46
$\begingroup$

Q: How do you avoid having three people with birthdays in the same month while making your group of people as large as possible?

A: By having two in each month. That makes $24$ people. So in which month was the $25$th one born?

$\endgroup$
5
  • 2
    $\begingroup$ I really hate to ask this, because I am positive I just don't understand higher mathmatics, but how is this true? If all 24 people have the same birth month, then ?? $\endgroup$
    – CGCampbell
    May 9, 2016 at 17:09
  • 6
    $\begingroup$ @CGCampbell Then you don't have the worst-case scenario. The question is to find what number of people is required to guarantee that, no matter what the distribution of birthday months is, at least 3 of them will share the same month. In this case, the worst-case scenario is given by spreading out birthday months as much as possible. With 24 people, that means 2 for each month. If you have 25 people, it's impossible not to have at least 3 people share the same month. $\endgroup$
    – kettlecrab
    May 9, 2016 at 17:16
  • $\begingroup$ Maybe it should have been reworded from the start? $\endgroup$
    – user317457
    May 9, 2016 at 20:44
  • $\begingroup$ @CGCampbell : Nobody said 24 people all have the same birth month. I said two in each month. I.e. two in January, two in February, two in March, and so on. $\qquad$ $\endgroup$ May 30, 2016 at 4:50
  • $\begingroup$ @GCCampbell : Maybe I didn't fully understand your comment the first time, but if all 24 are in the same month, then you have NOT avoided having three in the same month. $\endgroup$ Aug 27, 2020 at 21:06
42
$\begingroup$

Your question is a straightforward application of the pigeonhole principle. In its simplest form, applied to the context of your question, the pigeonhole principle states that for $m = 12$ months, if there are $n \ge 13$ people in a group, then there is guaranteed to be a month in which at least two people's birthdays occur.

This makes intuitive sense: if we had $n = 12$ people, then each person could be assigned a different birth month. But if we add in one more person, this thirteenth person would necessarily have a birth month in common with one of the other twelve.

The generalization of this idea is given in the Wikipedia article we linked to:

For natural numbers $k$ and $m$, if $n = km + 1$ objects are distributed among $m$ sets, then...at least one of the sets will contain at least $k+1$ objects.

As this applies to your original question, then, we see that $m = 12$ (the number of months), $n$ is the number of people in the group, and $k = 2$ is the maximum number of people allowed to share a birth month before satisfying the criterion of the problem.

$\endgroup$
1
  • $\begingroup$ Ah I see, I am still trying to grasp the pigeonhole principle, so this helped out a lot. Thank You. Ans: 25. $\endgroup$ May 8, 2016 at 16:20
11
$\begingroup$

A group of twenty-four people can fail to satisfy the request (how?). What if you ask another person to join the group?

$\endgroup$
4
  • $\begingroup$ "If k+1 objects are assigned to k places, then at least one place must be assigned at least two objects" I'm still trying to grasp the pigeonhole principle. So 2X12 = 24 we add 1 and get our answer to be 25? $\endgroup$ May 8, 2016 at 16:11
  • $\begingroup$ So, the question is really asking: what is the largest number that can fail to satisfy the question, plus one? Why doesn't he just ask the proper question, since we all know how to add one? $\endgroup$
    – user317457
    May 9, 2016 at 20:42
  • $\begingroup$ @nocomprende Because such questions are usually formulated that way. $\endgroup$
    – egreg
    May 9, 2016 at 20:44
  • $\begingroup$ When I studied statistics, I found that most of it would have been a lot more understandable if it had been stated in terms that people were familiar with. I guess this is like data analysis, where a lot of queries to the database actually ask for things that are not there. People seem to be fascinated by counterfactuals and things that don't exist! $\endgroup$
    – user317457
    May 9, 2016 at 20:47
1
$\begingroup$

12 month * 2 people + 1 maybe.

$\endgroup$
0
1
$\begingroup$

The Answer is $25$, So the question is assuming that if there were $12$ people in the same room they are all born in separate months, so you would do $2\times12=24$. Now $2$ people are in each month now add one person because whichever month he is born in will allow there to be $3$ in one month.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .