20 people in a room. 40% chance two people share a birthday.

What? How do you do that calculation. Someone explain it to me. I'm sure it has something to do with combinations or permutations but I don't know how they get to that % via math.

Edit: It's 41.1% actually. But the calculation in general:

You have 20 people in a room what is probability two people share a birthday?

Someone explain.

This one's easy, but it's kind of not exact: It's the probability that not everyone is born on a different day. This includes, for example, the probability that two people are born on the same day, and that two other people are born another day, which is the same for them.

First off, what's the probability that no people share birthday? If we can find that, then we can do the magic trick P(not A) = 1 - P(A) to find the answer.

So, for two persons, what is the probability that they do not share birthday? Well, it is the probability that they do not have a birthday on the same day, which is the following:



So, say person A is born on x, then person B is born on any other day, which there are 364 of. Divide that by the total amount of days, which is 365, and you got your answer.

Let's extend this into three persons: Say person A is born on x, and person B is born on y. Then, we first need to know the probability that x and y is different days, which is the answer above. Then we multiply this by the probability that person X is born on z, which is neither x or y. As there are 363 different days to choose from which are not x or y, we multiply by 363/365.

Now, in general, we can say that this is P(n) where n is the amount of people. For P(1), the answer is 1. For P(2), the answer is 364/365. For P(3), the answer is P(2) * 363/365.

The neat thing about this is that this is induction. We can show that, for any amount of people n (which is positive integer), P(n) = P(n-1) * (366-n)/365. With some further trickery with the terms, we then end up with this thing:



So that's the expression for the probability that all have distinct birthdays. For the probability that they do not, just calculate 1 - P(n). For 20, it is 3176795160316341458068147014210271053247964357/7721192983187403134097091636121110137939453125.

Noah

[video=youtube;9G0w61pZPig]http://www.youtube.com/watch?v=9G0w61pZPig[/video]
and
http://www.wolframalpha.com/input/?i=1-%...F365^20%29

1-P(everyone has a different birthday)

Consider person one... he can have any birthday without matching someone

1-365/365 aka 0% 1 person shares a birthday with someone else (makes sense.... there's no one else)

2nd person... any birthday cept the one from the previous person so he has 364/365 options

1- (365*364)/(365*365)

go to 20 people

1- (365*...*346)/(365^20) ~41%

How many people do you need in a room to guarantee that there exists at least ONE group of 3 people who either:
- Know one another mutually, or
- Know nothing about anyone else in the group

?

That's basically a graph connectedness question.

Basically, set up relationships between people as lines connecting them.

Do a cut that contains 3 people.
- all connected: they all know each other
- all unconnected: they don't know each other
- 2 connected, 1 isol: okay

So basically the question is, what's the largest number composed entirely of that third option. Plus 1.

3 people: possible. A knows B, neither know C.
Inductive: try to add a person so that none of the possible sets of 3 gain someone attached to the pair.
ie. 4th person must know C.
4 people: A knows B, C knows D.
Try again. How do we add a 5th person? If we add it to an existing group (knowing any of the 4) that forms 3 who know each other. If we add it outside, we get 3 who know nothing about anyone else in the group.

So... 5 people.

Hold on hold on, I've read your posts but I'm still trying to grasp it to full understanding. Hold on.

That's basically a graph connectedness question.

Basically, set up relationships between people as lines connecting them.

Do a cut that contains 3 people.
- all connected: they all know each other
- all unconnected: they don't know each other
- 2 connected, 1 isol: okay

So basically the question is, what's the largest number composed entirely of that third option. Plus 1.

3 people: possible. A knows B, neither know C.
Inductive: try to add a person so that none of the possible sets of 3 gain someone attached to the pair.
ie. 4th person must know C.
4 people: A knows B, C knows D.
Try again. How do we add a 5th person? If we add it to an existing group (knowing any of the 4) that forms 3 who know each other. If we add it outside, we get 3 who know nothing about anyone else in the group.

So... 5 people.

I'll just leave this here.

 spoiler...

The point is that you have to guarantee that there exists at least one group of 4 in which ONE person has to know (or not know) the rest. This can happen with 6, but not 5 (you can know 2 and don't know the other 2, but if you're given 5 people, you have to either know or not know 3).

Well, I assumed that "know each other mutually" means that if Alice knows Bob, and Bob knows Carol, then that group of 3 counts as knowing each other, because Bob knows all 3 members.

As such, deductively:
- there can only be two or fewer groups that are linked in this way (if there are 3, take 1 from each and they don't know each other)
- each group can only have 2 people in it at most, otherwise the 3 people in that group are mutual acquaintances.

there's no way for 5 people to satisfy both.


If it requires a group of 3 people in a triangle, all knowing each other, then there's no limit on the size of the group.
However, you
- can't have loops of fewer than 4 people (forms a triangle)
- can't have a loop of 4 people, along with anyone else (take every 2nd member, plus one from the other group)
- can have a loop of 5, as long as there's noone else (your first example)
- can't have loops of 6 or more people (take every 2nd)