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](http://www.projecteuler.net) challenge, but it wasn't selected.



What is the minimum set of combinations C(p,n) required to guarantee q<p matches with a target combination (pT,n)
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](http://dx.doi.org/10.1016/j.ejor.2007.01.039)


Hoping this is useful...


