17
$\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$
  • 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$ – barak manos May 8 '16 at 16:06
  • 2
    $\begingroup$ If you are the same person who posted this other Pigeonhole Principle problem, you should merge your accounts. $\endgroup$ – N. F. Taussig May 8 '16 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 '16 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 '16 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$ – MackTuesday May 9 '16 at 21:09
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$
  • $\begingroup$ Ah I see, I am still trying to grasp the pigeonhole principle, so this helped out a lot. Thank You. Ans: 25. $\endgroup$ – Kono Dio Da May 8 '16 at 16:20
45
$\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$
  • 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 '16 at 17:09
  • 5
    $\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$ – person27 May 9 '16 at 17:16
  • 1
    $\begingroup$ Wow, great way to reword this question, instantly making it clear! $\endgroup$ – Kik May 9 '16 at 18:00
  • $\begingroup$ Maybe it should have been reworded from the start? $\endgroup$ – user317457 May 9 '16 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$ – Michael Hardy May 30 '16 at 4:50
12
$\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$
  • $\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$ – Kono Dio Da May 8 '16 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 '16 at 20:42
  • $\begingroup$ @nocomprende Because such questions are usually formulated that way. $\endgroup$ – egreg May 9 '16 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 '16 at 20:47
1
$\begingroup$

12 month * 2 people + 1 maybe.

$\endgroup$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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