Author |
Topic: Standing in Line (Read 777 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Standing in Line
« on: Nov 12th, 2003, 4:38am » |
 Quote  Modify
|
A cinema is offering a free ticket to the first person with the same birthday as someone ahead of him/her in the queue. Ignoring leap years, and assuming a uniform distribution of birthdays, where in the queue should you stand in order to maximize your chances of winning?
|
|
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Standing in Line
« Reply #1 on: Nov 12th, 2003, 5:10am » |
Quote Modify
|
::I would suppose you'd want x persons in front of you, all with different birthdays, giving you a chance of x/365 that one of them will have your birthday. And then maximize for x, which isn't too hard to find then.. I hope.. 
hmm.. I expected a better chance than 173158 in 5357635 ~= 3.2%::
|
| « Last Edit: Nov 12th, 2003, 5:18am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Standing in Line
« Reply #2 on: Nov 12th, 2003, 10:23pm » |
Quote Modify
|
If there's x people in front of you, the probability of you winning is
P(x) = x!(N-1Cx-1)/Nx=x(N-1)!/(Nx(N-x)!).
Now, x! ~ exlog x - xsqrt(2[pi]x), so
dx!/dx ~ x! (log x + 1/(2x)) ~ x! log x
Setting P'(x) = 0 gives
-1/x = log (1-x/N) ~ -x/N,
so x ~ sqrt(N); plug that in and you get a value of 1/sqrt(eN).
For N=365, this gives an approximation of 3.17%, versus the actual value, which is closer to 3.23%.
I'm not sure where 173158/5357635 comes from...it's close to what I get, but it doesn't seem to be a convergent of the continued fraction expansion or anything like that?
|
|
IP Logged |
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: Standing in Line
« Reply #3 on: Nov 12th, 2003, 11:27pm » |
Quote Modify
|
I would stand directly behind my twin brother, near the front. If he couldn't make it then I would stand 57th in line.
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Standing in Line
« Reply #4 on: Nov 13th, 2003, 12:30am » |
Quote Modify
|
on Nov 12th, 2003, 10:23pm, Eigenray wrote:| I'm not sure where <hidden> comes from... |
|
I just calculated the chance for integral x's, and took the x which maximized the chance.
When I threw it in symbolic math-program it simplified to that fraction..
Oddly enough I can't seem to reproduce it, so I'm now puzzled... (the error is in the order of a rounding error at machine-level, so maybe I made an aproximation somewhere without realizing..)
|
| « Last Edit: Nov 13th, 2003, 12:42am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Standing in Line
« Reply #5 on: Nov 13th, 2003, 2:37am » |
Quote Modify
|
In general, you'll want the closest integer to sqrt(N) people ahead of you, verified for N<5000.
For an extra digit of accuracy, taking another term in the approximation gives
Pmax ~ 1/sqrt(e)*[1/x + 1/(2x2)], which is 3.26% when N=365.
Problems like this always involve e somehow...
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Standing in Line
« Reply #6 on: Nov 17th, 2003, 5:01am » |
Quote Modify
|
Somewhat simpler:Let pn be the probability that the person in position n wins.
There are n-1 ways for someone ahead in the queue to share the same birthday as person n.
Now we need n-2 distinct birthdays among the remaining 364 days.
These can be chosen in 364C366-n ways.
Hence pn = (n-1)*(364C366-n)/365n-1
And pn/pn-1 = (n-1)*(367-n)/[(n-1)*365]
This is a decreasing function for n > 2, and we want the largest n such that pn/pn-1 > 1
Solving for n gives n < [3 + sqrt(1461)]/2
This gives n = 20 and p20 = 0.03231985755...
|
| « Last Edit: Nov 17th, 2003, 5:05am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print