1

In some lottery, the entry numbers are from $1$ to $80$ inclusive and $22$ numbers are chosen among them. In a ticket someone can choose $10$ numbers and if his or her $10$ numbers exist among the drawn $22$ numbers he or she wins the jackpot. No repetitive selection is allowed either is draw or ticket.

So the question is "How many combinations of 10 numbers do you need to play in order to be sure to win?" or in other words "At least how many distinct tickets I have to buy in order to be sure to win?" The answer is (?) : $$\dfrac {C(80,10)}{C(22,10)} = \dfrac {1646492110120}{646646} \simeq 2546203.1933$$ which surprisingly is not integer! If this calculation is correct HOW that's possible and if not where was I wrong?

  • 1
    Is the question you're trying to answer: "How many combinations of 10 numbers do you need to play in order to be sure to win?" or "How many possible combinations of 10 numbers are there?" – hmakholm left over Monica Apr 06 '16 at 19:58
  • @HenningMakholm - C(22,10) is number of ways to match my 10 numbers with the 22 numbers drawn. –  Apr 06 '16 at 19:59
  • @HenningMakholm - the first one! I'll edit. Thanks –  Apr 06 '16 at 20:00
  • 2
    Your fraction is the expected number of tickets required to win once, on average, not the total number of possible tickets. As such, it's not surprising that this isn't integral. Try smaller numbers to understand the mechanics: Imagine a Keno game where there are numbers $1$ through $10$, and you pick $2$ of them, hoping that they will fall within the $4$ numbers selected by the game-master. There are $45$ different two-number tickets, of which only $6$ can be winners. The fact that $6$ doesn't divide $45$ is not a paradox. – Brian Tung Apr 06 '16 at 20:00
  • @BrianTung: For that interpretation, the denominator should have been the number of different draws a given ticket can win for, which is $\binom{80-10}{22-10}$, not $\binom{22}{10}$. The latter is the number of different tickets that will win in a given draw. – hmakholm left over Monica Apr 06 '16 at 20:03
  • @BrianTung so I have calculated 45/6 instead of 6? If so, I still struggle to come up with number 6 ! How did you get 6? –  Apr 06 '16 at 20:06
  • That's what's called a "lower bound" for the number of tickets you need to buy, so it need not be an integer. Try the same problem, where the lottery just picks a number from one to $100$ and your ticket has six numbers, and you win if one of your numbers is the number picked. Then the minimum number of tickets needed to ensure a win would be $100/6$. The fact that 100/6 is not an integer means that the "actual" minimum number of tickets you need to buy is 17>100/6$. – Thomas Andrews Apr 06 '16 at 20:46
  • @ThomasAndrews - No way! suppose that the drawn number is 1 (and I don't know it yet). I select 6 number among 2, ..., 100. How many possibilities : C(99,6) meaning that if I had bought 1120529256 tickets each of them doesn't have 1 in it still I won't win let alone 17 tickets! –  Apr 06 '16 at 20:56
  • 1
    Well, sure, if you pick the tickets at random. The assumption is that you are trying to cover all 100 options of winning. You can't cover them with $16$ tickets, and you see that by noting that $100/6$ is bigger than sixteen. But there is a way to pick 17 tickets to cover all 100 possible results. @Edi – Thomas Andrews Apr 06 '16 at 21:01
  • @ThomasAndrews - I know what is that way! not repetitive number in another ticket. Thanks a lot. Very informative. :) –  Apr 06 '16 at 21:05

2 Answers2

0

What you're computing there is a lower bound for the number of tickets you need to buy. Your computation shows -- if you fix it so the denominator is $\binom{70}{12}$ rather than $\binom{22}{10}$, namely the number of different draws that a single ticket gives win chances for -- that if you buy fewer tickets than the number you get, there will necessarily be possible draws that are not covered by any of your tickets.

What your argument doesn't show is that that this number of tickes -- even if it were an integer -- are enough. It would be enough if you could choose your tickets such that there is no overlap between the set of lucky draws between any two of your tickets. But nobody says that is possible, and in fact for this game it is very impossible. You can't even choose two tickets to play that can't win simultaneously, because those two tickets have at most 20 numbers on them together, and those 20 numbers can all appear in the same draw.

In probability terms, $p={\binom{70}{12}}\big/{\binom{80}{22}}$ is the chance of any given ticket winning. You're trying to reach a winning chance of $1$ by buying $1/p$ different tickets. But in order for that to work, you need to add the probabilities of each of the tickets winning, and that is only valid if the win event for each of your tickets are mutually exclusive. And that is generally impossible here.

hmakholm left over Monica
  • 286,031
  • $\dfrac {C(80,10)}{C(70,12)}$ is still non-integer. But, I am reading your answer again because I couldn't understand it well :-) –  Apr 06 '16 at 20:15
  • @Edi: And so what? All it says is a lower bound for the true answer. It doesn't need to be an integer in order to be a lower bound. – hmakholm left over Monica Apr 06 '16 at 20:16
0

Always best to look at smaller examples for questions like this.

Let's play a lottery where you pick three numbers from $\{1,2,3,4,5\}$ and the lottery drawing is a pair of numbers from the same set. You win if the pair of numbers are both in you selection.

There are $\binom{5}{2}=10$ pairs of numbers. Each ticket you buy "covers" three pairs of numbers. So you cannot cover all pairs with $3$ tickets. You need at least $10/3$ tickets. Now, $10/3$ is not an integer, it is just a "lower bound" for the number of tickets you need. Since the number of tickets must be an integer, you can say the lower bound is actually $4$.

Now, can you actually cover all possible pairs with $4$ tickets? Yes, you can: $$1,2,3\\ 1,4,5\\ 2,4,5\\ 3,4,5$$

Now, ever pair is covered by at least one ticket, so if you buy these four tickets, you are sure of at least one ticket winning.

However, there was nothing guaranteeing that these tickets existed. The numerical calculation I did to get $10/3$ was fairly crude.

For example, if you pick three numbers from $\{1,2,3,4\}$ and the lottery picks two from $\{1,2,3,4\}$ then you'd get a lower bound of $\frac{\binom{4}{2}}{\binom{3}{2}}=2$, but there is no way to pick two lottery tickets that cover all pairs.

In general, if you are picking $n$ numbers from $\{1,2,\dots,m\}$ and the lottery picks $k\leq n$ numbers, and you win if every number picked by the lottery is in your set, then you need, for $i=1,2,\dots,k$, then, if you can ensure winning with $t$ tickets, you need, for $i=1,\dots,k$:

$$t\binom{n}{i}\geq \binom{m}{i}\left\lceil\frac{(m-i)!(n-k)!}{(n-i)!(m-k)!}\right\rceil$$

That's still only lower bound, not necessarily the greatest lower bound.

For example, with $m=36$, $n=6$, $k=2$, then for $i=2$ we get $t\geq 42$ and for $i=1$ we get $t\geq 42$, but $42$ is known to not be achievable.

In fact, the question of $(m,n,k)=(n^2,n,k)$ already is an unknown question. Then $t\geq n^2+n$, and we can achieve that value when $n$ is the power of a prime, but it is unknown whether these are the only values of $n$ for which $t=n^2+n$ tickets can ensure a win.

Thomas Andrews
  • 177,126
  • Thank you. But how to calculate the "real" or "greatest" lower bound? –  Apr 06 '16 at 23:24
  • 2
    This lower bound is low-hanging fruit. The full answer is unknown to me, but it is not trivial. It's probably rarely much more than this lower bound, but I don't know how much more the greatest lower bound can be. – Thomas Andrews Apr 06 '16 at 23:28
  • It's not always that. If you pick $3$ numbers from ${1,2,3,4,5,6,7}$ and the lottery picks two numbers, then the lower bound $\binom{7}{2}/\binom{3}{2}=7$ is the greatest lower bound - you can buy $7$ tickets that cover all the pairs. The case where the lower bound is an integer leads to a part of combinatorics called "design theory" - you can reach that lower bound when a "design" exists of a certain type. – Thomas Andrews Apr 06 '16 at 23:35
  • For case {1,2,3,4,5,6}, C(6,5)/C(3,2)=5 but you have to buy 7 tickets to cover. I calculate for {1,2,3,4,5,6,7}, it's 9 tickets! : 1,2,3 - 1,4,5 - 1,6,7 - 2,4,5 - 2,6,7 - 3,4,5 - 3,6,7 - 4,6,7 - 5,6,7. –  Apr 06 '16 at 23:38
  • With tickets of $4$ numbers from ${1,2,3,4,5,6,7}$ and draws of 3 numbers, you get $35/4$ for $9$ as the rough lower bound, but I think you need at least 14 tickets to cover all triples. That because, to cover all triples, any pair, like ${1,2}$, has to be on $4$ tickets. So in $n$ tickets, you have $6n$ pairs, and there are $\binom{7}{2}=21$ pairs that you have to cover at minimum $4$ times each. So you need $6n\geq 4\cdot 21$ and thus $n\geq 14$. – Thomas Andrews Apr 06 '16 at 23:46
  • Should I upload this as a new question on MSE i.e. to determine the greatest lower bound in general say as an idea for graduate/undergraduate research project? I couldn't find in internet about it. –  Apr 06 '16 at 23:51
  • 1
    Many questions about even the design case, where this lower bound is an integer and it is the greatest lower bound - are unsolved questions. So it is definitely an area for research, but don't expect a general answer. You'll be lucky to find a new special case where you find a greatest lower bound. Unsolved questions general aren't good to post on this site, but you can ask for guidance about what is known. – Thomas Andrews Apr 06 '16 at 23:57