Ana səhifə

Betting Wheels, Lotteries & Lotto Designs

Yüklə 65.5 Kb.
ölçüsü65.5 Kb.
Betting Wheels, Lotteries & Lotto Designs


G.H.J. van Rees

1 Introduction

2 Scope of Problem

3 Applications

4 History

5 Constructions

6 Algorithms

How to Run a Lottery

1. Betters buy a ticket i.e. choose k numbers from n numbers

2. After sales are closed, the gov’t randomly chooses p numbers from the n numbers.

3. If the better gets exactly t of the gov’t’s numbers correct, then better wins the t prize.

4. The larger t is the more the better wins.

5. Never give out as much money as you take in.

The best strategy for a better-

Don’t bet.

The Question
How many tickets must I buy to guarantee winning the t prize?
A lot of people are interested in this question: betters, governments, web sites, salesman of lottery wheels.
This number is called: L(n,k,p,t).

For lotto 6-49, the number is L(49,6,6,t) or if you count the bonus ball - L(49,6,7,t)

This talk will not be about increasing your expected gain.
Definition: L(n,k,p,t) is the minimum number of k-subsets (or blocks) of a n-set that are needed to ensure that any p-subset of the n-set intersects one of the blocks in at least t elements.

Definition: LD(n,k,p,t;b) is a lotto design on b blocks in

which any p-subset of the n-set intersects one of the blocks of size k in at least t elements.

Definition: LD*(n,k,p,t;b) is a lotto design in which b=L(n,k,p,t).

The following is an LD(7,3,4,2;3):

{ { 1,2,3 },

{ 3,4,5 },

{ 5,6,7} }

The following is an LD*(7,3,4,2;3):

{ { 1,2,3 },

{4,5,6 } }
Big Example; LD(20,10,6,4;6)
{ { 1, 3, 5, 6, 7,10,11,12,13,14 },

{ 2, 4, 5, 6, 7, 8, 9,10,12,15 },

{ 1, 2, 3, 4, 8, 9,11,13,14,15 },

{ 3, 5, 6,10,12,16,17,18,19,20 },

{ 1, 7, 9,11,14,16,17,18,19,20 },

{ 2, 4, 8,13,15,16,17,18,19,20 } }

Check every 10-set yourself. Trust no one!

Some of lotto numbers are easy to calculate.

L(49,6,6,1)= ,
L(n,k,p,1) = .
In the Hungarian Lottery L(90,5,5,2) = 100 is of interest. This is not easy, but it has been proved.
We can get an upper bound by noticing the construction that gives:

L(49,6,6,3)  L(22,6,3,3) + L(27,6,4,3)  77+86 = 163.

Proof: Take any p=6-set out of the 49 elements. Either there are at least 3 elements from the 22 elements and we have one of the 77 blocks intersecting the 6-set in at least three elements or there are at least 4 elements from the 27 elements and there is a block intersecting the 6-set in at least 3 elements.
Now LD*(22,6,3,3;77) is a well-known combinatorial design and you could not get a better lotto design.
Whereas LD(27,6,4,3;86) was found by a computer program using a simulated annealing algorithm. It can probably be improved.
But even if LD(27,6,4,3;86) was the best you could do, there may be better ways to split the 49 elements or better different constructions.
So we know that:

87  L(49,6,6 ,3)  163. Still a big gap.

But why are there brazillions of web sites on this topic?
In the advanced lotto countries of this world (not Canada), people are given the choice of betting an LD(n,k,p,t;b), for various parameters and small n. It encourages the better to know that b is absolutely as small as possible.
Betters also believe in “their lucky numbers”. So if the gov’t picks p numbers that include r of the better’s v lucky numbers, he wants to buy tickets that guarantee the t prize. This would be an LD(v,k,t,t). These lottery wheels are sold in Australia and elsewhere. Some lotteries will provide the wheels for free and let you bet them with one super ticket that costs $L(v,k,t,t).

Other Applications

When p=t, this lotto problem becomes a classic problem called covering design problem. It has been much studied and has many applications. The main other ones are error-trapping decoding of error-correcting codes, data compression, covering codes
Research Approach

Theory – Recursive – Constructions

Programming – lower bound – backtracking

= Tables

Lots of stuff on L(n,k,t,t) then and now

Bate and Brouwer in 1978 - easy stuff – L(n,3,3,2) 
Furedi – 1996 – t=2 – graph theory like
Hartmann – 1997 – theory of lower bounds
Bate & van Rees –1998- L(49,6,6,2)=19. Structure
Bluskov – 99,02 – heuristic algorithms
Li & van Rees – 1999,00,02,06 – lower bounds, constructions, heuristic algorithms, frequency analysis and tables
South Africans – 05,06 - small designs
Lutful & van Rees -06?– small designs
Li & Toulouse – 05- heuristic parallel algorithms for L(n,k,t,t)

Lots and lots of work left to be done.


Bound:  L(n,k,p,t) 

Proof: L(n,k,p,t) 
Proof: L(5,4,3,2)  =5
12,34,13,25,14,35,15,24,23,45 are all the 2-sets

1234, 1325, 1435, 1524, 2345 are 5 4-sets holding all the 2-sets. I claim this is a LD(5,4,3,2;5). Take any 3-set {1,2,3} and find a 2-set in it, say 23. 23 is in block 5.

This is trivial to generalize. 

Bound: L(n,k,p,t) 

Proof: L(7,4,5,3)( ) 

Every block of size 4 is represents = 15 5-sets.

1234 represents 12356, 12367, 12357

12456, 12467, 12457

13456, 13467, 13457

23456, 23467, 23457

12345, 12346, 12347

So the minimum number of blocks times the number represented must be at least as big as the number of 5-sets.

L(7,4,5,3)  3.

This is easy to generalize. 

Complements: L(n,k,p,t) = L(n,n-k,n-p, n-k-p+t)
Proof: Take an LD(n,k,p,t) and complement each block and check. 

Note that this cuts the tables in half.

Theorem (S.A.)

L(n,k,p,t) = 2 iff 2t-1+max{n-2k,0}pn+t-k+1

L(n,k,p,t) = 3 iff p  min{2t-2+max{n-2k,0},n-k+t-1} and

t 3k-2+max{m-3n,o}, if m  2n,

t (3/2)k-1+max{m-(3/2)n,0}, if m < 2n.

Since the most frequent numbers are 1, 2 and 3 we no longer have to write down those parts of the tables.

Monotinicity(Li & van Rees)(easy)

L(n,k,p,t) increases or stays the same as

n increases

t increases

k decreases

p decreases

n and t decrease

n and p decrease

t and k increase

t and p increase

n and k and p and t increase
What about t,k,p all increasing? Sometimes increase
Theorem(Li) Generalized Schonheim

L(n,k,p,t) 

This bound is good for L(n,k,p,t) when k=t or p=t in the complement. These are the classic cases and there the bound is called the Schonheim bound. Unfortunately as k-t or p-t gets large the bound is not much use.
Theorem (Construction)

Let n=n1+n2 and p=p1+p2-1,

L(n,k,p,t)  L(n1,k,p1,t) + L(n2,k,p2,t) Seen it earlier

Theorem (Construction)

L(n+1,k+1,p+1,t+1)  L(n,k,p,t) + L(n,k+1,p+1,t+1).
Proof by picture.


Let n, k, p, t, n1, k1,and r be integers so that n1 < n, p-rt, k1t-r-1 and k1 = k-n +n1. Then

L(n,k,p,t)  L(n1,k,p-r,t) + L(n1, k1, p-r-1,t-r-1).

Proof: Exercise

We need the theory to tell us as much about what the design looks like so we can fine tune our algorithms.

Lower Bounds

1. Backtracking : Even with early isomorphism rejection, frequency analysis and precomputing, this needs to be done in parallel.

Upper Bounds (Heuristics)(Bluskov, Finns)

1. Simulated Annealing – Bounce off the walls for a while and then settle down.

2. Tabu Search – Don’t look where you just looked.
3. Co-operative Multi-Level Search (Li & Toulouse 2005)

25 new and improved small L(n,k,t,t) numbers. These are the classic numbers that have received a lot of attention. So I consider this an important achievement. This is parallel work where the computers co-operate and communicate with each other. Further, they coarsen the search space to make it smaller and then take the solutions (approximations) they find back to the original search space and then search there. They may iterate this many times.


For more details and references see:
1. P.C. Li & G.H.J. van Rees, Lotto Designs, a section in The CRC Handbook of Combinatorial Designs, Editors – C.J. Colbourn & J.H. Dinitz Boca Raton, CRC Press, (2006) 10 pages ----appearing soon in a bookstore near you.
This reference and the talk is on my web site.

- -

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur © 2016
rəhbərliyinə müraciət