CODEWITHSUNDEEP
algorithm
Rob L
Rob L

Reputation: 3304

Lotto Ticket Coverage From Algorithm Design Manual?

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?

Upvotes: 19

Views: 2942

Answers (2)

Colin Jack
Colin Jack

Reputation: 776

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.

Upvotes: 22

dabei
dabei

Reputation: 187

In figure 1.11 the number of slots on each ticket is 3. So there are 3 winning numbers. With two tickets {1,2,3} and {1,4,5}, you are guaranteed to have at least 2 out of the 3 winning numbers.

Upvotes: 2

Related Questions