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.
Audience
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.
Definitions
In the articles involving the lottery problem on Nerdland, the following conventions will be used for terms and variable naming:
- range
- 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.
- m-match
- 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.
- C(n,k)
- 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”
- O(n)
- 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“.
References
- 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.
| Greedy Algorithm Design Decisions » |
Share this content on:
“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.”
The first sentence is correct. The second sentence is utterly wrong and irrelevant. Which ticket contains the pair 1-6 for example. None, because it isn’t needed to achieve the stipulated guarantee.
I concur with the comment by erce.
The second sentence implies that The problem is one of combinations rather than coverings or combinatorics. We should not expect every combination of two numbers from 1 to 6 to be found on each of those three tickets, 1-2-3, 4-5-6, and 1-3-4. Besides the 1-6 mentioned by erce, 1-5, 2-5, 2-4, 2-6, 3-5, 3-6 are not covered.
This does not mean that the article is flawed; on the contrary, it is an excellent article with just an incorrect sentence.
If I were to edit the article, I would write the second sentence as follows:
“The reader can verify that every combination of three numbers from 1 to 6 (ignoring order) will match at least two numbers on one or more of those three tickets.”
By the way, I have my own applications of combinatorics at http://www.betstarter.com/lottery/AbbreviatedWheels.asp
Hi, is a real good analysis.
I would like to add a little details here about lottery wheels.
what I never see on internet is nobody realize that every lottery, in my state, for example, have different behave, beside they have different amount of numbers to play. and the problem with the wheel is never the wheel program compare the results with the winning history lotto, at least, if you see the history-winning numbers they never reapeat, so what about if the numbers in your wheel already drawed? = you are wasting money. plus another details. thanks.
Victor, lotteries draws are normally independent. That is, the results historical drawings CAN repeat. Because there are so few historical results compared to the number of possible results, it is rather unlikely that the next result will be equal to any of the previous results, but it could happen.
If you’re saying that some particular lottery has a RULE against repeated results (e.g. if they draw the same numbers as a previous result, they will re-draw), then yes this should be taken into account, but I don’t think it would make too much of a difference. This is because, as I said above, that situation is unlikely anyway. Assume that a 6-from-49 lottery draws a different result every day for ten years — there would still only be about a 1 in 3,800 chance of hitting a repeat combination.