Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site bbncc5.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!genrad!panda!talcott!harvard!bbnccv!bbncc5!ldenenbe
From: ldenenbe@bbncc5.UUCP (Larry Denenberg)
Newsgroups: net.puzzle
Subject: Winning 1/2 of the Lottery (***SPOILER***)
Message-ID: <795@bbncc5.UUCP>
Date: Thu, 2-Jan-86 18:05:14 EST
Article-I.D.: bbncc5.795
Posted: Thu Jan  2 18:05:14 1986
Date-Received: Sat, 4-Jan-86 05:34:46 EST
Reply-To: larry@bbn-unix.UUCP (Larry Denenberg)
Organization: Bolt Beranek and Newman, Cambridge, MA
Lines: 50
Keywords: lottery
Summary: 84 and counting

Remember all those details of my last posting that you didn't wade through?
Well, forget them:  Here's a solution in 84 tickets.  (I'm assuming that you
recall the notation and a few partial solutions, though.)

I received a letter from chuck@dartvax who claims an upper bound of 48
on L(18:3,6,3).  That instantly yields a solution in 96 tickets to the overall
problem, as he points out.  (His article never made it here so I have asked
him to repost in case others missed it too.  I'm assuming his solution is
correct, sight unseen.  Dartmouth people are trustworthy.)

Now let's take the uneven-sized blocks idea of spitzer@faust a little further.
Suppose we break up the universe into blocks of 4, 14, and 18, noting that
 L(36:6,6,3) <= L(4:3,6,3) + L(14:3,6,3) + L(18:3,6,3) + L(4:2,14:2,18:2,6,3)
The first term here is obviously 1, and we're using chuck's bound of 48 for
the third term.  The final term is easy:  seven tickets, each with all four
of the first group and two of the second group, handle it with no sweat.  Now
     L(14:3,6,3)  <=  L(12:3,6,3) + L(12:2,4,2) <= 17 + 13
since you just cover all triplets in the first twelve numbers, then cover
all pairs in those numbers using four numbers at a time and put the final
two numbers on each of the last 13 tickets.  (The bounds of 17 and 13 come
from my last article.)  Grand total 1+17+13+48+7 = 86 tickets.

But the first ticket is clearly unnecessary since you cover all four of
its numbers with each ticket in the group of seven.  Moreover, at least
one of the tickets in the group of 17 is unnecessary by the tricks of the
previous posting;  one of those 17 is needed for only three triplets, and
these can be covered by the 13 as they do their other work.  Thus we're
down to 84 tickets.

The weak spot in this is the bound of 29 for L(14:3,6,3).  This business of
breaking up a block and solving pieces separately seems invariably suboptimal;
most of my recent progress rests on the "indecomposable" but economical bounds
for L(12:3,6,3) and L(12:2,4,2) that I got by moving numbers around on paper,
not breaking up blocks.  Yet above I broke down a block of 14 into 12 and 2
just because I know good ways of solving blocks of 12!  A direct assault
on L(14:3,6,3) would undoubtedly save a few more tickets and get us into
the seventies.  Looks like a job for Superhacker.

Concerning lower bounds:  greg@harvard points out that at least 23 tickets
are required (since the probability of matching 3 or more with a single 
ticket is less than 1 in 23).  It's easy to push this to 24 by looking
closely at the unavoidable overlap.  Anyone have a stronger argument?

Before anyone jumps on me, I'd like to correct a few errata in my previous
posting.  First of all, (5*3)+(1*3) is 18, not 15 [it doesn't affect any
results].  Second of all, my explanation of "independent" is a paragraph too
early;  the word means something slightly different where it first appears.

/Larry Denenberg
larry@{bbn-unix,harvard}