DO NOT TRY TO SOLVE THE "174 CHALENGE" IN LESS THAN 87 TICKETS!
Iliya Bluskov
I posted a (quite rough) lower bound, 54, on the number of tickets
to garantee a 3 win in 6/49 lottery. There is a better (recent) result
of Furedi et al.
Just to recall what we are talking about:
A system S of k-subsets(tickets) of an n-set V={1,2,...,n}
is called an (n,k,p,t)-lottery system(wheel) if for every p-subset P of V
one can find a k-subset(ticket) L of S such that L and P have at least
t numbers in common.
The minimum number of tickets in an (n,k,p,t)-lottery system is denoted
by C(n,k,p,t).
The result of Furedi, Szekely and Zubor is
(n choose t)(n-p+1)
C(n,k,p,t)>= -----------------------------------
(p-1 choose t-1)(k choose t)(n-t+1)
The aplication of this estimate for n=49, k=p=6, t=3 gives
C(49,6,6,3)>=87.
As 87 is exactly twice less than 174, there is still room for improvement...
Iliya Bluskov
Eric Montagnino
>This may be of some help to the attackers of the 174 ticket challenge.
>I posted a (quite rough) lower bound, 54, on the number of tickets
>to garantee a 3 win in 6/49 lottery. There is a better (recent) result
>of Furedi et al.
>Just to recall what we are talking about:
>A system S of k-subsets(tickets) of an n-set V={1,2,...,n}
>is called an (n,k,p,t)-lottery system(wheel) if for every p-subset P of V
>one can find a k-subset(ticket) L of S such that L and P have at least
>t numbers in common.
>The minimum number of tickets in an (n,k,p,t)-lottery system is denoted
>by C(n,k,p,t).
>The result of Furedi, Szekely and Zubor is
<snip>
Where/when was this published? Is the article available online?
I am still wondering if anyone is still interested in implementing a
"brute force" program or something that uses this formula.
Dave Budd
>I am still wondering if anyone is still interested in implementing a
>"brute force" program or something that uses this formula.
Interested but too busy with real work, sadly.
The 'brute force' code is simple, given a decent FORTRAN on a 64bit vector
processor such as the CS6400 we have here. I'm a trifle concerned about the
disk storage I'd need though. Maybe I'll get round to it if I ever get this
damn Novell machine fixed.
--
...or something
Dave Budd +44 161 275 6033 fax 6040 D.B...@mcc.ac.uk
http://www.man.ac.uk:80/~zlsiida (getting better!)
Bill Brooks
says...
>
>In article <4f6m46$k...@bud.shadow.net> emo...@shadow.net (Eric
Montagnino) writes:
>>I am still wondering if anyone is still interested in implementing a
>>"brute force" program or something that uses this formula.
>
>Interested but too busy with real work, sadly.
>The 'brute force' code is simple, given a decent
>FORTRAN on a 64bit vector processor such as the CS6400 we
>have here. I'm a trifle concerned about the disk storage I'd need
>though. Maybe I'll get round to it if I ever get this damn Novell
>machine fixed.
I too was thinking about writing a very brute-force program to test this
out. Problem is, from working on similar problems in a brute-force method
I guess it would take from two weeks to a month on my P-133 at home.
Since I'm not going to tie up my home computer for that long, I'll
probably run in on an old 386-33 I have around.
It's anyone's guess how long that will take!
Bill Brooks.
Eric Montagnino
>I too was thinking about writing a very brute-force program to test this
>out. Problem is, from working on similar problems in a brute-force method
>I guess it would take from two weeks to a month on my P-133 at home.
>Since I'm not going to tie up my home computer for that long, I'll
>probably run in on an old 386-33 I have around.
>It's anyone's guess how long that will take!
I hope you have a UPS ! It will probably take soooo long on a 386
that the you will have a power outage before it finishes. :-)
Let me know if you have any luck. I am curious to see if the recently
posted formula is correct.
Eric Montagnino
>The minimum number of tickets in an (n,k,p,t)-lottery system is denoted
>by C(n,k,p,t).
>The result of Furedi, Szekely and Zubor is
> (n choose t)(n-p+1)
>C(n,k,p,t)>= -----------------------------------
> (p-1 choose t-1)(k choose t)(n-t+1)
Being a "mathematical midget" I am not sure that I understand the
terminology " n choose t". Does this mean n things chosen t at a
time?
Iliya Bluskov
>
>>The result of Furedi, Szekely and Zubor is
>
>> (n choose t)(n-p+1)
>>C(n,k,p,t)>= -----------------------------------
>> (p-1 choose t-1)(k choose t)(n-t+1)
>
>
>Being a "mathematical midget" I am not sure that I understand the
>terminology " n choose t". Does this mean n things chosen t at a
>time?
Yes, that is right.
>
>>The aplication of this estimate for n=49, k=p=6, t=3 gives
>>C(49,6,6,3)>=87.
>
>
The paper is published in Journal of Combinatorial Design vol.4,No 1, 1996, pp.
5-10.
Iliya Bluskov
Bill Brooks
Oops. I recently discovered that it would take not only a month on a P-133,
but probably closer to 6 months! I wrote a program to do it, and thought I'd
test it out using the following method: Reduce the lottery to a 6/10 lottery
(pick 6 with numbers from 1 - 10) and attempt to find a minimum covering to
gaurantee a 3 number winner for 10, 9, 8, 7, 6, and 5 tickets. I started it
yesterday and after about 20 hours it's still trying to figure it out for 10
tickets. Correct me if I'm wrong, but I'll try to explain why it will take so
long...
Taking the 6/10 stripped-down lotto as an example, there are 210 possible
combinations of 10 numbers. There are 120 combinations of 3 numbers. To
determine if you can get a 100% coverage of the 3-number combinations with 10
tickets, you need to try every 10-ticket combination of among the 210 possible
combinations. Do you know how many combinations that is?
210! / (10! * 200!) =
(210 * 209 * 208 * 207 * 206 * 205 * 204 * 203 * 202 * 201) / 10! =
(210 * 209 * 208 * 207 * 206 * 205 * 204 * 203 * 202 * 201) / 3628800 =
36,976,937,738,230,000
(please correct my math if it's wrong!)
And then for each of those combinations you have to check to see if all 120
3-number combinations are covered (although the last step isn't the most
time-consuming). And that's only for 10 tickets out of 210 combinations.
Think about 174 tickets out of 13,983,816 combinations...
13983816! / (174! * 13983642!)
Granted we already know there's a cover for 174 tickets, but I would start
with 174 in order to verify the program is working, and to find out if there
may be more than one 174 ticket cover. Then you have to check for 173
tickets, 172, 171, etc., all the way down to (supposedly) 87 tickets - and
maybe beyond if the calculation is incorrect (which I personally doubt).
This is a Win95 program so it will run even while working on other programs,
but then you have to worry about windows crashing (what's the probability on
that happening :) probably pretty likely!), or the power failing during the
course of operation. So I think I'll put in some sort of status-saving code
that will allow you to restart the program from the last saved "known point"
in the figuring.
I'll get back to you next year...
:)
Bill Brooks
Eric Montagnino
>>Taking the 6/10 stripped-down lotto as an example, there are 210 possible
>>combinations of 10 numbers. There are 120 combinations of 3 numbers. To
>>determine if you can get a 100% coverage of the 3-number combinations with 10
>>tickets, you need to try every 10-ticket combination of among the 210 possible
>>combinations.
>This is not the same as the 174 ticket challenge. In that case, you can't
>have 100% coverage of all 3-number combinations with 174 tickets. Rather,
>you can only insure that you will match at least 3 numbers out of any given 6.
What is the difference? Am I missing something here. In order to
"match at least 3 numbers out of any given 6" you would need to cover
every 3-number conbination.
Bruce Kaskel
Eric Montagnino <emo...@shadow.net> wrote:
>kas...@seastar.berkeley.edu (Bruce Kaskel) wrote:
>>This is not the same as the 174 ticket challenge. In that case, you can't
>>have 100% coverage of all 3-number combinations with 174 tickets. Rather,
>>you can only insure that you will match at least 3 numbers out of any given 6.
>
>What is the difference? Am I missing something here. In order to
>"match at least 3 numbers out of any given 6" you would need to cover
>every 3-number conbination.
>
Yes, you are missing something.
Take a simple case: A lottery which chooses 6 numbers out of 9. Then if
you buy ANY one ticket, say [1,2,3,4,5,6], you will be guaranteed a 3/6 win.
But this ticket does not cover every 3-number combination. In fact, it
doesn't cover any 3-number combination containing a 7, 8 or 9.
--Bruce Kaskel
Normand Veilleux
>From: kas...@kirkuk.berkeley.edu (Bruce Kaskel)
>>From: Eric Montagnino <emo...@shadow.net>:
>>From: kas...@seastar.berkeley.edu (Bruce Kaskel):
>>>This is not the same as the 174 ticket challenge. In that case, you can't
>>>have 100% coverage of all 3-number combinations with 174 tickets. Rather,
>>>you can only insure that you will match at least 3 numbers out of any given 6.
>>
>>What is the difference? Am I missing something here. In order to
>>"match at least 3 numbers out of any given 6" you would need to cover
>>every 3-number conbination.
>>
>
>Yes, you are missing something.
>Take a simple case: A lottery which chooses 6 numbers out of 9. Then if
>you buy ANY one ticket, say [1,2,3,4,5,6], you will be guaranteed a 3/6 win.
>But this ticket does not cover every 3-number combination. In fact, it
>doesn't cover any 3-number combination containing a 7, 8 or 9.
Another way to look at it too is that in the case of a Lotto 6/49
the 6 draw numbers form 20 different triples. So, if you are trying
to produce a wheel that matches every triple, then your wheel will
have to match all of those 20 triples. That is what is referred to
as a 3 on 3 system. Because if the draw only had 3 numbers instead
of 6, your wheel would still get a winner (a 3 on 3).
The 174 ticket wheel is a 3 on 6 system. It means that if the draw
has 6 numbers (like in the Lotto 6/49) one the tickets will match
3 of those 6. In other words, in the worse possible case we only
match one of the 20 triples formed by the 6 draw numbers. This is
a lot less expensive than a 3 on 3 system.
BTW, 3 on 6 means that 3 numbers on a ticket matched the 6 draw
numbers. So, if a lottery was setup to draw 6 numbers, but that the
tickets sold only contained 5 numbers, you could still build a 3 on
6 wheel. Obviously, it would require more tickets since each ticket
now only covers 10 triplets instead of 20.
Hope your not more confused! :)
Eric Montagnino
>>What is the difference? Am I missing something here. In order to
>>"match at least 3 numbers out of any given 6" you would need to cover
>>every 3-number conbination.
>>
>Yes, you are missing something.
>Take a simple case: A lottery which chooses 6 numbers out of 9. Then if
>you buy ANY one ticket, say [1,2,3,4,5,6], you will be guaranteed a 3/6 win.
>But this ticket does not cover every 3-number combination. In fact, it
>doesn't cover any 3-number combination containing a 7, 8 or 9.
OK I am awake now :)
Thanks.