## A Deal with the Devil for £163m

You have made a deal with the devil… You will win the lottery if you can decide the optimal position in the queue to buy the £163m Euromillions winning lottery ticket.

There are some conditions. Ain’t that always the way when making this sort of deal!

You will win, if your position in the queue is the first position whose birthday is the same as someone who has already bought a ticket in the queue ahead of you. You can get into the line at any position, after all, the devil is in favour of queue barging!

Assuming that you don’t know anyone else’s birthday, that birthdays

are distributed randomly throughtout the (non-leap)year, etc., what position in line gives you the greatest chance of being the first duplicate birthday?

Your very soul depends on this…

July 15th, 2011 at 10:17 am

I’ll choose position 183.

July 15th, 2011 at 11:01 am

23

July 15th, 2011 at 1:43 pm

I know why John24 gave that value. I think it is harder than that though. Someone at position 22 has a similar probabilty of being the winner. So I think you need to be nearer the head of the queue. I’ll do some calculations later.

July 15th, 2011 at 2:03 pm

Ooops. John24’s answer might be smarter than I thought.

July 15th, 2011 at 2:11 pm

i think John24 has it right

July 15th, 2011 at 3:31 pm

You need to be second in line.

July 15th, 2011 at 4:11 pm

Confucius he say “you need to be twentieth in line, then you have a 3.17% probability of winning the lottery ticket”.

July 15th, 2011 at 10:04 pm

I’ll take position #207

This is a tricky one.

You must consider the probability of any pair matches against the probability of a match against yourself.

You would want the position in line that offers both the least chance of there being any pair matches ahead of you but also provides the best chance of there being a match for yourself.

If you graph these functions they collide at around position #207 (~43%).

July 16th, 2011 at 12:41 am

Chris – Agreeing with John24 – 23rd, 2nd and 20th – any other queue positions you would like to take up to ensure this £163m prize? If you change any more I shall have to ask you to preface your answer with: “Karl, my final answer is…..”

Scott – a good position for having a high probability of matching a birthday ahead of you in the queue… But is that the best chance of being the first person in the queue to have a matching birthday?

July 16th, 2011 at 2:19 am

Ahh, I messed up one of my probability calcs.

I now revise my position in line to #40. final answer.

July 16th, 2011 at 3:33 am

Karl. My final answer is the 20th in line. But I’m not entirely satisfied with the precise way I’ve found that, and so accept it might be wrong. I won’t have computer access for the next 40 or so hours. So no further calculations from me, unless it’s within the next hour. The probabilty of winning is 3.15% (3SF).

I hadn’t quite agreed with John24. My comment was meant to imply that he was closer than I first thought, although it had crossed my mind that by a curious coincidence with the birthday paradox, that he might actually be right.

My second in line was due to a serious error of reasoning.

July 16th, 2011 at 4:07 am

the one that corresponds to my date

July 16th, 2011 at 4:10 am

Aaaarrrghhh. I just tried another calculation and got 23rd in line with prob 26.6% – but I think that’s a mistake.

Definitely gotta go. Rats and rats.

July 16th, 2011 at 4:13 am

Chris, does this one count as your final answer or are we sticking with ~20 until something better comes up?

July 16th, 2011 at 4:38 am

@ #40 there is both a 10% chance of there being any matches and 10% chance of there being a match for yourself.

July 16th, 2011 at 4:51 am

LOL. Even though it’s making me late, I’ve turned PC on again. I’m lost. I like my 20th and a low probability. But…

July 16th, 2011 at 5:14 am

Hmm, it would seem that I suck badly at probability, I left out the last step (combining the 2 probabilities) and I’m now getting a similar answer as Chris.

But I’ll jump just in front @ #19. final, final answer

(I’m probably still wrong though)

With ~3.1535% chance of winning, I’m not sure this deal was such a good idea…

July 16th, 2011 at 5:28 am

LOL, I love this puzzle, it’s doing my head in but I have a compulsion to solve it.

I think Chris has it @ #20, I think my 19 was how many people in front of me in queue, nice job Chris I know how you feel on the uncertainty of the calcs

Thanks for a good challenge, I learned something useful:

Don’t deal with the devil, he’s a crafty statistician…

July 17th, 2011 at 11:04 am

Will and I say 23.

July 17th, 2011 at 1:57 pm

I’m not going to post the answer to this for a few more days…

July 17th, 2011 at 2:16 pm

Hi Karl. I’m home again. I’m ready to publish (and be damned). I can hold off as to why the answer is 20 if you like.

July 17th, 2011 at 3:04 pm

Go ahead Chris – publish – damnation awaits…

July 17th, 2011 at 3:08 pm

If you are in position n+1 in the queue, there will be n people in front of you. The probability that at least one of them shares your birthday is 1 -(364/365)

^{n}.The probability that no people share a birthday in a group of n people is 365!/((365-n)! 365

^{n}). See http://en.wikipedia.org/wiki/Birthday_problem for both fornulae.So the probability of you sharing a birthday with one of the n people, and none of them sharing any birthday is the product of those two probabilities. That’s allowed as the two situations are independent.

I don’t know a slick method of finding the maximum value of that product. The standard calculus method leaves you with an equation that is very difficult to solve (except by numerical methods) and even then the gamma function slips in.

Number crunching shows that the maximum value of the overall probability occurs when n = 19, and then the probability is 3.15352%. So you need to be at position 20 in the queue. I had unwittingly used an approximation for the birthday problem when I said 3.17% in post 20. At position 23, the probability is 3.07092%, at 40 it’s 1.23571%, and at position 183 it’s 3.74734*10

^{-23}%Now I await Karl’s damnation.

July 17th, 2011 at 7:43 pm

163

July 18th, 2011 at 1:05 am

I concur with Chris’ method, though being a novice it took me much longer and several wrong answers before I got there

July 18th, 2011 at 3:50 am

For what it’s worth, for positions 19, 20, 21 the probabilities are 3.14679%, 3.15352%, 3.14242%.

If it were possible, you’d really like to have 18.9 people in front of you, then the probability of winning would be a whopping great 3.15367%.

I’m dying to know why so many of you think position 23 is the optimum position.

July 18th, 2011 at 3:50 am

Chris did get the right answer at 20th place in the queue.

Please pop round to my place in Falkirk to pick up the £163m…

Here is an alternative, none to slick alternative to Chris’s solution…

Suppose you are the Kth person in line. Then you win if and only if the K-1 people ahead all have distinct birthdays AND your birthday matches one of theirs.

A = event that your birthday matches one of the K-1 people ahead

B = event that those K-1 people all have different birthdays

Then

Prob(you win) = Prob(B) x Prob(A | B)

(Prob(A | B) is the conditional probability of A given that B occurred.)

Now let P(K) be the probability that the K-th person in line wins,

Q(K) the probability that the first K people all have distinct

birthdays (which occurs exactly when none of them wins). Then

P(1) + P(2) + … + P(K-1) + P(K) = 1 – Q(K)

P(1) + P(2) + … + P(K-1) = 1 – Q(K-1)

P(K) = Q(K-1) – Q(K) This is what we want to maximize.

Now if the first K-1 all have distinct birthdays, then assuming

uniform distribution of birthdays among D days of the year,

the K-th person has K-1 chances out of D to match, and D-K+1 chances

not to match (which would produce K distinct birthdays). So

Q(K) = Q(K-1)*(D-K+1)/D = Q(K-1) – Q(K-1)*(K-1)/D

Q(K-1) – Q(K) = Q(K-1)*(K-1)/D = Q(K)*(K-1)/(D-K+1)

Now we want to maximize P(K), which means we need the greatest K such

that P(K) – P(K-1) > 0. (Actually, as just given, this only

guarantees a local maximum, but in fact if we investigate a bit

farther we’ll find that P(K) has only one maximum.)

For convenience in calculation let’s set K = I + 1. Then

Q(I-1) – Q(I) = Q(I)*(I-1)/(D-I+1)

Q(I) – Q(I+1) = Q(I)*I/D

P(K) – P(K-1) = P(I+1) – P(I)

= (Q(I) – Q(I+1)) – (Q(K-2) – Q(K-1))

= Q(I)*(I/D – (I-1)/(D-I+1))

To find out where this is last positive (and next goes negative), solve

x/D – (x-1)/(D-x+1) = 0

Multiply by D*(D+1-x) both sides:

(D+1-x)*x – D*(x-1) = 0

Dx + x – x^2 – Dx + D = 0

x^2 – x – D = 0

x = (1 +/- sqrt(1 – 4*(-D)))/2 … take the positive square root

= 0.5 + sqrt(D + 0.25)

Setting D=365 (finally deciding how many days in a year!),

desired I = x = 0.5 + sqrt(365.25) = 19.612 (approx).

The last integer I for which the new probability is greater than the old is therefore I=19, and so K = I+1 = 20. You should try to be the 20th person in line.

July 18th, 2011 at 3:52 am

Chris, 32%? I’m seriously cutting into the queue at a very specific point, mid person – is that not 3.2…%?

July 18th, 2011 at 3:53 am

Posting at the same time are we?

July 18th, 2011 at 4:08 am

Hi Karl, 32% was not only a typo, but worse, was wrong (now fixed). Depending on how I calculate it, I keep on getting different results for the best n when I let n become real. But Mathematica will slip into using the Gamma[n+1] rather than n! when n isn’t integral.

July 18th, 2011 at 4:35 am

Hi Karl. Good problem, I’ve not seen it before. I was well agitated at not being able to find the time to make sure my head was clear about it.

July 18th, 2011 at 11:40 am

Chris: to answer your question in post 26 …. because it was one of the numbers on the hatch (4,8,15,16,23,42)

July 18th, 2011 at 12:27 pm

Hi cazayoux. I don’t understand. What’s the hatch?

July 19th, 2011 at 1:53 pm

Hi Chris … it was a reference to the TV show “LOST”.

July 19th, 2011 at 7:37 pm

23 is the smallest number of people in a group that would yield a better than 50% chance of two people having the same birthday.

How many ways can you pick n birthdays from a calendar before you have a match ( 365! / ( (365-n)! ) divided by the total number of ways to pick n birthdays (365^n).

365! / ( (365-n)! / 365^n which becomes

365! / ( (365-n)! * 365^n)

solving for n so the answer is greater than 50% give you 23, to be precise 50.73% chance.

July 20th, 2011 at 6:17 am

Hi cazayoux. Would you believe that I’ve not seen a single episode of “Lost”. So why didn’t anyone suggest 42? It featured on “Lost” and is also the answer to everything.

Hi John24. I knew that was probably why 23 was being offered. I couldn’t understand why anyone thought it was relevant, except to show that it must be too large.

August 3rd, 2011 at 7:28 pm

I have two answers…. second place, right after your twin.

and being “Everyman” the embodiment of every man of all times and places (from the play Everyman)

Mostly just for jokes….this is what my family came up with when presented this question.