I can’t remember exactly how I got there (I suspect that Wikipedia was involved), but some weeks ago I ended up reading the UK National Lottery Wheeling Challenge website. The “challenge” involved is to generate a lottery wheel as small as possible for winning at least £10 in the United Kingdom’s national lottery. What exactly is a wheel, and why should it be small? To quote my own introduction:
A lottery wheel is a set of tickets for a lottery drawing which, if purchased in its entirety, guarantees a certain type of win, according to the rules of the lottery, no matter which ticket is actually drawn. […] The goal is straightforward. Each ticket we purchase costs money, so we want to generate a lottery wheel that is as small as possible while still guaranteeing a win of some minimum desired prize.
Now, obviously, such a thing no matter how good is not going to let you turn playing the lottery into a reliable money-maker, but in fact the reason that this is interesting has nothing to do with actually playing the lottery. I’ve only bought one lottery ticket in my entire life, and needless to say I lost.
The reason that this was initially interesting to me was that the site showcased a wheel of 163 tickets, which seems quite good for a 6-from-49 lottery, but went on to solicit for better wheels (indicating that the 163-ticket wheel was not known to be optimal) and to note that no wheel generation algorithm was known. The more I thought about how to create a generation algorithm, the more intriguing the problem became. The problem turns out to be a very special, highly symmetric form of minimum set covering. From what I was able to find, this problem has been studied academically, but with minimal results, and rarely on realistically-sized problems.
So, inspired by this, I set out to do two things: write a program that runs in a reasonable amount of time on a modern personal computer that can generate good lottery wheels for realistically-sized lotteries, and if possible prove whether this problem is NP-Hard or not.
I am documenting this project in a series of articles on the lottery problem. To start with, I have posted the first three articles which describe the problem, its relationship to set covering, and the challenges involved in implementing a generator algorithm for realistically-sized lotteries. Further articles will be posted later documenting my progress on the problem.
Share this content on:
