[sibrahim]

For anyone else that's curious, the lottery problem is called the Transylvanian lottery: https://en.wikipedia.org/wiki/Transylvania_lottery

The primary observation is if you want to match k numbers on tickets where you pick n numbers, each ticket simultaneously covers n choose k different k-tuples. The Translyvanian lottery is designed so that finite projective planes give you the minimal result (no pair appears on more than one ticket).

This sort of combinatorial design is rumored to have been used by the MIT syndicate that gamed the Massachusetts lottery (notably, they manually and laboriously picked their numbers while the other two syndicates were using random quick picks).

(I've had to learn a lot about lotteries in the last two years :P)

On a side note, finding a minimal set of tickets to cover a set of outcomes is exactly analogous to testing software with pairwise testing: https://en.wikipedia.org/wiki/All-pairs_testing

[pitchka]

General problem - having ticket with k numbers where possible numbers are from 1 to n, find the minimal set of tickets that will cover all of the possible ones so that at least one ticket in your set has at least m equal numbers on the ticket that is drawn (m <= k). (Trivial example. To win the lottery - guarantee k matches - one has to buy all of the tickets.)

It is still unsolved although maths has provided some nice bounds for large amounts of (n,k,m) triplets, and solutions to (n,k,2). Although, for the (n,k,2) a simple greedy set cover finds the optimal solution always.