1
$\begingroup$

You are allowed to select as many random1 people as you like, and place them in a room. How many do you need for the probability that at least 2 people will have a birthday2...
  a. on the same day...
  b. on two consecutive days...
...to be greater than 50%?

Please explain why this is so. You may ignore leap years if it interferes with the answer, which I'm pretty sure it would.

  1. In this case, random means they have a $\frac{1}{365}$ chance of having a birthday on Jan. 1, or any other day.
  2. The 'birthday' references the day and month. Years are irrelevant.
|improve this question
$\endgroup$
6
$\begingroup$

Let's suppose there are $r$ people in the room. We want to find the probability that at least two have the same birthday or adjacent birthdays. It seems easier to find the complementary probability, i.e. the probability that no two have the same or adjacent birthdays.

There are $365^r$ possible arrangements of birthdays for the $r$ people, all of which we assume are equally likely. The number of arrangements in which the birthdays are distinct and non-adjacent can be obtained from a well-known combinatorial formula, as follows. There are $\binom{365-r+1}{r}$ ways to pick $r$ integers from 1 to 365 with no two adjacent, where $\binom{n}{m}$ is a binomial coefficient: $\binom{n}{m} = \frac{n!}{m! (n-m)!}$. But we need to multiply by $r!$, because we are considering the people to be distinguishable, so the order of the $r$ integers is significant. Hence the probability that no two people have the same or adjacent birthdays is $$f(r) = \frac{\binom{365-r+1}{r} r!}{365^r}$$

The probability that at least two people do have the same or adjacent birthdays is $1-f(r)$. If we do the computations, we find $1-f(13) = 0.4822$ and $1-f(14) = 0.5368$, so the answer to your question is that you need 14 people.

I should add that we're not considering 31 December and 1 January to be adjacent. If we did, it would change the probabilities a little bit, but I don't think it would change the final answer of 14 people.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Nice answer. In case you're interested, if we count December 31 and January 1 as adjacent, the number of ways to pick $r$ days with no two adjacent is ${365-r+1\choose r}-{365-r-1\choose r-2}$. I checked, and you are correct that this doesn't change the answer of 14. $\endgroup$ – Julian Rosen Dec 24 '14 at 17:43
4
$\begingroup$

This is more complicated than simply the birthday problem times three, because there's the potential for overlap. For instance, if person A is born on Jan 5, and person B is born on Jan 7, then person C only has a 5/365 chance to meet the criteria.

Rather than do the math, I wrote a script to solve it, ignoring leap years (although it turns out that the margin between N=16 and N=17 is large enough that I expect the same answer holds if leap years are accounted for).

With 16 people, you will satisfy the criteria 48.3% of the time, and with 17 people, you satisfy them 52.6% of the time, so the answer is 17. I put the script up at http://pastebin.com/YjNzECrP if anyone would like to check my work.

EDIT: Thanks to Lopsy for pointing out a mistake in the script, fixing that causes it to produce 14 people as the answer.

|improve this answer
$\endgroup$
  • $\begingroup$ thank you for right approach :) (im too lazy to calculate that) It seems OP does not know the answer, so he accepted other one. $\endgroup$ – shyos Dec 24 '14 at 15:25
  • $\begingroup$ Your script has a typo. b.count([i]) > 1 should be b.count(i) > 1. As a result, it only counts consecutive birthdays, not equal birthdays. The correct answer is 14, as was proven by awkward. $\endgroup$ – Lopsy Dec 24 '14 at 17:47
  • $\begingroup$ I knew it was 14... $\endgroup$ – warspyking Dec 25 '14 at 1:40
2
$\begingroup$

Like the birthday problem, but with triple the likelihood, I guess...

  1. So, person 1 would have a birthday, doesn't matter when, won't be before or after anyone else.

  2. Person 2 could have their birthday on any of the 365 days (lets ignore leap years, since the question does), chance of the 2nd person being within a day of the first person is 3/365.

  3. If they don't (362/365) then the next person has a 6/365 chance to be within a day of the first two, and so on.

  4. So we have 1 * 362/365 * 359/365 * ... First time this drops below 50% is 365/365 * 362/365 * 359/365 * 356/365 * 353/365 * 350/365 * 347/365 * 344/365 * 341/365 * 338/365 * 335/365 * 332/365 * 329/365 * 326/365 = 0.4596676, so 14 people.

Edit: Typed too fast and fat fingers took over :)

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ actually with your thinking/calculation it should be 14 people with prob is equal to 0.4596676222355141. You jumped from 365 to 352. However still this isnt the right answer for question. $\endgroup$ – shyos Dec 24 '14 at 14:48
  • $\begingroup$ D'oh, thanks for spotting that - updated now. $\endgroup$ – CaffeinatedDave Dec 24 '14 at 14:52
  • $\begingroup$ this is not the right answer. why accepted? $\endgroup$ – shyos Dec 24 '14 at 15:21
  • $\begingroup$ @warspyking Then your source is wrong, this answer does not include overlapping days. $\endgroup$ – shyos Dec 24 '14 at 15:28
  • $\begingroup$ @warspyking I can't reach his script from work, but his approach is right, if code is also right then it is the right answer. $\endgroup$ – shyos Dec 24 '14 at 15:32
2
$\begingroup$

The solution: If we consider Jan 1 and Dec 31 not adjacent is given above. In the comment of the accepted answer, it is indicated that if we consider Jan 1 and Dec 31 adjacent, the number of ways to arrange the birthdays is $\binom{365-r+1}{r}-\binom{365-r-1}{r-2}$. I'm having some trouble understanding this.

Could anyone points out where I'm doing wrong?

I think this is equivalent to ask:
How many ways can we arrange 365-r $0$s and r $1$s such that the ones are not adjacent. First, for the case treating Jan 1 and Dec 31 non adjacent, I paired the $r$ ones in the following way: $$10,10,...,10,1$$ Therefore, there are $365-2r+1$ 0s left. Then the number of ways satisfying the non-adjacency condition is $\binom{365-2r+1+r}{r}=\binom{365-r+1}{r}$, which agrees with the accepted answer.

To consider the case treating Jan 1 and Dec 31 adjacent. I do the following: $$10,10,...,10$$ and there are then $365-2r$ 0s left. Similar argument gives the number of ways being $\binom{365-r}{r}$.

We can also think about the second case by subtracting the number of arrangements satisfying condition in the first case and Jan 1 and Dec 31 are occupied by 1. I do the following: $$1,01,01,...,01,0,1$$ There are $r-2$ 01 pairs and one 0 in the middle, a total of $r-1$ spots. There are still $365-2r+1$ 0s out there. Therefore, the number the ways fixing a one on Jan 1 and another one on Dec 31 while all ones in between satisfying the non-adjacency condition is $\binom{365-2r+1+r-1}{r-1}=\binom{365-r}{r-1}$. Therefore the final result is $\binom{365-r+1}{r}-\binom{365-r}{r-1}=\binom{365-r}{r}$, which agrees with my previous argument.

Could anyone points out where is wrong?

|improve this answer
$\endgroup$
  • $\begingroup$ Hi, welcome to puzzling SE! You can add spoiler tags by adding >! in front of your text! $\endgroup$ – North Feb 24 at 21:14

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.