# Can number of choices be non-integer?

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?

• 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 6 '16 at 19:58
• @HenningMakholm - C(22,10) is number of ways to match my 10 numbers with the 22 numbers drawn. – user231343 Apr 6 '16 at 19:59
• @HenningMakholm - the first one! I'll edit. Thanks – user231343 Apr 6 '16 at 20:00
• 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 6 '16 at 20:00
• 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 6 '16 at 21:01

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.

• Thank you. But how to calculate the "real" or "greatest" lower bound? – user231343 Apr 6 '16 at 23:24
• 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 6 '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 6 '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. – user231343 Apr 6 '16 at 23:38
• 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 6 '16 at 23:57

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.

• $\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 :-) – user231343 Apr 6 '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 6 '16 at 20:16