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.