Subscribe via feed.

## A Deal with the Devil for £163m

Posted by Karl Sharman on July 15, 2011 – 9:10 am

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…

Tags:
This post is under “Tom” and has 37 respond so far.

### 37 Responds so far- Add one»

1. 1. cazayoux Said：

I’ll choose position 183.

2. 2. John24 Said：

23

3. 3. Chris Said：

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.

4. 4. Chris Said：

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

5. 5. Tom Said：

i think John24 has it right

6. 6. Chris Said：

You need to be second in line.

7. 7. Chris Said：

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

8. 8. Scott Said：

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%).

9. 9. Karl Sharman Said：

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?

10. 10. Scott Said：

Ahh, I messed up one of my probability calcs.

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

11. 11. Chris Said：

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.

the one that corresponds to my date

13. 13. Chris Said：

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.

14. 14. Karl Sharman Said：

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

15. 15. Scott Said：

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

16. 16. Chris Said：

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…

17. 17. Scott Said：

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…

18. 18. Scott Said：

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…

19. 19. Haley&Will Said：

Will and I say 23.

20. 20. Karl Sharman Said：

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

21. 21. Chris Said：

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.

22. 22. Karl Sharman Said：

Go ahead Chris – publish – damnation awaits…

23. 23. Chris Said：

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)! 365n). 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.

24. 24. windy Said：

163

25. 25. Scott Said：

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

26. 26. Chris Said：

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.

27. 27. Karl Sharman Said：

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.

28. 28. Karl Sharman Said：

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

29. 29. Karl Sharman Said：

Posting at the same time are we?

30. 30. Chris Said：

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.

31. 31. Chris Said：

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.

32. 32. cazayoux Said：

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

33. 33. Chris Said：

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

34. 34. cazayoux Said：

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

35. 35. John24 Said：

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.

36. 36. Chris Said：

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.

37. 37. kikifoxgrin Said：