Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
You seem to be asking for a minimum block design? en.wikipedia.org/wiki/Block_design –  András Salamon Aug 9 '10 at 14:59

4 Answers 4

up vote 0 down vote accepted

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

share|improve this answer
    
Thanks Nathann. The paper you referred to, has numerical results for small cases. No closed solution for the general case seems yet to exist. I understand now, why my question was not used on Project Euler. –  Walter Baeck Aug 10 '10 at 16:05

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.