Re: A birthday puzzle
 

ok, I get it now. I was confused over the meaning of the phrase "The first person in line who..."

It evidently means, The First "first person in line" who ...

I took it to mean that if at any time, any person in line has a birthday matching one of the ticket purchasers, then the First such person in line wins the ticket. With a billion people in line almost certainly one of them will match the first ticket purchaser. I figured the birthday would be announced on a loudspeaker, there would be about 2,740,000 people in line with matching birthdays raising their hands, and the First of them in line would get the ticket.

Nevermind


PairTheBoard

LetYouDown, can you post your code? (NM)
 

Maybe we can find the flaw.

Re: A birthday puzzle
 

Alternate way of solving.

Excel Spreadsheet -- took about 2 minutes (longer to type this).

1. For each person on line, calculate the probability that there is a birthday match.

Person 1 -- 0.0000, Person 2 -- 1/365 (.00274), Person 3 2/365 (.005464) etc.

2. Determine the percentage chance that someone has not already won (this will be 1 - the sum of the probablilties determined in step 1 for all prior people).

3. For each person in line, multiply the amount in step 1 by the amount in step 2.

Relevant part of chart --

Person 19 .032207
Person 20 .03232
Person 21 .03225

Probablilities of winning increase to person 20 and decrease thereafter

Re: A birthday puzzle
 

Very Nice Ken.

Two New Variations
 

Variation 1 (fairly easy if you can do the orignial variation)

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose birthday and birth hour is the same as someone else who has already purchased a ticket. You can get in line at any time. The birthdays and hours are distributed uniformly at random over 365 days and 24 hours. Which position in line should you take?


Variation 2
(Hard. I don't think there is a closed form expression for the answer, but maybe good approximations exist.)

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose random number is the same as someone else who has already purchased a ticket. You can get in line at any time. The random numbers are uniformly distributed integers ranging from 1 to N. Which position in line should you take? (The answer is a formula which depends on N.)

Re: Two New Variations
 

[ QUOTE ]

Variation 2

The manager of a movie theatre announces that a free ticket will be given to the first person in line whose random number is the same as someone else who has already purchased a ticket. You can get in line at any time. The random numbers are uniformly distributed integers ranging from 1 to N. Which position in line should you take? (The answer is a formula which depends on N.)

[/ QUOTE ]
Actually, I think this might have been asked in this forum before.

Let P(k) be the probability that the first duplicate is the kth person in line.

P(k) = (N-1)(N-2)...(N-(k-2)) (k-1) / N^(k-1)

We'd like to know when P(k+1) is smaller than P(k). When this happens, we want to be the kth person in line.

P(k+1)/P(k) = (N-(k-1))k / (N (k-1))

After a little algebra, we see that this is 1 when k(k-1)=N, or when k = 1/2 + sqrt(N+1/4).

When 1/2 + sqrt(N+1/4) is an integer, it is equally good to stand in this place or the next. These are the optimal places. For example, when N=2, it is equally good to stand in place 0.5+sqrt(2.25)=2 and 3.

When 1/2 + sqrt(N+1/4) is not an integer, the optimal place is given by rounding 1/2 + sqrt(N+1/4) up to the next integer. For example, when N=365, you want position ceiling(0.5+sqrt(365.25)) = ceiling (19.61) = 20.

Re: Two New Variations
 

Lovely solution. I didn't sit down to figure it out before reading your post. I should have!

Re: A birthday puzzle
 

You are looking for:
P(No Birthday Found Before Me)*P(Someone's Birthday In Line is the same as mine | Unique Birthdays)

Call them 1-f(n) and g(n).

g(n) is easy, its (n-1)/365, where n is your position in line.

f(n) is a little more tricky, in essence, its "a birthday matched before me, or everyone before me is unique, and I match".

So f(n) = f(n-1) + (1-(f(n-1))*g(n).

These can be calculated out.

So the max of (1-f(n))*g(n) occurs when n = 20, so when there are 19 people in front of you.