spitzer@faust.UUCP (12/26/85)
Here is a way to construct a 108 ticket solution to guarantee a 3
number match in the Mass lottery and a couple of suggestions on how
this number might be reduced. (The tickets are at the end if you
don't want to read through the rest.)
Define 3 blocks of tickets, each block covering the numbers in a
subrange of 1-36, such that all numbers 1,..,36 are in at least
one block.
Construct the tickets in each block so that all 3 number
combinations in the range are found one at least one ticket in
the block.
We then have the situation where (1) at least one block has three
of the winning numbers, or (2) each block has exactly two winning
numbers. In case (1) the problem is solved, since any 3 numbers
in the block appear on at least one ticket. To cover case (2), do
the following:
Construct a 4th block of tickets by generating "sub-tickets" of
length 2 to 5 numbers so that all the pairs in a previous block
are on at least one subticket. By definition (case 2), at least
one of these subtickets will contain 2 winning numbers. Now
combine these subtickets with every number in another previous
block. The resultant tickets will contain at least 3 winning numbers
on one of them.
For the 108 ticket solution:
Let the range of B1 = 1,..,6 (6 numbers)
range of B2 = 7,..,20 (14 numbers)
range of B3 = 21,..36 (16 numbers)
B1 needs one ticket to match all 3 number combinations in its range.
B2 needs no more than 33 tickets and B3 needs no more than 53
tickets (both of these are shown below). 87 tickets so far.
To construct B4:
the following subtickets (length 4) contain all possible pairs
of numbers between 1 and 6.....1 2 3 4
1 2 5 6
3 4 5 6
If B1, B2, or B3 do not contain 3 winning numbers, one of these
subtickets must contain 2 winning numbers. To combine these
subtickets with every number in B2 (which also has at least 2
winning numbers) simply add 2 numbers from B2 at the end of
each subticket until all the numbers from B2 are used:
1 2 3 4 7 8 1 2 5 6 7 8 3 4 5 6 7 8
1 2 3 4 9 10 1 2 5 6 9 10 3 4 5 6 9 10
.
.
.
1 2 3 4 19 20 1 2 5 6 19 20 3 4 5 6 19 20
This takes 21 tickets. The total is 87 + 21 = 108.
To construct B2 and B3 as required, one can use the method as
presented in previous postings (including one of mine). This
involves pairing all the numbers in the range and then taking
all the 3 way combinations of the pairs. This assures covering
all 3 number combinations in the range, but is not, in general,
the most efficient way to do this. However if this method was
used, we would have the following result:
B1 = 1 ticket
B2 = 35 tickets
B3 = 56 tickets
B4 = 21 tickets
Total = 113 tickets
Here's a method that improves B2 and B3 (but only slightly)
(remember, we're trying to make sure that if 3 numbers fall
within the range then they will appear on at least one ticket):
1) divide the range into 2 subranges
2) construct the tickets in each subrange to contain all 3 number
combinations in the subrange
3) construct subtickets (length 2 - 5) that contain all pairs in
subrange 1 and combine them with all numbers in subrange 2 (just
like B4 construction)
4) construct subtickets (length 2 - 5) that contain all pairs in
subrange 2 and combine them with all numbers in subrange 1
Then we have the following cases: 1) All 3 numbers that fall in
the range also fall in one of the 2 subranges. Problem solved by
(2) above; 2) 2 numbers fall in one subrange and 1 number in the
other. Problem solved by (3) and (4) above.
The subranges that produce 33 and 53 tickets for B2 and B3 are:
B2: B2R1 = 7,..,10 B2R2 = 11,..,20 (4! and 10 numbers)
1 ticket for 3 10 tickets for 3
number comb. number comb.
1 length 4 sub- 9 length 4 sub-
ticket for all tickets for all
pairs pairs
Total = 1 + 10 + (1 * 5) + (9 * 2) = 34
Since there is one ticket 7 8 9 10 x x that is a subset of
the pairs ticket of R1 matched with the numbers of R2:
7 8 9 10 11 12
7 8 9 10 13 14
etc.
we can subtract one from the total. Therefore B2 has 33
tickets.
B3: B3R1 = 21,..,26 B3R1 = 27,..,36 (6 and 10 numbers)
1 ticket for 3 10 tickets for 3
number comb. number comb.
3 length 4 sub- 9 length 4 sub-
tickets for all tickets for all
pairs pairs
Total = 1 + 10 + (3 * 5) + (9 * 3) = 53 tickets for B3
All of the actual tickets are indicated at the end.
Improvement possibilities:
1) Only even numbered ranges were used, because ranges covering
odd numbers are very hard to work with to generate "all pairs"
and "all triplets". Maybe odd would produce better results.
2) There must be a way to generate all triplets within a range
that is more efficient than the methods presented so far.
(One that can be done with pencil and paper, rather than limited
to a computer)
3) The initial Block range sizes are 6, 14, and 16. I believe them
to be the best given the number of tickets needed for B2 and B3.
I could be wrong. If B2 and B3 could be done in less they
probably would change.
Here are all the tickets:
B1: 1 ticket 1 2 3 4 5 6
B2: 33 tickets
B2R1: 7 8 9 10 x x (discarded) B2R2: 11 12 13 14 15 16
11 12 13 14 17 18
11 12 13 14 19 20
11 12 15 16 17 18
11 12 15 16 19 20
11 12 17 18 19 20
13 14 15 16 17 18
13 14 15 16 19 20
13 14 17 18 19 20
15 16 17 18 19 20
11 12 13 14
11 15 16 17
11 12 7 8 each 11 18 19 20
13 14 9 10 combined 12 15 16 19
7 8 9 10 combined 15 16 with 12 17 18 20
with 17 18 13 15 18 20
19 20 13 16 17 19
14 15 17 19
14 16 18 20
B3: 53 tickets
B3R1: 21 22 23 24 25 26 B3R2: 27 28 29 30 31 32
27 28 29 30 33 34
27 28 29 30 35 36
27 28 31 32 33 34
27 28 31 32 35 36
27 28 33 34 35 36
29 30 31 32 33 34
29 30 31 32 35 36
29 30 33 34 35 36
31 32 33 34 35 36
27 28 29 30
27 31 32 33
27 28 21 22 each 27 34 35 36
21 22 23 24 each 29 30 23 24 combined 28 31 32 35
21 22 25 26 combined 31 32 25 26 with 28 33 34 36
23 24 25 26 with 33 34 29 31 34 36
35 36 29 32 33 35
30 31 33 35
30 32 34 36
B4: 21 tickets 7 8
9 10
1 2 3 4 each 11 12
1 2 5 6 combined 13 14
3 4 5 6 with 15 16
17 18
19 20