Lotto Ticket Coverage From Algorithm Design Manual?
algorithm
Solution
In the example
- n = 5 - the numbers from the psychic
- j = 3 - the number of winning numbers from n
- k = 3 - the number of slots on the ticket
- l = 2 - the number of matches needed to get a prized
What makes this case simple is the fact that all the numbers on the ticket must be between 1..5. This is because j=k, meaning the number of winning numbers falling between 1 and 5 matches the number of slots on the ticket.
So take the tickets {1, 2, 3} and {1, 4, 5}. That does indeed mean you're missing the match {3, 5} but if the numbers {3, 5} are on the ticket then the other number on the ticket must be from the set {1, 2, 4}. If its the 1 then the match 3 has been picket up by the first ticket, if its the 2 then then same, if its the 5 then the second ticket catches it.
Problem
I am reading the Algorithm Design Manual by Steven S. Skiena. I am in the first chapter reading about the lottery ticket problem. Skiena claims his first solution for the optimal number of tickets for a guaranteed win was incorrect. I do not understand how his next and final solution is correct? In figure 1.11 he says: Guaranteeing a winning pair from `{1,2,3,4,5}` using only tickets `{1,2,3}` and `{1, 4, 5}` and there is a diagram. I am confused why the other numbers are not in there? For example, what if the winning numbers were `(3,4)`, `(2,4)`, `(2,5)`, `(3,5)`, etc...? You obviously cannot combine tickets together, so how can this be explained? In the lottery, if the winning numbers were 3 and 5, you must have one ticket that has a 3 and 5 in some order. Can someone please explain?