Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site uvacs.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!mcnc!ncsu!uvacs!dsr
From: dsr@uvacs.UUCP (Dana S. Richards)
Newsgroups: net.puzzle
Subject: Re: Re: Winning 1/3 of the Lottery
Message-ID: <16@uvacs.UUCP>
Date: Mon, 25-Nov-85 17:27:37 EST
Article-I.D.: uvacs.16
Posted: Mon Nov 25 17:27:37 1985
Date-Received: Thu, 28-Nov-85 07:56:18 EST
References: <25@bbncc5.UUCP> <516@harvard.UUCP> <78@bbncc5.UUCP>
Organization: U.Va. CS dept.  Charlottesville, VA
Lines: 31

> 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?

This is hard it seems.
I looked at the presumably simpler problem of minimizing T given that
you much intersect a randomly chosen pair; recall a random ticket gives
rise to C(6,2)=15 such pairs.
IF we used {1,...,49} and cardinality 7 then we can be optimal;
i.e. use T=C(49,2)/C(7,2)=56 tickets.
The idea (and I have not been careful and relied on memory) is to
use a complete set of 6 mutually orthogonal order 7 latin squares with
the 2 trivial order 7 designs (i.e. constant rows and columns).
However this approach does not work for the cardinality 6 case since
such designs do not exist.
Since the simpler problem is messier for 6 I would be surprised if the
original problem had an elegant solution.