What is the minimum set of combinations C(p,n) required to guarantee qA state lottery draws p numbers out of a grid of n numbers. Players participate by filling in p numbers into a grid, at unit cost. They can sumbit as many grids as they like.
The lottery pays out when a player's grid matches at least q numbers with the outcome of the drawing, the "winning combination" pT. How many grids does a player need to submit, to ensure a payout ?
Obviously, a player could cover the whole space of C(p/n) = n!/p!(p-n)! possible combinations, thereby guaranteeing every possible match of q, q+1, .., p numbers with the target set pT. That would certainly cover the C(q/p).C(p-q / n-p) combinations that match exactly q elements of the target set pT. But only one such match is required. How does one construct a minimum subset of C(p/n) to guarantee at least one grid matching at least q elements of the target set pT ?
I have previously submitted this question as a Project Euler challenge, but it wasn't selected.
 A: Hmmm... I recently saw a paper dealing exactly with this. You may like to learn that this problem is known in the litterature as the "lottery number".
I was not able to find this paper back, though I found one from 2008 whose introduction contains several interesting references :
A note on a symmetrical set covering problem: The lottery problem
Hoping this is useful...
A: You may find the following interesting.
I think what you're asking for is the minimum cardinality of a code of length $p$ over the alphabet $Z_n$ (the integers mod $n$, assuming) the possible  numbers are $1,2,\ldots,n-1$ with covering radius $p-q$. This is in general a very hard NP-complete problem. 
Given two vectors $x,y$  in $Z_n^p$, their Hamming distance $d(x,y)$ is defined as the number of coordinates on which they differ. Given a subset $C$ of $Z_n^p$ which corresponds to the collection of lottery selections, the covering radius $R(C)$ is
$$
R(C) = \max d(x,C)
$$
where the maximum is taken as $x$ ranges over $Z_n^p$ and where $d(x,C)=\min d(x,c)$ with the minimum taken over $c \in C.$ When you think about it, you're asking for the minimal cardinality code with covering radius $p-q,$ i.e., with $p-q$ wrong numbers out of $p$.
In general there are bounds on $R(C)$ and the case $n=3$ is of interest in football [soccer] pools. The Golay code is relevant here since it is a perfect ternary code with good covering radius. 
There was a nice article MAA monthly years ago entitled something like "football pools, a problem for mathematicians".
A: I'm a programmer, not a mathematician, but knowing that the probability of any payout match on a single grid is given by
$p = _pC_r / _nC_r$, where $r$ is the number of matches required for a payout and
$(r <= q)$,
intuitively, having $1/p$ grids covering all r-tuples will result in a probability of $1$; a guarantee.
However (unfortunately) I don't believe there exists a design for a $1/p$ set of grids covering all r-tuples uniquely (my brute force computer trials have all failed), but I don't have the math skills to prove it.  Such sets exist, but with many more than $1/p$ members.
As a side note, this concept was implemented successfully by a group who purchased several hundred grids weekly with a guaranteed payout that covered about 60% of the cost.  Since their grids covered 100% of the smallest r-tuples thus covering a significant portion of (r+1)-tuples which paid out substantially more, frequently their payout was out enough to turn a "profit" thus sustataining the pool without additional funds.  Over a couple of years, the scheme won many larger payouts (but not a jackpot) until the grid price was doubled after which the group dissolved.
A: As I had pointed out earlier, this is a difficult problem to solve in general. 
I have managed to find a nice description of the problem in sections VI.8 and V.8 in the CRC Handbook of Combinatorial Designs by Colbourn and Dinitz.
