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!cbosgd!ihnp4!qantel!lll-crg!seismo!harvard!bbnccv!bbncc5!ldenenbe
From: ldenenbe@bbncc5.UUCP (Larry Denenberg)
Newsgroups: net.puzzle
Subject: Winning 1/2 of the Lottery  (***SPOILER***)
Message-ID: <969@bbncc5.UUCP>
Date: Thu, 9-Jan-86 13:18:06 EST
Article-I.D.: bbncc5.969
Posted: Thu Jan  9 13:18:06 1986
Date-Received: Mon, 13-Jan-86 01:12:54 EST
Reply-To: larry@bbncc5.ARPA (Larry Denenberg)
Distribution: net
Organization: Bolt Beranek and Newman, Cambridge, MA
Lines: 39

With Chuck (chuck%dartmouth) Simmons' corrected 48-ticket bound on L(18:3,6,3)
and (especially) using Greg (greg@harvard) Kuperberg's new ideas, we can now
give a 75-ticket solution of the overall problem.

The basic breakdown is into two groups of 18:
               L(36:6,6,3)  <=  L(18:3,6,3)  +  L(18:4,6,3)
since if there aren't 3 special numbers in the first group, there must be at
least 4 in the second group.  We now break the second group of 18 into three
groups of 6---call them groups A, B, and C.  Think of them arranged in a
circle, so that A follows B follows C follows A.  Now either (a) one of the
groups has at least three numbers, or (b) there exists a group with two
numbers followed by a group containing at least one number.  (Justification:
if (a) fails, then the four special numbers are divided either 2-2-0, 2-0-2,
0-2-2, 2-1-1, 1-2-1, or 1-1-2.)  So we solve L(6:2,6:1,6,3) and use it three
times, on A&B, B&C, and C&A.  Now
        L(6:2,6:1,6,3)  <=  L(6:2,4,2)*L(6:1,2,1)  =  3*3  =  9
and moreover these tickets can easily be chosen so that all triplets in
the first group of 6 are covered.  Grand total 48 + 3*9 = 75 tickets.

Also in the news, Arthur David (ado@elsie) Olson replies to my 13-ticket
bound on L(12:2,4,2) with "No, it's not sleazy---in fact, I can top it!"
Here is his provably optimal, 12-ticket solution on numbers 0-9,a,b:
   0123  0456  0789  01ab  1457  1689  248a  259a  267b  349b  358b  367a
The simplest proof of optimality is this:  each number must appear on at
least 4 tickets (since each must be paired with 11 other numbers).  But that
means 12*4 = 48 spots minimum, precisely the number of spots in 12 tickets.
Similar arguments give lower bounds of 14 and 42 on L(12:3,6,3) and
L(18:3,6,3) respectively.

Chuck Simmons also gives this 15-ticket solution of L(12:3,6,3) (the numbers
here are 1-9,a,b,c, and x means "don't care"):
      1234xx    5678xx    9abcxx
      12569a    1278bc    13579b    1368ac   14589c    1467ab
      3456bc    34789a    2457ac    24689b   2358ab    23679c
Notice that the tickets on the top row only cover four triplets each.  
Even so, this will be very hard to beat.

/Larry Denenberg
larry@{bbncc5,harvard}