The Lottery Problem, sometimes known more specifically as the Lottery Wheel Problem is a problem in combinatorics and computer science that arises from a common gambling tactic used to guarantee non-jackpot wins at the expense of a higher initial investment.
This problem is intriguing from a computational perspective because it is difficult, but not impossible, to compute reasonably good solutions for real-world sized problems. Nevertheless, the question of how to efficiently generate optimal solutions seems to be presently unsolved. Also unsolved is the related question of whether or not this problem is in fact NP-Complete. The answer to this latter question would determine if generating optimal solutions is feasible at all.
This page is an index into a continuing series of articles cataloging my research into this problem.
- An Introduction to the Lottery Problem
- Greedy Algorithm Design Decisions
- Greedy Algorithm Implementation Walkthrough
- Implementation Challenges
- Relationship to Minimum Set Covering
- Results and Analysis of the Greedy Implementation
Share this content on:
How would you go about solving the case where you have k tickets for a lottery and you want to maximize the number of prizes you can win with those tickets? For example, for a 45 pick 5 lottery, you have 10,000 tickets and you win a prize if you have at least 2 matching numbers. This seems to be a variant of the set-covering problem.