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 most trivial lottery wheel is every possible ticket, since this would obviously guarantee that you would win every possible prize, including the jackpot. More interesting lottery wheels are those which guarantee that you win some level of lesser prize other than the jackpot. Most lotteries furnish prizes to those who do not match the drawing but still match some m numbers out of the drawing, regardless of order, for various values of m. This series of articles concerns itself with the problem of finding small lottery wheels that will guarantee a match of m numbers from any drawn ticket.
For example, consider a lottery which draws 3 numbers in the range 1 to 6. A lottery wheel that guarantees a match of 2 numbers from the winning ticket would then be: 1-2-3, 4-5-6, 1-3-4. The reader can verify that every combination of two numbers from 1 to 6 (ignoring order) can be found on each of those three tickets. Therefore, any ticket drawn as the winner will either be one of those three tickets, or will share at least two numbers in common with at least one of them. So if the lottery were to award prizes for matching two numbers form the winning ticket, you would be guaranteed to win that prize if you bought the above three tickets.
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. Theoretically, if there were a wheel so small that the set of tickets cost less to purchase than the value of the guaranteed prize, you could use such a wheel to play the lottery and win money every time without risk.
In reality, of course, lottery wheels are not an effective get-rich-quick scheme. Organizations that run lotteries are quite aware of the mathematics involved and set the ticket prices and payout levels such that the expected value of your ticket is always less than face value. Buying a wheel of tickets will not make this expectation positive no matter how good the wheel. Playing the lottery will always lose you money in the long run, but the lottery wheel problem remains mathematically and computationally interesting nonetheless.
The Lottery Problem articles may at times assume some familiarity with combinatorics, graph theory, and computer programming. However, it should be accessible to those who do not have such knowledge. In particular, I have tried to provide summaries and examples where relevant, and I have included links to further introductory information on technical topics.
In the articles involving the lottery problem on Nerdland, the following conventions will be used for terms and variable naming:
- The number of “balls” in the lottery drawing. This is abbreviated as r.
- ticket size
- The quantity of numbers that one selects on a single ticket. This is abbreviated as t.
- match size
- The quantity of numbers from the winning ticket that must be matched to win the prize that the wheel attempts to guarantee. This is abbreviated as m.
- t-from-r lottery
- A lottery in which t balls are drawn from a set of r balls without replacement and without regard to order.
- A set of m specific numbers that appear on a ticket.
- selected ticket
- A ticket that has been included in the wheel being generated.
- covered ticket
- A ticket that, if drawn as the winning ticket, would share at least one m-match with at least one selected ticket.
- The number of ways in which k items can be selected from a set of n items without regard to order. This is known as a combination and is read “n choose y”
- This is big-O notation which describes the asymptotic worst-case running time of a computational process, relative to the size of the input. It is read as “Oh of n“.
- The UK National Lottery Wheeling Challenge by Richard K. Lloyd. The site which initially inspired me to investigate this problem.
The above list of references will be updated as this article series is expanded.