Abstract
An ( n, k, p, t) lotto design is a set of k sets (called blocks) of an n set such
that any p set intersects at least one block in at least t points. We will
denote the minimal number of blocks needed to make an (n, k,p, t) lotto
design by L(n, k, p, t). This paper lists a few known theorems for upper and
lower bounds for lotto designs. We then apply these theorems to the New
Zealand lotto system and calculate upper and lower bounds for each of the
six divisions of the New Zealand system.
Lotteries are a common form of gambling. Generally they work by bettors
choosing tickets with k numbers on them between 1 and n. The house then
draws p random numbers between 1 and n. If a bettor has t or more numbers
that are drawn on their ticket, then they win a prize. Usually for the lower
values of t, the bettor wins a fixed amount of money. While for the larger
values of t the bettor wins a share of the prize, depending on the number of
other people who had the same number of numbers drawn on their tickets.
The prize for having all k of your numbers being drawn is almost always
a large sum of money. Because of this, everybody wants to win. There are
numerous systems out there all claiming to increase your chances at winning.
Some of these systems are based on lotto designs. The focus of this paper
will be on lotto designs, and how they can/can not help us win the lottery.
Chapter 2 will cover the basic definitions and ideas of lotto designs. This
will include a number of theorems and their proofs. In the second part of
chapter 2 will look at a few algorithms used to construct lotto designs.
The most common lottery in New Zealand is Lotto, run by the New Zealand
Lotteries Commission. In chapter 3 we will be trying to apply the theorems
and constructions in chapter 2 to the NZ lotto system. Our main focus will
be trying to construct upper and lower bounds for the number of tickets
needed to guarantee winning each of the six divisions of Lotto.
2
CHAPTER 2
Lotto, and other Designs
2.1 Lotto Designs
To begin with we will need a few definitions. We will begin with some basic
combinatorics definitions, then move onto definitions used in making lotto
designs.
Note: throughout this paper we will be referring top sets, k sets, etc. These
are just sets with p or k points in them respectively.
Definition 2.1. A combinatorial design is a pair (P, B), where B is a non-
empty set of blocks made up of elements called points from a set P.
Definition 2.2. At- (n, k, A) design is a combinatorial design such that P
has n points in it, every block in B has exactly k points, and such that every
t element subset of P is contained in exactly A blocks.
The invitation problem is a common combinatorial problem solved using com-
binatorial designs. The idea is to invite n friends to dinner, k at a time in
such a fashion that everybody has dinner with everybody else at least once.
Example 2.3. The invitation problem for inviting 7 friends to dinner, 3 at a
time can be represented by a 2- (7, 3, 1) design. In the case of this example
P = {1, 2, 3, 4, 5, 6, 7}, and the blocks of Bare:
{1,2,3}, {1,4,5}, {1,6, 7}, {2,4,6}, {2,5, 7}, {3,4, 7}, {3,5,6}.
Definition 2.4. An (n, k,p, t) lotto design is a set of blocks each consisting
of k points from an n set such that every p set intersects a block in at least
t points. We will denote the minimal number of blocks an ( n, k, p, t) lotto
design can have by L(n,k,p,t).
Example 2.3 is an example of an (7, 3, 2, 2) lotto design. A special case of
lotto designs is when you have a (n, k, k, k) lotto design. In this case the lotto
design has to include every k subset of the set n. This makes L(n, k, k, k)
very easy to calculate. It is just ( ~ ) .
Example 2.5. A (12,4,6,3) lotto design (on the set N = {1, .. , 12}) is given
by the following 8 blocks:
{1,2,3,4},{1,5,6,7},{2,3,4,5},{2,3,4,6},{8,9, 10, 11},{8,9,10,12},
{8,9,11,12},{8,10,11,12}.
3
CHAPTER 2. LOTTO, AND OTHER DESIGNS 4
If we take any random 6 set A, then there is a block B such that IAn B I
~
3.
For example, if A = {1, 4, 5, 7, 8, 10}, then B = {1, 5, 6, 7}. If we take the
intersection of these two sets, then we get {1, 4, 5, 7, 8, 10} n {1, 5, 6, 7} =
{1, 5, 7}.
It is very important to note that while it seems lotto designs give you an
advantage this is not true. They do not improve the expected return on
each ticket. However, they do increase your odds of winning something small
instead of winning nothing at all.
There are two important subclasses of lotto designs. These are covering
designs, and Tunin designs. A (n, k, t) covering design is a design such that
choosing blocks of k points from a set of n points, any subset of t points is
contained in one of those blocks. In terms of lotto designs, a covering design
is an (n, k, t, t) lotto design. Any t- (n, k, 1) design is a covering design. We
will denote the minimal number of blocks in a (n, k, t) covering design by
C(n, k, t)
A ( n, p, t) Tunin design is a design with blocks of k points chosen from a
set of n points where any arbitrary subset of p points will contain at least
one block of the design. A Tunin design is an ( n, t, p, t) lotto design. The
minimal number of blocks in a Tunin design will be denoted by T( n, p, t).
Both covering and Turan designs have been studied to a great extent as stand
alone designs, and many papers have been written about them, see [4].
Covering and Turan designs are closely related as theorem 2.6 will show us.
Theorem 2.6. The complement of a Turim design is a covering design,
and the complement of a covering design is a Turim design. Consequently
T(n,p, t) = C(n, n- t, n- p).
Proof. We will denote the set {1, .. , n} by N. Remember that a 1\1ran design
is a L(n, t,p, t) design, so any p-set will contain a k set oft= k elements of
the Turan design. This can be seen in fig 2.1 where the k set B is shown in
green, the p set A is shown in purple, and everything else is grey.
CB c:
A
Figure 2.1: A block of a Turan design
If we take the complement of these sets we will get something that looks like
fig 2.2, where B' = N\A, and A'= N\B. In this figure then- p set B' is
CHAPTER 2. LOTTO, AND OTHER DESIGNS 5
shown in green, the n - t set A' is shown in purple, and everything else is
grey.
A' C <
Figure 2.2: The complement of a block of a Tunin design.
Take any n- p set B' in the N, then there is a corresponding p set N\ B' = A.
In the original Tunin design there is a block B contained in A. Since A ;2 B,
we can conclude
B' = N\A
~
N\B = A'.
This works for any n- p set B' you could choose, so we have for any n - p set
B' there is an-t block A' that contains it. Therefore we have a (n, n-t, n-p)
covering design. This shows us that the complement of a Turan design is a
covering design and thus T(n,p, t) ::; C(n, n - t, n- p). Using a similar
argument, working backwards it can be shown that T(n,p, t) > C(n, n-
t, n- p). Therefore T(n,p, t) = C(n, n- t, n- p).
D
It is often computationally difficult to construct large lotto designs. As the
size of n increases, the size of the corresponding lotto design increases rapidly.
Often it is better to construct upp er and lower bounds for our desired lotto
designs first. This approach allows us to find out whether our lotto design
will be practical without calculating the actua l lotto design. Once we have
done this, if the design could be practical, we can then go about constructing
the desired design. Doing this can save us a lot of time. Presented below
are a number of theorems used to calculate upper and lower bounds for lotto
designs. This is by no means a complete list, there are many more theorems
out there that can be used to calculate lower and upper bounds for lotto
designs, see [3] pages 578-584, [7], [8] and [9].
Theorem 2. 7. If n = n 1 + n 2 , and p = p 1 + p 2 - 1, then L(n, k,p, t) ::;
L(n1, k,p 1 , t) + L(n 2 , k,p 2 , t).
Proof. To show that this is true we will show that if you take any (n 1 , k,p 1 , t)
and (n 2 , k,p 2 , t) lotto designs on disjoint sets, then when we combine them
we have an (n, k,p, t) lotto design. This situation can be shown by fig 2.3,
CHAPTER 2. LOTTO, AND OTHER DESIGNS 6
where the sets PI and p 2 are in purple and the blocks BI and B 2 are in blue.
In the figure, either ti 2': t or t 2 2': t (or both) .
Figure 2.3:
Let N = {1, .. , n}, NI = {1, .. , ni} and N 2 = {ni + 1, .. , n}. Also let B =
BI U 8 2 , where BI is the set of blocks of an (ni, k,pi, t) lotto design on NI
and 8 2 is the sets of blocks of an (n 2 , k,p 2 , t) lotto design on N 2 . We will
show that (N , B) is an (n , k,p, t) lotto design on N. Take any p set
A
~
N.
Either lA n Nil 2': PI, or lA n N 2 1 2': p 2 . Otherwise we would have
This is a contradiction because IAI = p. If lA n Nil 2': PI, then there is a
block BI
~
BI such that IAnBII 2': ti. If IAnB 2 12': p 2 , then there is a block
B 2
~
B 2 such that lA n N 2 1 2': t 2 . Either way there is a block B
~
B such
that IE n AI 2': t. Therefore we have an (n , k,p, t) lotto design.
0
Example 2.8. Say we are wanting to find an upper bound for L(27, 6, 8, 3).
Using theorem 2.3 we know
L(27, 6, 8, 3) :::; L(15, 6, 4, 3) + L(12, 6, 5, 3).
From the tables in [6] we know that L(12, 6, 5, 3) = 2, and L(15, 6, 4, 3) :::; 14.
This gives us
L(27, 6, 8, 3) :::; L(15, 6, 4, 3) + L(12, 6, 5, 3) :::; 14 + 2 = 16.
Th
' 2 9 T( t) > ( ~ ) n-p+I
eorem . . n,p, _ (p-1) · n-t+I.
t-1
Proof. This is just a rewording of the proof from [2]. To start off we show
that:
G) n - p + 1 n - p + 1 ( n )
( ~: =i ) . n- t + 1 = t ( ~ : = i ) · t- 1 ·
This is relatively straightforward, and goes as follows.
CHAPTER 2. LOTTO, AND OTHER DESIGNS 7
(;) n- p + 1 n!/((n-t)!·t!) n-p+1
( P- 1 ) . n-
t + 1
t-1
(p- 1)!/((p- t)! · (t- 1)!) · n- t + 1
n! · (p- t)! · (t- 1)! n- p + 1
(n- t)! · t! · (p- 1)! . n- t + 1
n! (p- t)! · (t- 1)!
( n t + 1) ! · ( t - 1)! · t · (p - 1) ! · ( n - P +
1 )
( t ~ 1 ) 1 ( )
-t- . (p-1) . n - p + 1
t-1
= ~ ~ ( ~ = 1 ) 1 . c : 1)
Let H be a collection oft subsets of the set N = { 1, .. , n}. We will define mp
to be the number of distinct collections of all possible t subsets of p subsets
of N such that every t set in the collection is contained in H. That is, if G is
such a collection, then there exists a p set such that every possible t subset
of the p set is a t set in H. The collection G would be all the t subsets of the
p set. Note that mt is just !HI, and that mt- 1 is just ( t ~ J Now, theorem 1
from [2] states that
p 2 . mp ( mp ( t - 1) ( n - p) + p)
m + 1 > -- - -'---.:__:_-:::------'-----
P - (p - t + 1) (p + 1) mp- 1 p 2 '
whenever mp_ 1 =I- 0. Let
_ ( ~ = i ) ( n - t + 1 ) - ( n - p + 1 ) ( n)
F(n, p, t) - t(p-1) t- 1 .
t-1
It can be shown through long and tedious, but simple calculations that
(t- 1)(n- p) + p ( n )
F(n,p + 1, t) = F(n,p, t) +
t
2
( ~ ) t _
1
We will now prove by induction on p that
t2 ( ~ )
mp ?: mp-1
2 (
n ) ( mt - F ( n, p, t))
p t-1
(2.1)
(2.2)
(2.3)
when p = t the theorem does not apply because mt_ 2 = 0. When p = t + 1,
from (2.1) we have
mt+I > t
2 mt
(mt _ ( t - 1) ( n - p) + p ( n ) )
(t+1)mt-1 t 2 t-1
t2 c ~ 1 )
mt( ) 2 (n)(mt-F(n,t+1,t)).
t + 1 t-1
CHAPTER 2. LOTTO, AND OTHER DESIGNS 8
This proves the case p = t+ 1. From this we also see that mt+l > 0 whenever
m > (t-l)(n-t)+t ( n )
t t2 t-1 .
Now, if p > t + 1 then we have
by(2.1)
induction(2.3) >
by(2.2)
This proves (2.3). It follows from (2.3) that mp > 0 whenever mt > F(n,p, t).
In other words, H contains all t subsets of some p subset of N if !HI >
F(n,p, t). Let N(t) be the set of all possible t subsets of the set N. The
collection of sets H = N(t\H will have a p subset which does not contain
any t subset from H if !HI is strictly less then (7) - F(n,p, t). Therefore
T n t > (n) - F n t = ( n - p + 1) ( n ) = J:;)_ . n - p + 1
( ,p, )_ t ( ,p,) t ( ~ = D t 1 ( ~ = ~ ) n-t+1'
The next theorem is useful for creating lower bounds for lotto designs. The
lower bounds in chapter 3 where calculated using theorem 2.9 with the fol-
lowing theorem.
Theorem 2.10. L(n, k,p, t) 2:: T ( ( ~ ) , t )
Proof. This can be rewritten as L( n, k, p, t) (;) 2:: T( n, p, t). Take a ( n, k, p, t)
lotto design with L(n, k,p, t) blocks. Any p set will have at least t points in a
k block. If we take every k block and replace it with (;) blocks corresponding
to all different combinations of t points made up from the k points in that
block, then we will have at most L(n, k,p, t)(;) blocks. Now take any p set,
then there is a block in the original design that covered at least t points from
this set. This set of t points is a possible combination of t points made from
the k points of the block. Therefore there is a block of t points in the new
design that contains these t points. That is, those t points form a block of the
new design. This gives us a (n,t,p,t) lotto design, that is a (n,p,t) Tunin
design. Therefore L(n,k,p,t);:::: r ( ( ~ r l · o
CHAPTER 2. LOTTO, AND OTHER DESIGNS
Theorem 2.11. Let p = T(t- 1) + 1 + v where 0::::; v::::; t- 1, then
T
L(n, k,p, t) ::::; minn-v=l:[=
1 CTi L C((Ji, k, t).
i=l
9
Before we provide a proof of this it would be a good idea to. explain a little
more about what this theorem is saying. In its current form it is a bit
confusing. It simply states that given T suitable coverings on disjoint sets,
if we form the union of all the blocks of each covering design we get an
(n, k,p, t) lotto design. The minimum is taken over all possible combinations
of (Ji· We try all possible combinations of (Ji and find the one that gives the
minimum sum. Figure 2.4 may make things clearer, we can see the set N
partitioned into T disjoint sets each with a covering on them plus the set of
v points which is disjoint from the other sets.
Figure 2.4: (n, k,p, t) = U[ = 1 ((Ji, k, t)
Now that we understand what is going on, we can provide a proof.
Proof. To prove this we need to show that if we have the union of ((Ji, k, t)
coverings on disjoint sets such that L:=T =l (Ji + v = n, then we also have a
(n, k,p, t) lotto design. Suppose we have T suitable coverings on T disjoint
sets Ni for 1 ::::; i ::::; T and the set N 0 = {1, .. , v} which is disjoint to all Ni.
Let Bi be the collection of blocks of covering ((Ji, k, t) on the set Ni. Given
any arbitrary p subset A of the set N = U[ =oNi, we will show that there is a
block E in one of the covering designs such that IE n A I 2:: t.
Let p = L:=T =oPi, where A= An Ni and Pi= I Ni n AI. Now suppose there
is no block E in the union of covering designs such that IE n AI ;=::: t; in other
words Pi ::::; t- 1 for all1 ::::; i ::::; T. Then we would have
IAI ::::; T(t- 1) + v = p- 1.
This is a contradiction because IAI = p. Therefore there exists ani such that
Pi 2:: t, and consequently there is a block E
~
Bi such that IE n AI 2:: t. This
holds for any arbitrary p set A
~
N. Therefore we have an (n, k,p, t) lotto
design.
CHAPTER 2. LOTTO, AND OTHER DESIGNS 10
This applies to any arbitrary set of coverings that satisfy the theorems con-
ditions. This includes the smallest possible coverings that satisfy these con-
ditions. Therefore
T
L(n, k, p, t) ~ minn-v=L:[= 1
D
Example 2.12. If we want to find an upper bound for L(40, 6, 14, 4), then
we can use theorem 2.11. To do so, we would do the following:
14 = T(3) + 1 + 'U :::} T = 4, 'U = 1.
This gives us
4
£(40,6,14,4) ~ LCki,6,4),
i=l
where I:,i=l (Ji = 39. Looking up the tables in [4] we see that in this case the
sum is minimal when
(Jl (Jz = (J3 = 10, and (J4 = 9
(or some similar permutation of this). The upper bounds for 0(10,6,4)
and C(9, 6, 4) are 20 and 12 respectively [4]. Therefore L( 40, 6, 14, 4) <
3. 20 + 12 72.
Theorem 2.13. Let n = n 1 + n 2 , 0
~
s
~
t and s
~
l
~
k t + s. Then
t
C(n, k, t) ~ L m/n C(n 1 , l, s) · C(nz, k -l, t- s).
s=O
Proof. Let N 1 = {1, .. , n 1 } and Nz = {n 1 + 1, .. , n 2 }. Let Bl,s be the set of
blocks you get when for each block of a ( n 1 , l, s) covering design and each
block of a ( n 2 , k - l, t - s) covering design we take the union of these two
blocks. Do this for all possible values of lands. Choose an arbitrary p = t set
A
~
N = {1, .. , n} and let A 1 = AnN 1 and A 2 = AnNz. Since IA1 UAzl = t
we know that there is a set of blocks B 1 ,A 1 for each possible value of l. The set
Bl,A 1 is made from joining all blocks from the (n 1 , l, A 1 ) covering design with
all blocks from the ( n 2 , k -l, t- A 1 ) covering design. Because of this, there is
a block B
~
B1,A 1 such that B = B1UBz, IA1nB1I =sand IA 2 nBzl t-s.
When we form the union of B 1 , and B 2 we see that
lA n (Bl u Bz)l = I(Al n Bl) u (Az n Bz)l = (s + (t- s)) = t.
Therefore, for any arbitrary p = t set A we could choose there is a block
B such that IE n AI = t. So we have a (n, k, t) covering design. So given
CHAPTER 2. LOTTO, AND OTHER DESIGNS 11
any collection of coverings of the form ( n 1 , l, s), and ( n 2 , k - l, t - s) for all
possible values of l, and s we can form a (n, k, t) covering design.
This includes the coverings that give us the minimum value for the sum of
the products of their size. The minimal number of blocks in this covering
design is given by:
Therefore
C(v 1 , l, 0) · C(v 2 , k -l, t)
+ C ( V 1 , l, 1) · C ( Vz, k - l, t - 1)
+ C ( V 1 , l, t - 1) · C ( Vz, k - l, 1)
+ C(v 1 , l, t) · C(v 2 , k -l, 0)
t
C(n, k, t)::; L min C(v1, l, s) · C(vz, k -l, t- s).
s=O
D
We can try different variations of n 1 and n 2 to get a better upper bound.
One thing to note is that if a + b = n, then trying n 1 = a and n 2 = b will
give us the same result as n 1 = b and n 2 = a.
2.2 Algorithms for Constructing Lotto De-
.
signs
There are three main types of algorithms used to construct lotto designs.
They are greedy algorithms, backtracking, and simulated annealing. Due to
space constraints, we will only briefly discus each type of algorithm. During
the writing of this paper a greedy algorithm was written and implemented.
2.2.1 Greedy Algorithms
Greedy algorithms are the simplest algorithms for finding lotto designs. They
are very easy to program. However, they usually don't find optimal solutions.
The way a greedy a.lgorithm works is by finding a feasible solution by choos-
ing the best option at each step. So for a lotto design, at each step the
a.lgorithm would choose the ticket that covers the most p sets that are so far
not covered by any other ticket. Presented below is some basic pseudo code
for a greedy lotto design algorithm.
CHAPTER 2. LOTTO, AND OTHER DESIGNS
Greedy(P)
Input: P = [Po, PI, ... , Pm],profit function
Output: X= [x 0 , xi, ... , x 1 ], a subset of P
Profit = 0
X=0
foreach Pi E P do
if profit(pi) >Profit then
I
Point= Pi
Profit = profit(pi)
end
end
P +-- P\Point.
X+-- XU Point
Greedy(P)
Algorithm 1: Pseudo Code for a Greedy Algorithm
12
In this code the set P is the set of all the possible k sets for the lotto design
and the profit function is the number of uncovered p sets each k set covers. As
the code runs, it finds the k set (called Point) that covers the most uncovered
p sets, it then adds it to the set X, then runs again with the set P\Point and
a new profit function. It will keep doing this until all the p sets have been
covered. In the appendix is a greedy algorithm written in Maple.
2.2.2 Backtracking Algorithms
Backtracking is an exhaustive search method, it considers every feasible so-
lution. Because of this, it will always find an optimal solution. The draw
back of this is that it consumes large amounts of memory, and can take a
long time to run. Certain methods called pruning methods can be used to
decrease the workload. Presented below is some pseudo code based on the
code from [5], pg 107 for a general backtracking algorithm. P is called the
possibility set, it is made up of all the possible solutions the problem could
have. In the case of a lotto design it is made up of all possible tickets. For
each partial solution X = [x 0 , X1, ... , Xz-I] there is a choice set C 1 <;;:; Pi that
contains all feasible points from Pi given that X = [x 0 , XI, .. , xz_I]. Using
the choice set is one pruning method because at each step, you don't have
to consider all of the xi's remaining. You just consider the xi E C 1 •
CHAPTER 2. LOTTO, AND OTHER DESIGNS
BACKTRACK( l)
Input: x, constraints
Output: X
if [x 0 , x 1 , ... ] is a feasible solution then
I process it
end
compute Ct
foreach X E C1 do
I
Xt +-----X,
BACKTRACK(l+ 1)
end
Algorithm 2: Pseudo Code for a. Backtracking Algorithm
13
To start off, l = 0, and X = 0. The basic idea of the algorithm is if X is
a feasible solution then the process command checks if it is better then the
current best solution, and saves it if it is. If it is not a feasible solution it
creates new solutions by adding each x from the choice set to the current
partial solution X and runs the algorithm again with the new X. Once it
has gone through all possible solutions it outputs the current best solution
X.
2.2.3 Simulated Annealing
Simulated Annealing is a modified version of Hill-climbing. The way hill-
climbing algorithms work is they start with a. feasible solution and try to
improve it to get an optimal solution. The way this is done is by taking the
current solution and looking a.t the solutions in its neighborhood, checking to
see if any of these solutions are better. The neighborhood of a solution is
all the different solutions possible by slightly changing the current solution.
The problem with hill-climbing is that is can get stuck a.t a. local maximum.
This will happen if the current solution is better then all other solutions in
its neighborhood.
Simulated annealing is a way of getting round this problem. In simulated an-
nealing even if the solution being checked is worse then the current one there
is a. probability that this solution will be still accepted. This is how simulated
annealing avoids getting stuck at local maximums. The probability that a
solution is chosen despite not being as good as the current solution is often
referred to as the temperature, and denoted by T. As the algorithm runs,
the temperature T decreases. Usually simulated annealing will run until it
reaches its iteration limit, at which point the current solution is outputted.
Below is some pseudo code for simulated annealing. In the code N(X) per-
forms a neighborhood search and chooses a random neighbor of X. It returns
fail if, then there are no points in the neighborhood of X.
CHAPTER 2. LOTTO, AND OTHER DESIGNS
Annealing(cmax, To, a, X)
Input: Cmax, To, a, X
Output: Xbest
c=O
T=To
Xbest =X
while C ::::; Cmax do
Y = N(X)
if Y :f Fail then
if P(Y) > P(X) then
X=Y
if P(X) > P(Xbest) then
I Xbest =X
end
else
r = Random(O, 1)
if r < e(P(Y)-P(X))/T then
I X=Y
end
end
end
c=c+1
T=aT
end
return Xbest
Algorithm 3: Pseudo Code for a Simulated Annealing Algorithm
14
In the algorithm c records the number of iterations and Cmax is the maximum
number of iterations. the algorithm starts off with a feasible solution X it
checks a random feasible solution from the current solution's neighborhood.
If this solution is better then the current one then it becomes the current
solution. If not, then it chooses a random number between 0 and 1. If
this number is less then e(P(Y)-P(X))/T then it becomes the current solution
anyway. At the end of each iteration the temperature T is decreased by a
factor of a. Once it reaches its iteration limit it outputs the current best
solution.
CHAPTER 3
Lotto Designs on the NZ Lotto
System
3.1 The NZ Lottery
In the NZ lotto system there are 40 balls and 6 are chosen at random. After
this a final bonus ball is chosen at random from the remaining 34 numbers.
Below is a table of the possible winning tickets and how much you can expect
to win
1 .
For more information see [1]
Number of Bonus Average Corresponding
Winning Numbers Ball Winnings Lotto Design
Division 1 6 No $833,333 (40,6,6,6)
Division 2 5 Yes $27,587 (40,6,7,6)
Division 3 5 No $699 (40,6,6,5)
Division 4 4 Yes $64 (40,6,7,5)
Division 5 4 No $34 (40,6,6,4)
Division 6 3 Yes $24 (40,6,7,4)
We want to be able to construct lotto designs corresponding to these six
divisions. The obvious goal is be able to construct a lotto design for one (or
more) of these divisions such that the amount of money required to buy all
the tickets in the design is less then the amount of money we can expect to
win.
The first step is to calculate upper and lower bounds for these divisions.
Calculating upper and lower bounds for a design is much easier to do then
to calculate the actual lotto design. If we discover that the lower bound for
a lotto design is greater the maximum number of tickets we can by and still
make a profit, then there is no point in trying to construct that lotto design.
Using proposition 2.9 and theorem 2.10 we can construct lower bounds for
the NZ lotto system. With the power ball we have:
62145 :::::
T(40,7,6)
::; L(40, 6, 7, 6)
m
6906 :::::
T(40,7,5)
::; L(40, 6, 7, 5)
m
280 :::::
T(40,7,4)
::; L(40,6, 7,4)
m
1 Based on the lotto draws over the last 10 weeks
15
CHAPTER 3. LOTTO DESIGNS ON THE NZ LOTTO SYSTEM 16
And without making use of the power ball we have:
3838380 ::::;
T(40,6,6)
::::; L(40,6,6,6)
m
21325 ::::;
T(40,6,5)
::::; 1(40,6,6,5)
m
433::::;
T(40,6,4)
::::; 1(40, 6, 6, 4)
m
Unfortunately, now that we have calculated lower bounds for all six divisions
we see that no possible lotto design could guarantee us a profit, as the table
below shows. This table is just for the lower bounds, the actual designs could
cost us a lot more.
Cost Guaranteed Average Winnings Profit
Division 1 $2,303,028 $833,333 -$1,469,695
Division 2 $37,287 $27,587 -$9,700
Division 3 $12, 795 $699 -$12,096
Division 4 $4,143.6 $64 -$4,079.6
Division 5 $259.8 $34 -$225.8
Division 6 $168 $24 -$144
Even though none of these lotto designs can be of use to us, we would still like
to calculate some upper bounds for them. These are generally a lot trickier
to calculate. We will use a number of different theorems to try to get the
lowest upper bound.
Not all of the cases we are interested in are difficult. The upper bound for
1(40, 6, 6, 6), (which corresponds to winning first division), is very easy to
calculate. To have a ( 40, 6, 6, 6) lotto design, we require that choosing sets of
6, every possible set of 6 is contained in one of the sets we chose. The only
way to achieve this is to choose every possible set of 6. So 1( 40, 6, 6, 6) =
( ~
0
) = 3838380. So the upper bound is (trivially) 3838380. That is,
1( 40, 6, 6, 6) :S; 3838380.
Another easy upper bound is 1( 40, 6, 7, 4), which would guarantee a sixth
division win. Using theorem 2. 7, varying the values of n 1 , and n 2 we get
1(40,6, 7,4)::::; 1(20,6,4,4)+1(20,6,4,4). Onethingtonoteisthat1(40,6,4,4)
is a covering design. This is good because we have access to some good
tables on covering designs in [4]. From the tables in [4] we know that
1(20, 6, 4, 4) ::::; 456. This gives us our second upper bound,
1( 40, 6, 7, 4) ::::; 912.
Now, using theorem 2.11, we know that 1(40, 6, 7, 6) ::::; C(39, 6, 6). Using a
similar argument as we did for 1(40,6,6,6), we deduce that 1(40,6, 7,6)::::;
C(39, 6, 6) = e:) = 3262623. So now we have our third upper bound.
1(40,6, 7,6)::::; 3262623
CHAPTER 3. LOTTO DESIGNS ON THE NZ LOTTO SYSTEM 17
The final three upper bounds require a bit more work. Using theorems 2.11
and 2.13 we can construct upper bounds for the remaining lotto designs,
L(40,6, 7,5), 1(40,6,6,5), and 1(40,6,6,4). These are
1(40,6,7,5) < 105339
1(40,6,6,5) ::::; 123478
1(40,6,6,4) ::::; 7474
There is quits a lot of tedious work involved in these calculations. See the ap-
pendix for an example of the calculations involved in calculating 1( 40, 6, 6, 4).
Now we have complete lower and upper bounds for all six divisions of the
NZ lotto system. With the bonus ball we have:
Division 2 : 62145 ::::; 1(40, 6, 7, 6) ::::; 3262623
Division 4: 6906 ::::; 1(40, 6, 7, 5) ::::; 105339
Division 6: 280 ::::; 1(40,6, 7,4) ::::; 912
And without the bonus ball.
Division 1 : 3838380 ::::; 1( 40, 6, 6, 6) ::::; 3838380
Division 3: 21325 ::::; 1 ( 40, 6, 6, 5) ::::; 123478
Division 5 : 433 ::::; 1(40,6,6,4) ::::; 7474
3.2 Lucky Numbers
Some people foolishly or otherwise think that some numbers are lucky, ie
have more chance of being drawn then regular numbers. If this is the case
then you can drastically reduce the number of tickets needed to get at match.
Of course in these situations you lose the guarantee of getting at match. But
if you believe that the lucky numbers are suitably likely to be drawn then
you can construct lotto designs with a positive expected gain.
Example 3.1. Working with the NZ lotto system, assume that you believe
that 16 out of the 40 numbers are lucky. We will assume that there is a
high enough chance that of the 7 numbers drawn, all of them will come from
these 16 lucky numbers. If these numbers were not lucky, then this would
only happen about 0.06% of the time. To get a 4 match (and hence win sixth
division) we will need an 1(16, 6, 7, 4) lotto design. Using theorem 2.10 (and
theorem 2.9) we can construct a lower bound for this design.
1(16,6,7,4) 2::
T(16, 7, 4)
( ~ )
C:) 16-7 + 1
( ~ ) . ( ~ ) 16 - 4 + 1
1820 10
--·-
300 13
== 5.
Therefore 1(16, 6, 7, 4) > 5.
CHAPTER 3. LOTTO DESIGNS ON THE NZ LOTTO SYSTEM 18
This gives a lower bound of 5. So with each ticket costing $0.6, this design
would cost a minimal of $0.6 · 5 = $3. With the average return for winning
sixth division being around $24, you could make a profit if all of the numbers
drawn were from your lucky numbers occurred about every eighth draw.
However, this would mean that it was happening about 200 times more often
then it should be. So for this to be the case your lucky numbers would have
to be very lucky. This is just a lower bound, we may need to buy more tickets
then this to get our design.
From [6] we get an upper bound of 14 for a (16, 6, 7, 4) lotto design. This
would cost you $8.4. If L(16, 6, 7, 4) was 14 then you would need all of the
numbers drawn to be from your set of lucky numbers happening every third
time. This is about 540 times higher then what you would expect normally.
Your numbers would have to be extremely lucky for this to happen.
If we want to construct an (16, 6, 7, 4) lotto design there are several ways
we can do this. One way is to first use theorem 2.7. This tells us that
L(16, 6, 7, 4) :::; L(8, 6, 4, 4) + L(8, 6, 4, 4). Doing this make it a lot easier
because it is a lot easier to calculate an (8, 6, 4, 4) lotto design then it is to
calculate a (16, 6, 7, 4) lotto design. The following (8, 6, 4, 4) lotto design was
constructed by the greedy algorithm in the appendix. The blocks are:
{1,2,3,4,5,6},{1,2,3,4, 7,8},{1,2,5,6, 7,8},{3,4,5,6, 7,8},{1,2,3,4,5, 7},
{1,2,3,4,5,8},{1,2,3,4,6, 7},{1,2,3,4,6,8}.
We can join this lotto design together with a similar covering on {9, 10, 11, 12, 13, 14, 15, 16}.
This will give a (16, 6, 7, 4) lotto design with the following blocks:
{1,2,3,4,5,6}, {1,2,3,4, 7,8}, {1,2,5,6, 7,8}, {3,4,5,6, 7,8},{1,2,3,4,5, 7},
{1,2,3,4,5,8},{1,2,3,4,6, 7},{1,2,3,4,6,8}{9,10,11,12,13,14},
{9,10,11,12,15,16},{9,10, 13,14,15,16},{11,12,13, 14,15,16},{9,10, 11,12,13,15},
{9,10,11, 12,13,16},{9,10,11,12,14,15},{9,10,11,12,14, 16}.
Example 3.2. Once again we will be working with the NZ lotto system,
and the same set of lucky numbers as example 3.1. This time we will look at
L(16, 6, 7, 5), which corresponds to winning fourth division( 4 numbers from
the 6 drawn plus the bonus ball). The odds of all 7 balls drawn being from
our set of lucky numbers is around 0.06%. The average winnings for fourth
division is about $64. Again using theorem 2.10 we can construct a lower
bound for L(16, 6, 7, 5), which is 41. To use this design it would cost us
a minimum $24.6, so to make a profit the odds of all 7 balls being drawn
from our set of 16 lucky numbers must be greater then around 61%. This
is roughly 1000 times higher then expected odds. This is also the best case
scenario, from theorem 2.11 and [4] we find that the upper bound is 385. It
would cost $231 to implement this design, about 3.6 times more then what
you could win. In this case, the design would be very impractical.
CHAPTER 4
Conclusion
Winning lotto is what dreams are made of. But we have seen that winning
is not an easy task. While it can be easy to construct small lotto designs,
constructing large lotto designs ( n > 30 say) is very difficult. This is what
lotteries rely on. Otherwise everybody would be constructing lotto designs.
Despite the difficulty, this is still an active area of research. In this paper we
saw only a small part of the number of theorems and constructions related
to lotto designs.
In chapter 3 we constructed lower and upper bounds for the NZ lotto system.
While these were not optimal bounds, they still gave us an idea of the number
of tickets needed for the corresponding lotto designs. In particular, we saw
that the possible winnings for the NZ lotto system were well below the value
needed to make playing lotto practical. That is, the number of tickets needed
to make an optimal lotto design for any one of the divisions was far too high
when compared with the amount we could win. However, this is just one
lottery, there may be other lotteries out there for which effective lotto designs
can be constructed.
19
APPENDIX A
Calculating the Upper Bound
for L( 40,6,6,4)
To calculate the upper bound for £(40,6,6,4), the first thing we need to do
is use proposition 2.11 to write L( 40, 6, 6, 4) as the sum of suitable coverings.
When we do this we get the following results.
p T(t- 1) + 1 + V
6 T(4-1)+1+v
5 3T+ V
Therefore T = 1,v = 2. So we have £(40,6,6,4)::::; 0(38,6,4). Now we use
proposition 2.13 to calculate an upper bound. For the best results we have
to check all values of n 1 such that 19 ::::; n 1 ::::; 32. We don't check for higher
values of n 1 because then n 2 would be less then k, which is not possible for
a covering. After we do a few calculations we will come to n 1 = 27, and
n 2 = 11. This gives us the smallest upper bound. The following calculations
were used to calculate the upper bound.
0(27, 0, 0) · 0(11, 6, 4) = 1· 32 = 32
min of 0(27, 1, 0) · 0(11, 5, 4) 1· 66 = 66
0(27, 2, 0) · 0(11, 4, 4) = 1· 330 = 330 min= 32
0(27, 1, 1) · 0(11, 5, 3) = 27.20 = 540
+ min of 0(27, 2, 1) · 0(11, 4, 3) = 14.47 = 658
0(27, 3, 1) · 0(11, 3, 3) = 9. 165 = 1485 min= 540
0(27,2,2). 0(11,4,2) = 351. 11 = 3861
+ min of 0(27, 3, 2) · 0(11, 3, 2) = 117. 19 = 2223
0(27, 4, 2) · 0(11, 2, 2) = 61. 55 = 3355 min= 2223
0(27, 3, 3) · 0(11, 3, 1) = 2925.4 = 11700
+ min of 0(27, 4, 3) · 0(11, 2, 1) = 763. 6 = 4578
0(27, 5, 3) · 0(11, 1, 1) = 319. 11 = 3509 min= 3509
0(27, 4, 4) · 0(11, 2, 0) = 17550. 1 = 17550
+ min of 0(27, 5, 4) · 0(11, 1, 0) = 3906. 1 = 3906
0(27, 6, 4) · 0(11, 0, 0) = 1170. 1 = 1170 min= 1170
total=7474
From this we have £(40,6,6,4)::::; 7474. This is the smallest upper bound
possible using this approach.
20
APPENDIX B
Greedy Algorithm in Maple
What follows is a greedy algorithm to construct lotto designs written in
maple. The code is usually in one piece, but has been broken up to allow for
comments explaining what it is doing.
greedy:=proc(n,k,p,t)
local lp,mp,lp2,lp3,lk,mk,cover,total,P,count,j,
com,ii,jj,hh,gg,iteration,winner,h,rank,z;
with(combinat, choose);
with(combinat,numbcomb);
lp is the set of all possible p sets.
lp:=choose(n,p);
mp:=numbcomb(n,p);
lp2:=array(1 .. mp,1 .. 1);
lp3:=array(1 .. mp,1 .. 1);
lk is the set of all possible k sets.
lk:=choose(n,k);
mk:=numbcomb(n,k);
cover is the maximum number of p sets any k set can cover.
cover:=O;
total is the total number of blocks in the design.
total: =1;
P:=numbcomb(p,t);
count is the total number of p sets that are covered at each point of the code.
count:=O;
rank keeps track of how many uncovered p sets each k set covers at each
iteration of the code.
rank:=Matrix(mk,1);
The next part of the code checks to see the maximum number of p sets each
k set can cover.
21
APPENDIX B. GREEDY ALGORITHM IN MAPLE 22
for j from 1 to mp do; com:=choose(lp[j] ,t);
for ii from 1 to P do;
if ((convert(com[ii] ,set) subset convert(lk[1],set))=true) then;
cover:=cover+1;
break;
end if;
end do;
end do;
Before any k set is chosen, every possible k set covers the maximum number
(cover) of uncovered p sets.
for jj from 1 to mk do;
rank[jj,1] :=cover;
end do;
The first block the code chooses is { 1, ... , k}.
print(convert(lk[1],set));
count:=cover;
Now the code adjusts the number of uncovered p sets that each possible k
set covers according to the p sets covered by the first block, and also sets
lp2[j,1] to 0 if the p set j is now covered.
for jj from 2 to mk do;
for j from 1 to mp do;
com:=choose(lp[j] ,t);
for hh from 1 to P do;
if ((convert(com[hh] ,set) subset convert(lk[1] ,set))=true) then;
for gg from 1 to P do;
if (convert(com[gg],set) subset convert(lk[jj],set)=true) then;
rank[jj,1] :=rank[jj,1]-1;
break;
end if;
end do;
lp2 [j '1] : =0;
break;
end if;
end do;
end do;
end do;
Now the code runs through 100 iterations choosing the best k set at each
iteration until all p sets are covered. For larger designs we would need to
change the upper limit of iterations to something greater then 100.
for iteration from 1 to 100 do;
if (count
The first step is to find the unchosen k set that covers the most uncovered p
sets.
winner:=2;
for h from 2 to mk do:
if (rank[h,1]>=rank[winner,1]) then;
winner:=h;
end if;
end do;
print(convert(lk[winner] ,set));
Once the best k set is chosen, count increases by the number of uncovered p
sets the k set covers, then the number of uncovered p sets this k set covers
is set to 0.
count:=count+rank[winner,1];
total: =total+1;
rank[winner,1] :=0;
Now the number of uncovered p sets that each k set covers is adjusted ac-
cording to the p sets that the k set covered.
for jj from 2 to mk do;
for j from 1 to mp do;
First we check to see if the current k set covers any uncovered p sets.
if (rank[jj,1]<>0) then;
If it does, then we check to see if each uncovered p set is covered by the k
set.
if (lp2[j,1]<>0) then;
com:=choose(lp[j] ,t);
for z from 1 to P do;
if ((convert(com[z],set) subset convert(lk[winner] ,set))=true)
then;
lp3[j,1]:=1;
for ii from 1 to P do;
if ((convert(com[ii] ,set) subset convert(lk[jj] ,set))=true)
then;
rank[jj,1] :=rank[jj,1]-1;
break;
end if;
end do;
break;
end if;
end do;
APPENDIX B. GREEDY ALGORITHM IN MAPLE
end if;
end if;
end do;
end do;
for j from 1 to mp do;
if (lp3[j,1]=1) then;
lp2 [j '1]: =0;
end if;
end do;
end if;
end do;
print(total);
end proc:
24
It may seem strange to force the algorithm to choose the first block to be
{1, .. , k}, but this has no effect on the efficiency of the algorithm. Through a
suitable isomorphism we can change the block {1, .. , k} to any other k subset
of N = { 1, .. , n}. The fact that the first block has points labeled 1 to k does
not change the size or effectiveness of the design.
Nessun commento:
Posta un commento