Happy Birthday

[Murray]

Answers to the January 7 puzzles
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
On Earth:20
On Mars:27

For the record, I did some quick math and there are about 670 days in a Martian year.

[This message has been edited by Murray (edited 01-07-2000).]

[dyslecix]

Actually, on earth, it is 30, I don't know how long a year is on Mars, but if you tell me, I can probably figure out it.

[Griffin]

I get 23 for humans and 31 for Martians. I'm assuming "better-than-average" means greater than 50%. Does it mean something else?

[judy]

are all birthdays equally likely if the number of days on earth and mars differ.......explain

[araya]

I agree with Griffin.

Apparently the martian year contains 668.60 martian days. I don't know if the particular leap year system the martians use affects the probabilities too much.

[hank]

I agree with Murray

[Paladin]

Griffin is right. The probability of finding a new birthday is given by the product of the probabilities (y-(n-1))/y, for n = 1 to the number of people asked; y = year length in days. After 23 humans and 31 Martians, this probability falls below a half. Therefore you are likely to have found at least one shared birthday. Nice one, Griffin.

[This message has been edited by Paladin (edited 01-09-2000).]

[hank]

Welcome to the Grey Labyrinth Paladin. So you are a market analyst hey? Well I'm not going to argue probabilities with you, your livelyhood depends on a good grounding in probability and statistics. So where did I go wrong? Upon asking the second person what his birthday is, I determine the probability of a match at 1/y. Upon asking the third person, I add the 1/y to the 2/y which is the probability of a match for the second question. So the probability of a match after asking 3 people their birthday is 3/y. I continue to ask people until the sum of the probabilities for each person asked exceeds one half of certainty. Hmmm.

[This message has been edited by hank (edited 01-09-2000).]

[This message has been edited by hank (edited 01-09-2000).]

[Paladin]

hank, the problem is this: Agreed, the prob for the second person matching is 1/y. But assigning the prob 2/y for the third person means you are considering the prob for the second person twice; that's why your number of people is low. The easy way to do it is figure out how likely you are to NOT match any of the previous ones (1 x 364/365 x 363/365 etc.) and subtract this prob from 1. A bit of prob theory:
P(X=A or B) = P(X=A) +P(X=B) -P(X=A and B)
You did not account for the P(X=A and B). EG If I'm thinking of the ace of spades and you have to guess and get the suit OR number right, your chance is 1/4 (suit) +1/13 (number) -1/52(exact card), otherwise you account for the ace of spades twice. I hope this clears it up for you, I'm here if it doesn't!

[This message has been edited by Paladin (edited 01-09-2000).]

[hank]

Paladin, It took me a while, but I finally got it. Basic probability theory. I remember passing a course in probability years ago, by memorizing the formulas, but with very little basic understanding. By the way, back in the 50's, there used to be a western on t.v. called Paladin. He wore black with the symbol of a chess knight on his holster. I can't remember the actor's name, but years later he played Hec Ramsey on tv.
Thanx for the help!

[Paladin]

As this discussion of a probability problem has become a dissertation on TV westerns, the show featuring Paladin was "Have Gun Will Travel". However, I have chosen my moniker in honour of Charlemagne's paladins, an order of crusading knights.

[Andy]

I think that's the same source for the TV hero's moniker, exemplified by the line "...a knight without armor in a savage land..." in the theme song.

[Ghost Post]

Fun one. I was also going to say 20 for Earth and 30 for Mars. The phrase "better than average" stopped me though.

Asking two people from Earth gives a 1/365 chance of them having the same birthday. That's your average.

Asking three will give you a 3/365 chance of matching a birthday, which is better than the average chance.

So for both answers I will go with "three" from each planet need to be asked.

[Quailman]

I'm not sure I follow the logic behind the answer to 23. It seems that this is a way of determining "If I ask 22 people their birthdates, what is the probability that the next one I ask will match (not match) at least one of the 22 people I've asked already?" I say if you're going to ask the 23rd person, you already have 22 distinct dates, or you would have stopped asking sooner. If I understand the formula, it calculates the probability that you will find a new birthdate when you ask the Nth person, but you may have already found a match.

I'm inclined to stick with 20.

[Ghost Post]

I think the question is, how many people do you have to ask so that you will have a greater than 50% chance that at least two will have the same birthday. The answer to that is 23.

With 23 people, the probability that there is at least one match is equal to one minus the probability that there is no match, or one minus the probability that they are all distinct.

The probability that N randomly chosen people all have distinct birthdays (for N>=1, <=365) is:

(365-0)/365 * (365-1)/365 * (365-2)/365 * ... * (365-(N-1))/365

or ( 365! / (365-N)! ) / 365^N

(this ignores the occasional Feb 29)

[Andy]

Quailman - I'm not sure how you got 20, but here's my reasoning for 23 (this formula is for all distinct, NOT for the Nth different from any previous):

Ignoring leap years, and assuming that all possible birthdays are equally probable:

When you ask N people, you can divide the possible sets of birthdays into two groups - a) All different, and b) not all different. It's not necessary (for this puzzle) to make any finer distinctions.

It's not particularly simple to calculate directly the probability that not all are different, and it becomes extramely cumbersome when more than a few people are included. It's much easier to calculate the probability that all are different, and subtract that from 1 (a and b above are mutually exclusive and collectively exhaustive).

For N=1, the first and only person's birthday can be any of the 365 days in the year and still be distinct, so the probability is 365/365 = 1.

For N=2, the second person's birthday is distinct if it is any of the 364 days not matching the first person's birthday. The probability is 365/365 * 364/365 = 364/365.

For N=3, for all 3 to be distinct requires that the second person's birthday is different from the first and the third person's birthday is different from either. If the first and second are the same, we don't care about the third; if they are different (prob 364/365), the third person has only 363 distinct days available (prob 363/365) so the probability that all 3 are different is 364/365 * 363/365.

Continuing is this fashion, the probability that N people's birthdays are all different is 365*364*...*(366-N)/365. This becomes less than .5 at N=23 - i.e. the probability of 23 randomly-chosen people all having different birthdays is less than 1/2. The probability that at least one pair share a birthday is then > 1/2.

Notes:
Considering leap years would alter the numbers only slightly.
All possible birthdays are not equally likely - I don't know the actual statistics, but I believe that the differences are small.
Considering the above factors would make the calculations much more complicated.

[Quailman]

Thanks Andy. That's an easy to follow explanation. I think I understand it now. The way I (and I suspect the others who got 20) arrived at 20 is:

1 person= 0 probability (duh!)
2 = 1/365 -->1/365
3 = 2/365 -->3/365
4 = 3/365 -->6/365
5 = 4/365 -->11/365
and so on, until the running total is greater than 50%. This assumes that at each person, you have a (n-1)/365 chance of hitting an already-named date. I thought that your formula gave a lower probability of a match than my method because it allowed for potential matches in the 22 previously selected dates.

The 23 formula says that half the time when you select 23 random people, they will have 23 different birthdays. The other half of the time, there will be one OR MORE duplicate birthdays within that group of 23. I think that to find a match at least half the time, you only need to go to 20.

[Ghost Post]

To find a match (which neccessarily means to find at least one match) at least half the time, you need 23 people. You may get more than one match though.

With less than 23 people, you will most likely (greater than .5 probability) have no matches at all. This statement is really equivalent to the above.

I don't think there is any number of people for which you would have a greater than 50% chance of there being exactly one match.

Given 23 people, there is a little over .5 probability that some two of those people will have the same birthday. But there is less than .5 probability that there will be one and only one match.

With 20 people, there is about a 41% chance of one or more matches (i.e. at least one match), and thus a 59% chance that there will be no match at all.


[This message has been edited by extro... (edited 01-17-2000).]

[Ghost Post]

tell me, what's wrong with this flow:

let N = number of earthlings u need to ask to ensure that at least 2 of them share the same birthdate.

then

N taken 2 at a time > 365/2

and you'll arrive at N >= 20 earthlings.

[Ghost Post]

Quailman: Using your approach (1/365 + 2/365 + ... + n/365), you would get a greater than 100% chance of a match with 27 people, when in fact you don't have a 100% chance of a match until you have 366 people.

The problem is, when you do:
1 person= 0 probability
2 = 1/365 -->1/365
3 = 2/365 -->3/365
4 = 3/365 -->6/365
5 = 4/365 -->11/365

You are assuming at step 5 that the previous 4 were all distinct - that is how you get 4/365. But they may not be all distinct. Now, you're probably saying that if the previous 4 are not all distinct, then there is already a match. Yes, this is true. But the probability of that is smaller, and you can't just assume it didn't happen to increase the probability by 4/365 for the fifth person.

Try a simpler case. You have an infinite pile of playing cards, from which you will pick 4. What is the chance that at least two will have the same suit (4 equally likely suits).
1 card = probability 0 that it matches a previous card (as there are no previous)
2 cards = 1/4 probability that it matches the previous card

Now, the 3rd card :
IF the previous 2 cards were distinct (there is a 1/4 chance of a match, so a 3/4 chance that they are distinct), the third card has a 2/4 chance of being the same suit as one of them. The chance that the previous 2 cards were distinct, AND that the 3rd card matches one of them, is thus 3/4 * 2/4 = 3/8 (not 2/4).
Add these up and you get 5/8.

Now the 4th card:
IF the previous 3 were distinct (we've established a 5/8 chance of a match, so theres a 3/8 chance of no match), the fourth card has a 3/4 chance of being the same suit as one of them. The chance that the previous 3 cards were distinct, AND that the fourth card matches one of them, is thus 3/8 * 3/4 = 9/32
Add this to the previous total of 5/8 (which was 0+1/4+3/8), and you get:
5/8 + 9/32 = 20/32 + 9/32 = 29/32

Now using the other approach, the probability of a match is one minus the probability that all four are distinct. The probability that all four are distinct is:
1st card = probability 1
2nd card = 3/4 chance it is different from first one
3rd card = 2/4 chance it is different from first two
4th card = 1/4 chance it is different from first three
Multiply (since this is an AND, as opposed to an OR), and you get 3/32.
1 - 3/32 = 29/32.

The answers match.

Edea: I don't see the logic behind "N taken 2 at a time > 365/2", especially the 365/2 part. You've shown that with 20 people, the number of possible distinct pairs of people is 190, which is greater than half the number of days in a year. But I can't take it beyond that.

I was tempted to say you've shown that given a particular day (like Valentines day), with 20 people you have a better than 50% chance that some pair of people from those 20 would have at least one person with their birthday on that day, but that is not true, since those 190 possible pairs of people are still only 20 people, and have 20 birthdays (at most) among them.

[Andy]

There's a distinction to be made here. There are two questions that could be asked:
1) How many people do you need to have probability > 1/2 of at least one match; and
2) How many people do you need to have expected number of matches > 1/2.

Suppose you have a large number of groups of people, each the same size (e.g. thousands of groups of 6 people each, or thousands of groups of 79 people each).
For 1) above, the question is: What is the smallest number of people in each group such that at least half the groups contain at least one match? The answer is 23.
For 2) above, the question is: What is the smallest number of people in each group such that the total number of matches is at least half of the number of groups? I don't know the answer to this yet.

Obviously, for a given group size > 2, the total number of matches will be larger than the number of groups containing at least one match.

[Ghost Post]

I know that I am splitting hairs here, but what is the average number of people you need to ask in order to caculate a "better-than-average" chance of matching a birthday?

I listed earlier that I was going to answer '3' to each problem. That's because I find the wording of the problem ambiguous. Giving the benefit of a doubt as to what they were asking for, here's my calculated answers.

You can pair 20 people 190 unique ways. 190 pairs / 365 possible birthdays gives you a 52% chance of making a match.

You can pair 28 Martains in 378 unique ways. 378 pairs / 730 possible birthdays gives you a 51% chance of making a match. I'm using 730 days for a Martain year because I do not presently know the exact length of a Martain year.

[mithrandir]

So you're saying if there were, say, 100 people there would be 4950 pairings, and thus a 4950/365=1356% chance of finding a match? I don't think so. There's quite obviously a way for all 100 to have different birthdays,so it must be less than 100%. I'm quite certain its 23 for Earth, I've heard this problem many times, even in my probability class last semester and the answer is 23. I haven't checked the Martian part, but I'll agree with the 31 everyone else is saying.

[Ghost Post]

(last week I wrongly posted this message in the topic "happy birthday" instead of replying to "Happy Birthday")

assuming that better than average means more than 50% replies are:
23 humans; 31 martians.

martian year has 669.59 days (martian days!)
reply is always 31 martians, even if martian have a calendar made by 669 days or 670 (in fact we should assume they have a calendar with some kind of correction, like our 29th february, if they had a gregorian calendar, but maybe they neither have a pope);

[karan]

The answer to this one is 183, for earth as 2n-1 >= 365 is the solving equation. I don't know how many days a martian year has but once that is found out just replace 365 in the above equation

[Ghost Post]

183 would be the answer if the question asked for a better than 50% chance of someone's birthday matching some particular day. For 183 people, I get a 99.999999999999999999999952199816 % chance that at least two will have the same birthday.

[Ghost Post]

i just now found this site and thought that this question deserved some attention. my guess is that 13 people in a single room have better than average chances of sharing a birthday. i'm not sure, but if my memory serves me correctly, then this is the answer. i came across it years ago and for some reason, it stuck. if i can find where i came across it, i will post it. as for martians, my guess is closer to 20.

[Ghost Post]

Maestro,

I seem to remember this posted in an old OMNI magazine puzzle section. They also stated that the answer was roughly 12-13.

Also, has anyone taken into consideration that the Martian "day" is slightly longer than our 24-hour day (about 2200 seconds longer (roughly 37 minutes)). So how many Martian days are in a Martian year?

[Evil Empire]

Murray factored in the Martian day and I think everyone has seemed to use his number of 670 for calculating the percentage.

[Jonas]

Hello,

Actually, extro..., the number of people you would have to ask so that a match between a specific date and the birthdays of those people would be more than 50% likely, is 253. Ironically enough this caused by the same fact the puzzle is based on: people's birthdays tend to be more on the same date with higher numbers.

If you want you can calculate it for yourself. The chance for someone _not_ to be born on a specific date is 364/365, so the chance for n people _not_ to be born on a specific date is (364/365)^n. If you subtract this figure from 1, you get the chance that there is a match between the given date and the birthdays. With n=253, this is somewhat more than 0,5

Jonas

[Ghost Post]

Yes, and thanks. I tricked myself on that one. I unknowingly assumed 183 different birthdays, which is extremely unlikely.

[Matthew Thomas Kesner]

I have to go with 3 for both planets. I assume the average is the percentage of asking two inhabitants their birthday and having them be the same. I need not even figure out that percentage, all I need to do is better it- I'll ask a third.

[Ghost Post]

Yeah, the "better than average" miswording (I certainly hope it's a miswording) has been pointed out. Most of us have assumed that "better than 50% chance" was what was intended.

By the way - how did you come up with that name?

[Matthew Thomas Kesner]

Better than average does not mean more than 50%. But playing along and answering the question that way I have to agree with Karen although she made a boo boo. The question stated for us to assume that "all birthdays are equally likey," so the leap year birthday would have to be artificially added as equally likely. So my answer to the over 50% chance would be 184. 23 makes no sense at all. The 24th person would have a less than 7 percent chance of having the same birthday as the other 23. When you ask the 24th person there are 343 possible birthdays currently open and only 23 taken. You think there is a better than 50% chance that the 24th person is going to have one of the 23 taken birthdays rather than the 343 open ones????
As for Mars, we'd need the population because for each person selected you are depleting that days birthday pool by one. Assuming the population is big enough that that wouldn't be a factor like it isn't on Earth then my answer is 336 for Mars. Being that there are roughly 669.68 martian days in a martian year. That's cool to think that they probably would have a "leap" year every 4 years where they left out a day of a 670 day calender. (ps. a day on Mars is about 40 minutes longer than Earths.)

That's just my opinion- I could be wrong!

[Ghost Post]

Better than average does not mean more than 50% - that's understood, which is why I called it a "miswording".

And yes, the 24th has perhaps a less than 7% chance of matching one of the previous 23. But when you add the chance of the 23rd matching one of the previous 22, and the chance of the 22nd matching one of the previous 21, etc..., it adds up pretty quickly.

You asked: "You think there is a better than 50% chance that the 24th person is going to have one of the 23 taken birthdays rather than the 343 open ones?" Answer: Of course not. I ask: Do you think that the only way there can be a match among 24 people is if the 24th person matches one of the previous 23? Can't there be matches among the previous 23?

It's much simpler to think of it this way: With 23 people, what is the chance that they all have different birthdays? (For if they don't all have different birthdays, then there is at least one match). With 1 person, there are 365 possible birthdays that don't conflict with any of the previous ones (there are no previous), so it's a 365/365 chance. With 2 people it's 365/365 * 364/365 (i.e. the chance that the first persons birthday matches no previous ones times the chance that the second persons birthday matches no previous one). With 3 it's 365/365 * 364/365 * 363/365.

With 23 it's 365/365 * 364/365 * 363/365 * ... * 343/365
Which is less than 0.5

So with 23 people there is a less than 50% chance that all birthdays will be different.

The odds of having 184 randomly chosen people with no two having the same birthday is astronomically small - less than 1 in a trillion.

[Matthew Thomas Kesner]

I caught my mistake that not long after I posted it. Dumb dumb Matthew! Your explanation with the cards let me see the errors of my ways!

[Ghost Post]

this is maestro again, i found where i saw the answer to the question. i read it in a book called "Facts and Fallacies" which i read about 10-12 years ago. the answer is 23, saying that as the size of a group increases, the number of possible pairs also increases, but at a faster rate. in a group of five, the chance that people will share a b-day is just under 3 in 100, for 15, it is over 1 in 4, and for 23, it is nearly 1 in 2. so without all of the math, there is your answer.

there is a story that accompanies this.

"i his book 'lady luck,' the mathemetician warren weaver relates how this curious fact came up in conversation during a dinner party for a number of army officers during world war ii.
most of weaver's fellow guests thought it incredible that the figure was just 23; they were certain it would have to be in the hundreds. when someone pointed out that there were 22 people seated around the table, he put the theory to the test.
in turn, each of the guest revealed their birthday, but no two turned out to be the same. then the waitress spoke. 'excuse me,' she said. 'i am the 23rd person in the room, and my birthday is may 17th, just like the general's over there'" - facts and fallacies (1988)

sorry i don't have a martian incident.