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!mhuxr!mhuxn!ihnp4!qantel!lll-crg!seismo!harvard!bbnccv!bbncc5!ldenenbe
From: ldenenbe@bbncc5.UUCP (Larry Denenberg)
Newsgroups: net.puzzle
Subject: Re: Winning 1/3 of the Lottery
Message-ID: <78@bbncc5.UUCP>
Date: Fri, 22-Nov-85 13:41:13 EST
Article-I.D.: bbncc5.78
Posted: Fri Nov 22 13:41:13 1985
Date-Received: Sun, 24-Nov-85 06:33:20 EST
References: <25@bbncc5.UUCP> <516@harvard.UUCP>
Reply-To: larry@bbncc5.UUCP (Larry Denenberg)
Organization: Bolt Beranek and Newman, Cambridge, MA
Lines: 36

In article <516@harvard.UUCP> greg@harvard.UUCP (Greg) writes:
>In article <25@bbncc5.UUCP> larry@bbncc5.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, if you're incredibly unlucky, you may end up buying every single
>ticket which has only one number in common with the winning ticket, and also
>every single ticket which has no numbers in common with the winning ticket.
>The question remains, how many such tickets are there?
>. . .


Let me be more clear.

1)  Each lottery ticket contains a *set* of six numbers.  That is, order
    is not significant AND the six numbers are distinct.

2)  You're trying to be *clever*, not lucky.  You want a ticket that
    matches two or more numbers, but you want to buy as few tickets as
    possible.  For example, suppose that I had asked you to guarantee
    that you would match *one* or more numbers.  Then the answer is six:
    you just have to cover all of the numbers, and you can do this with
    six tickets.  (In fact you would have to cover only 31 of the numbers,
    but you still need six tickets.)  Don't forget that you get to choose
    which numbers are on your ticket.

Stated precisely, the puzzle is this:  Let a *ticket* be a subset of
{1,2,...,36} with cardinality six.  What is the minimum cardinality
of a set T of tickets with the property that for *every* ticket t there
exists a ticket in T whose intersection with t has cardinality two or more?