## Lottery Ticket ................

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

### Lottery Ticket ................

The lottery (in the UK) consists of 6 balls being drawn out of a total of 49 (numbered 1-49) .... plus another ball is drawn out of the remaining balls - this is the "bonus ball", but is irrelevant to this question.
When you purchase a lottery ticket, you pick 6 different numbers in the range 1-49.
If you have 3 numbers, you win £25. ..... obviously more numbers = a bigger win.
My question is, what is the minimum number of lottery tickets that I would have to buy, to guarantee that I win at least £25 ??
Now according to: http://lottery.merseyworld.com/Info/Chances.html
..... the odds of getting 3 numbers are approx 1 in 57 .... but if you buy 57 tickets, you're not guaranteed a win.
Permutations and combinations, etc, is not my strong point ...... anyone any ideas please ??

Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

### Re: Lottery Ticket ................

Not an answer, but deserves a spoiler anyway:
Spoiler:
This is an open problem. It's called, appropriately enough, the "lotto design" problem. You can google "L(49,6,6,3)" for more info.
With that out of the way, maybe the most fun way to handle this thread is for people to find the best ticket arrangements they can, without copying from the current best known results.
Let's get the ball rolling. I can do it in 875 tickets. That sucks, though. I bet picking a few hundred random tickets would work, even without a clever strategy.

nicklikesfire
Posts: 43
Joined: Fri Sep 02, 2011 11:20 am UTC
Location: CT, USA

### Re: Lottery Ticket ................

I think the upper bound is:

Spoiler:
729 tickets
tickets 001_ _ through 999_ _ (999 tickets)
take out everything that uses a zero (001 through 110, plus all multiples of ten, plus all X01 through X09)

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Lottery Ticket ................

nicklikesfire wrote:I think the upper bound is:

Spoiler:
729 tickets
tickets 001_ _ through 999_ _ (999 tickets)
take out everything that uses a zero (001 through 110, plus all multiples of ten, plus all X01 through X09)

i think you're confusing the way tickets are picked in this game for a different game. You're not picking a number between 1 and 100000, you're picking six numbers between 1 and 49.

A true upper bound is

Spoiler:
922, since that's the number of tickets required to cover all possible groups of 3.

You're on the right track though, because

Spoiler:
Figuring out how to remove redundant tickets is the key to the puzzle.

edit:

here's my solution track so far

Spoiler:
Consider that you pick a ticket with numbers ABCDEF. You win, then, if the winning ticket contains some combination of ABCDEFXYZ, where XYZ are numbers you didn't pick. Out of numbers you didn't pick, there are 43!/(40!3!) possible combinations for XYZ. Pick six from those nine, and you get (43!/(40!3!))(9!/3!6!) tickets that you can win with. However, this contains some redundant tickets, since ABCDEX getting picked could be from ABCDEFXYZ or from ABCDEFXYW, or from a whole lot of other chosen 9-pools. So we need to remove the redundancies. I am not sure what the best approach is for this, but I'm going to go from the bottom up:

There's one ticket that matches all six of your numbers: 1
Matching 5 of your numbers is (6 you can take out)(43 to put back in): 258
Matching 4 of your numbers is (6!/4!2! you can take out)(43!/41!2!) you can put back in): 13545
Matching 3 of your numbers is (6!/3!3! you can take out)(43!/40!3!) you can put back in): 246820

Now, I could have my math all screwed up there because it's been a long time since I've done combinatorics. But, that sum gives 260624 possible winning tickets from your one ticket. Since there's 83902896 tickets in all, that should mean that you can purchase 322 tickets and win. Note that it's not just any 322 tickets; but carefully constructed ones that don't have any solution overlap.

Unfortunately, I know that the actual answer has been shown to be much less than that, so I'm wondering where the error in my reasoning or math is. I have yet to read any of the literature on the actual proven boundaries.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Lottery Ticket ................

Xias wrote:A true upper bound is

Spoiler:
922, since that's the number of tickets required to cover all possible groups of 3.

I'm not sure that really is a proven upper bound.
Spoiler:
A ticket with 6 numbers covers 6C3 = 20 triplets.
There are 49C3 = 18424 triplets in total.
In the best possible case you could choose the numbers on your tickets so that no two tickets cover the same triplets. If you could do that for 921 tickets, you would cover 18420 of the triplets, and then a 922th ticket is needed to cover all of them.

There is however the assumption that it is possible to choose the 922 tickets to make their triplets non-overlapping enough to cover all of them. Therefore the real number of tickets to cover all possible triplets may be higher.

Regardless, the question is not about the number of tickets to cover all triplets, but the number of tickets to cover at least one of the 20 triplets that the winning set of numbers produces, regardless of what the winning numbers are going to be. This number will be lower than 922 anyway, which the rest of your argument makes fairly plausible, even though you run into the same issue of not proving the ticket combinations can actually be chosen that way.

Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

### Re: Lottery Ticket ................

Maybe some kind of Pigeonhole argument will help?
Spoiler:
If you split the 49 numbers into two groups of 24 and 25, then the winning ticket is guaranteed to have three numbers from at least one group. Maybe we can buy tickets to cover each group separately.

One reason this is good is that it's a lot more manageable for a computer than worrying about all 49C6 ~= 10,000,000 possible winning numbers. I wrote a Python program that keeps track of all 25C3 possible triples of numbers in a single group, and tries to cover them all with tickets. It's kind of a random-greedy search: at every step, it generates 20 random possible tickets, then chooses the one that covers the most remaining triples.

It found a list of 273 tickets which together cover every triple in the numbers 1-25, and a list of 237 tickets which together cover every triple in the numbers 26-49. (I considered copying the lists of tickets into here, but it's a huge mess of numbers, and I doubt you would gain anything from it.) Therefore, the answer is at most 273+237 = 521 tickets.

Moonbeam
Posts: 292
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

### Re: Lottery Ticket ................

Apparently it's called The UK National Lottery Wheeling Challenge and the record, so far, for the minimum number of tickets guaranteed to match 3 numbers is:

Spoiler:
163 tickets

and a list of all the tickets, can be found here

Now according to:

http://math.stackexchange.com/questions ... o-guarante

.... the true value is reckoned to be between
Spoiler:
87 and 163
... although, as of yet, no one has got lower than the upper limit ....

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Lottery Ticket ................

Moonbeam wrote:.... the true value is reckoned to be between
Spoiler:
87 and 163
... although, as of yet, no one has got lower than the upper limit ....

Of course not. If someone did, that would be the new upper limit.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Moose Anus
Posts: 417
Joined: Fri Oct 14, 2011 10:12 pm UTC

### Re: Lottery Ticket ................

It seems like you could cut out a few of the numbers from the wheel.
Spoiler:
You could remove 47, 48, and 49 from the wheel because if those numbers are picked, there will also be three other numbers that are picked and they can match up to your pool of tickets. So the wheel may be able to reduce its size by removing 3 numbers. I'm not sure if that would reduce the overall number of tickets in the wheel though.

ToastOfDestiny
Posts: 6
Joined: Sun Nov 30, 2008 5:55 am UTC

### Re: Lottery Ticket ................

Is it just me, or should the bounds be much higher?
Spoiler:
The event "at least three matches" is the union of "exactly 3, 4, 5, or 6" matches, or the complement of "exactly 0, 1, or 2" matches.

6 of the balls are going to be the winning balls, and 43 are going to be losing balls.

(43 choose 6) * (6 choose 0) = 6,096,454 tickets will score exactly 0 balls.
(43 choose 5) * (6 choose 1) = 5,775,588 tickets will score exactly 1 ball.
(43 choose 4) * (6 choose 3) = 1,851,150 tickets will score exactly 2 balls.

Adding these together, there are 13,723,192 distinct losing tickets.

To guarantee victory, you'd need 13,723,192 + 1 tickets.

elasto
Posts: 3750
Joined: Mon May 10, 2010 1:53 am UTC

### Re: Lottery Ticket ................

ToastOfDestiny wrote:Is it just me, or should the bounds be much higher?
Spoiler:
The event "at least three matches" is the union of "exactly 3, 4, 5, or 6" matches, or the complement of "exactly 0, 1, or 2" matches.

6 of the balls are going to be the winning balls, and 43 are going to be losing balls.

(43 choose 6) * (6 choose 0) = 6,096,454 tickets will score exactly 0 balls.
(43 choose 5) * (6 choose 1) = 5,775,588 tickets will score exactly 1 ball.
(43 choose 4) * (6 choose 3) = 1,851,150 tickets will score exactly 2 balls.

Adding these together, there are 13,723,192 distinct losing tickets.

To guarantee victory, you'd need 13,723,192 + 1 tickets.

I think it's like this:

Spoiler:
There's no point including all of the following tickets:
123456
123457
123467
123567
124567
134567
234567

If one of them has won, others are guaranteed to have won also. Or, to turn it round, if six of them have lost, the seventh will have too.

So we need not obtain as many as 13,723,192+1 tickets; We could start there but go on to exclude most because of the numbers they share in common with each other. We only need keep hold of tickets which have a triplet not on any other ticket.

ThirdParty
Posts: 347
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

### Re: Lottery Ticket

Since, aside from Moonbeam's links, nobody's said anything about a lower bound yet, here's a simple proof that we need at least 54 tickets:
Spoiler:
There are (49*48*47*46*45*44)/(6*5*4*3*2*1)=13,983,816 possible combinations of numbers. Each ticket we buy gets 3 matches on ((6*5*4)/(3*2*1))*((43*42*41)/(3*2*1))=246,820 combinations, 4 matches on ((6*5*4*3)/(4*3*2*1))*((43*42)/(2*1))=13,545 combinations, 5 matches on ((6*5*4*3*2)/(5*4*3*2*1))*(43)=258 combinations, and 6 matches on 1 combination, for a total of 246,820+13,545+258+1=260,624 ways to win. 13,983,816/260,624 = 53.6. So even if we somehow managed to find 53 tickets with no triplets in common, we still couldn't be guaranteed to win.

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

### Re: Lottery Ticket

ThirdParty wrote:Since, aside from Moonbeam's links, nobody's said anything about a lower bound yet, here's a simple proof that we need at least 54 tickets:
Spoiler:
There are (49*48*47*46*45*44)/(6*5*4*3*2*1)=13,983,816 possible combinations of numbers. Each ticket we buy gets 3 matches on ((6*5*4)/(3*2*1))*((43*42*41)/(3*2*1))=246,820 combinations, 4 matches on ((6*5*4*3)/(4*3*2*1))*((43*42)/(2*1))=13,545 combinations, 5 matches on ((6*5*4*3*2)/(5*4*3*2*1))*(43)=258 combinations, and 6 matches on 1 combination, for a total of 246,820+13,545+258+1=260,624 ways to win. 13,983,816/260,624 = 53.6. So even if we somehow managed to find 53 tickets with no triplets in common, we still couldn't be guaranteed to win.

That was what I was trying to calculate above, and I see that my mistake was that for some reason I divided by 6*5*4 instead of 6!. That explains why my lower bound was so much higher than proven upper bounds. So, thanks for showing me my error (even though you seem to have missed my post entirely, judging by your first sentence ).