How many tickets are needed to guarantee at least one winning ticket?

Question

In a special sort of lottery called reverse keno, a player buys a ticket on which he selects 10 numbers from 1-100 inclusive. Then, 10 numbers are drawn at random. The player wins if his ticket contains none of the numbers which are drawn. How many tickets are needed to guarantee at least one winning ticket regardless of the numbers drawn?

Answer 1

As I explained in the comment, my reasoning is as follows: first we find the number of possible losing tickets, say $k$, and then buy $k+1$ different tickets. This way you MUST have at least one winning ticket.

Now the challenge is finding the number of possible losing tickets.

Number of losing tickets = (Total possible tickets) - (Number of winning tickets)

Let's say that you can choose repeated numbers in the same draw, for Ex: $1,2,3,4,5,5,5,5,6,7$

The total number of tickets is: $100^{10}$ since there are 10 slots, and each one has 100 possible numbers to choose from.

The number of winning tickets is: $90^{10}$ since there are 10 slots and each one has 90 possible numbers to choose from. ($10$ of the $100$ numbers will result in a losing ticket, thus $100-10=90$ total possible valid numbers)

Therefore the minimum number of (different) tickets needed to guarantee a win is: $$100^{10}-90^{10}+1$$

A similar argument can be applied if repetitions are not allowed.

Answer 2

Rather than a guarantee of at least one winning ticket, would you be willing to accept a very low probability of not having at least one winning ticket? If so, below is a simple strategy that requires buying twenty tickets. It doesn't guarantee your having at least one winning ticket, but the probability that the strategy will fail is very low, about $2 \times 10^{-7}$.

The strategy is this: buy ten tickets with numbers $1, 2, 3, \dots ,10$ on the first ticket, $11, 12, 13, \dots ,20$ on the second ticket, etc., on up to $91,92,93, \dots ,100$ on the tenth ticket. Buy another ten tickets with numbers $1, 11, 21, ..., 91$ on the first ticket, $2, 12, 22, ..., 92$ on the second ticket, etc., on up to $10, 20, 30, \dots , 100$ on the tenth ticket.

What is the probability that a person holding these twenty tickets will not have any winner? Well, there are $\binom{100}{10}$ possible sets of ten numbers drawn in the lottery. (I am assuming the numbers are drawn without replacement, as is normal for lotteries.) How many of these drawings result in failure of the twenty ticket strategy? If the strategy fails, the ten numbers drawn must include at least one number on each of the twenty tickets. Think of the numbers on the twenty tickets as arranged in a ten by ten array, like this:

$$\begin{array}{ccccc} 1 &2 &3 &\cdots &10 \\ 11 &12 &13 &\cdots &20 \\ 21 &22 &23 &\cdots &30 \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 91 &92 &93 &\cdots &100\\ \end{array}$$ The numbers on the first set of ten tickets form the rows of the array, and the numbers on the second set of ten tickets form the columns. If the ten numbers drawn in the lottery include at least one number from each of the twenty tickets, then they must include one number in each row and one number in each column. The number of such arrangements is $10!$, so the associated probability is $$\frac{10!}{\binom{100}{10}} = 2.09632 \times 10^{-7}$$