1
$\begingroup$

A specific lottery "reverse keno" is where you pick 10 numbers on a/each ticket. If none of your numbers are chosen as one of the 10 numbers the lottery hoster picks, then you win. What is the minimum number of tickets you need to ensure a win on a ticket, if you pick carefully?

I have proved that 30 tickets work solidly with the following argument:

Pick your first 10 tickets with different sets of numbers, so 1-10, 11-20, 21-30, etc to 91-100. For all of these 10 sets/tickets to be knocked out, the lottery must pick one different number from each of the 10 sets; i.e. 1, 11, 21, 31...91. This MUST happen or else one of these tickets gets off scot-free.

Now pick 2 of these 10 sets. It doesn't matter which two as long as you still do it correctly, but for clarity's sake I'll use 1-10 and 91-100. There are combination 10 choose 9 ways = 10 ways to pick a group of 9 numbers from the set 1-10, and this ensures that one of these sets excludes the number that that ticket picks. So, if the number drawn for 1-10 was "1", there is the set 2-10 that excludes the picked number.

So now you have one more number to add to each group of 9 numbers. Pick any two different numbers from the second set of numbers you chose earlier (in this case 91-100). So the last two numbers can be 91 and 92. Since the lottery can only pick 1 number from each of the original 10 ticket sets, 91 and 92 cannot be both chosen without letting one of the other tickets win. Therefore we have a guaranteed winning ticket. This totals to:

10 original tickets + 10 * 2 tickets that contain the group of 9 (and the last number being 91 or 92) = 10 + 20 = 30.

So 30 tickets work.

Is there an even smaller number that will work?

$\endgroup$
2
$\begingroup$

The first ten tickets are chosen correctly. If after those tickets you do not win, then there must have been precisely one chosen from each group. So you add the tickets:

  • 1-5, 11-15
  • 1-5, 16-20
  • 6-10, 11-15
  • 6-10, 16-20

One of these will contain two of the hoster's numbers, two will contain one number, and one will contain no number. So 14 tickets suffice.

$\endgroup$
  • $\begingroup$ I think you meant 16-20 on the last bit there. Otherwise, great response, thank you! $\endgroup$ – mathflair Dec 30 '15 at 18:45
  • $\begingroup$ Thanks for the correction. Yeah, I don't know how that happened: I thought I copy-and-pasted it from the first line... But also, this can in fact be shown to be the optimal algorithm. $\endgroup$ – Alex Dec 30 '15 at 18:54
  • $\begingroup$ P.s. Sorry, I was out. But I did. :) $\endgroup$ – mathflair Dec 31 '15 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.