What is the minimum set of combinations C(p,n) required to guarantee q<p matches with a target combination (pT,n)

Question

A 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" p_T. 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 p_T. That would certainly cover the C(q/p).C(p-q / n-p) combinations that match exactly q elements of the target set p_T. 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 p_T ?

I have previously submitted this question as a Project Euler challenge, but it wasn't selected.

Answer 1

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

Answer 2

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".

Answer 3

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.

Answer 4

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.