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!mhuxr!mhuxn!ihnp4!qantel!lll-crg!seismo!harvard!greg
From: greg@harvard.UUCP (Greg)
Newsgroups: net.puzzle
Subject: Re: Winning 1/3 of the Lottery (*correct but partial spoiler*)
Message-ID: <523@harvard.UUCP>
Date: Sat, 23-Nov-85 21:49:16 EST
Article-I.D.: harvard.523
Posted: Sat Nov 23 21:49:16 1985
Date-Received: Thu, 28-Nov-85 03:44:39 EST
References: <25@bbncc5.UUCP>
Reply-To: greg@harvard.UUCP (Greg)
Organization: Harvard
Lines: 39
Summary: I can do it in 18 tickets.

In article <25@bbncc5.UUCP> larry@bbn.UUCP (Larry Denenberg) writes:
>The Massachusetts State Megabucks Lottery works like this:  A ticket costs
>$1 and consists of six distinct numbers of your choosing between 1 and 36
>inclusive.  You may buy as many tickets as you like.  On Lottery Day
>the Authorities choose six numbers.  If those six are the same as your
>six, you win!
>...
>What is the minimum number of tickets that you must buy to ensure that
>at least one of your tickets matches two or more of the winning numbers?

Well, I can give a crummy lower bound and pretty good upper bound.  The lower
bound is six tickets, because if you take five tickets, there are at least six
numbers which you haven't chosen, and the winning ticket might be those six
numbers.

The pretty good upper bound is as follows:  Arrange the numbers from one to
36 on a 6 x 6 chessboard (in an order you wish).  Now write down each column
on the first six tickets, and each row on the next six tickets.  So far we
have twelve tickets.  Clearly, there are 6! = 720 tickets that do not have
two numbers in common with these:  For the winning ticket, you may pick any
number out of the first column, any other number out of the second, any besides
the first two for the third, and so on.  The winning ticket may not have two
numbers in the same row or column.  Now for the remaining six tickets do the
following:  For ticket 1, write the second row of the first column and the first
row of the other columns; for ticket 2, the third row of the first column and
the second row of the other columns; and so on.  For the last ticket, pick
the first row of the first column and the last row of the other columns.  We
know that the winning ticket has to intersect with one of these last six if
it doesn't intersect with one of the first twelve.  Why?  Well, the winning
ticket must have some number in the first column, say the one on row n.
It must also have some number on row n+1 mod 6, and that number cannot be in
the first column of the sqaure.  Therefore the winning ticket intersects twice
with the ticket which has the number of row n, column 1, and all the numbers
on row n+1 mod 6, columns i>1. 

I don't know if it can be done in 17 tickets, but my guess is yes, because
the last six tickets were used poorly.
-- 
gregregreg