Hacker News Reader

Comment by pitchka | Hacker News Reader

It's just amazing what mathematics can do.

What was once attacked with NP-hard algorithms now has a constructive one.

Reminds me a little bit of the lottery problem - one has to find the minimum sized set of tickets that guarantee a match of at least K numbers on any of the tickets. Statistics can easily get you the expected number of tickets you have to buy but finding that minimum set can be mapped to a minimum set cover (where you're trying to cover all tickets with your set so that tickets in the set match all possible tickets in at least K numbers).

Then, all of a sudden maths can put bounds and direct formulas of how many tickets your set has to have (not trivial).

Leaving you again with a constructive polynomial algorithm.

View on HN

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

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.

Reply on news.ycombinator.com