Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site harvard.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!genrad!panda!talcott!harvard!greg
From: greg@harvard.UUCP (Greg)
Newsgroups: net.puzzle
Subject: Winning 1/2 of the Lottery (*yet another partial spoiler*)
Message-ID: <584@harvard.UUCP>
Date: Sun, 5-Jan-86 12:12:49 EST
Article-I.D.: harvard.584
Posted: Sun Jan  5 12:12:49 1986
Date-Received: Tue, 7-Jan-86 03:42:45 EST
Organization: Harvard
Lines: 82

Here is my best partial answer to the 3-number lottery problem.  For those
of you who have missed out on the lottery stuff, here is the question:

In the Massachussetts State Lottery, you choose six different numbers from
one to 36 on each ticket you buy (they cost $1).  Three days later the 
authorities will choose six numbers between 1 and 36.  If those six numbers
are the same as the six you chose, you win.  Order does not matter.  How
many tickets do you need to buy to guarantee that you match three numbers
with the winning ticket?

Now for my best solution of 84 tickets:

First, divide the numbers into the following groups:

Group 1:  1  2  3  4  5  6  7  8
Group 2:  9 10 11 12 13 14 
Group 3: 15 16 17 18 19 20 21 22
Group 4: 23 24 25 26 27 28
Group 5: 29 30 31 32 33 34 35 36

Now, the winning ticket has six numbers, so at least one of the following
three statements is true:

1.  One of the five groups has three winning numbers in it.
2.  There is a number N such that group N has two winning numbers in it and
group N+1 has at least one winning number in it.
3.  Group 5 contains two winning numbers and group 1 contains at least one.

In my strategy, if there are two numbers in group 1 and one in group 2, one
of the following tickets will contain those three numbers: 

 1  2  3  4  9 10,  1  3  2  4 11 12,  1  4  2  3 13 14
 1  2  5  6  9 10,  1  3  5  7 11 12,  1  4  5  8 13 14
 1  2  7  8  9 10,  1  3  6  8 11 12,  1  4  6  7 13 14
 3  4  5  6  9 10,  5  7  2  4 11 12,  2  3  5  8 13 14
 3  4  7  8  9 10,  5  7  6  8 11 12,  2  3  6  7 13 14
 5  6  7  8  9 10,  2  4  6  8 11 12,  5  8  6  7 13 14

Notice also that if there are three numbers in group 1, one of the above 18
tickets will contain those three numbers as well.

If, for each number n in the above tickets, we substitute n+14, we get 18
tickets which match any combination of two numbers in group 3 and one in 
group 4, as well as any set of three numbers in group 3.  If we substitute,
in the above tickets, 29 for 1, 30 for 2, 31 for 3, 32 for 4, 33 for 5,
34 for 6, 35 for 7, 36 for 8, 1 for 9, 2 for 10, 3 for 11, 4 for 12, 5 for 13,
and 6 for 14, and add these tickets:

29 30 31 32  7  8
29 30 33 34  7  8
29 30 35 36  7  8
31 32 33 34  7  8
31 32 35 36  7  8
33 34 35 36  7  8

he 24 tickets that result contain every combination of two numbers in group 5
and one number in group one, as well as every set of three numbers in group 5.

Lastly, for covering every combination of two numbers in group 2 and one
number in group 3, I choose the following tickets:

 9 10 11 12 15 16,  9 10 11 13 17 18,  9 10 11 14 19 20,  9 10 11 12 21 22
 9 10 13 14 15 16,  9 10 12 14 17 18,  9 10 12 13 19 20,  9 10 13 14 21 22
11 12 13 14 15 16, 11 13 12 14 17 18, 11 14 12 13 19 20, 11 12 13 14 21 22

Note that these 12 tickets also cover every set of three numbers in group 2.
Similarly, by adding 14 to each of the above numbers, one covers the case of
two numbers in group 4 and one in group 5, as well as three numbers in group
4.

So, the total is 18 + 12 + 18 + 12 + 24 = 84 tickets, or in Larry Denenberg's
L(n:a,y,m) notation:

L(36:6,6,3) <= L(8:2,4,2)*(2*L(6:1,2,1)+L(8:1,2,1))+2*L(6:2,4,2)*L(8:1,2,1)
<= 2*18 + 2*12 + 24 = 84.

In this notation, L(n:a,y,m) is the minimum number of tickets necessary to
match m numbers with the winning ticket in a lottery game with n numbers, in
which the authorities choose a numbers and you choose y numbers on each
ticket.
-- 
gregregreg