In a lottery game, there are 5 numbers drawn out of 90. How many tickets do I need, and how do I fill them out, for making sure I will have 4 matches?
You are asking for the domination number[1] of a certain Johnson graph[2] (please, no Big Lebowski jokes). In standard notation, this number is denoted [math]gamma(J(90,5))[/math].(Note: I'm assuming that the u201c5 numbers drawn out of 90u201d are all different, which I believe is the case in most lotteries).The Johnson graph [math]J(90,5)[/math] is the graph whose vertices correspond to all the [math]5[/math]-element subsets of [math]{1,2,ldots,90}[/math], and two vertices are adjacent (connected with an edge) whenever the corresponding sets have [math]4[/math] elements in common. For example, [math]{2,3,5,8,13}[/math] is adjacent to [math]{2,3,8,13,77}[/math] but not to [math]{2,3,5,9,14}[/math].A dominating set for a graph is a set of vertices that is adjacent to each vertex not in the set. If you have a dominating set of tickets for [math]J(90,5)[/math], whatever the winning combination turns out to be has at least [math]4[/math] matches with a ticket in your hand.Calculating the size of a minimal dominating set, called the domination number, is computationally hard (the corresponding decision problem is NP-complete), and our graph [math]G=J(90,5)[/math] is no peanut: it has [math]N=binom{90}{5}=43, 949, 268[/math] vertices, each with [math]d=5(90-5)=425[/math] neighbors.Of course, [math]G[/math] is a very specific and highly symmetric graph, so it's entirely possible that a minimal dominating set for it, or at least a relatively small dominating set, can be determined explicitly using some reasoning particular to this case.As with any optimization problem, we can pursue two competing paths: we may seek upper bounds by exhibiting some good dominating sets, and we can seek lower bounds by attempting to prove that every dominating set must be at least as large as some size [math]B[/math].Since the degree of [math]G[/math] is [math]425[/math], a dominating set must have at least [math]N/425[/math] elements, which sets a lower bound of [math]B=103, 411[/math] tickets. With fewer tickets than this you stand no chance of guaranteeing a four-element match. I suspect there is, in fact, a dominating set of this size, or very close to it.An equally obvious upper bound is obtained by simply scanning all [math]4[/math]-number combinations [math](a,b,c,d)[/math] in our range and filling in the fifth number arbitrarily. This yields a dominating set of size [math]binom{90}{4}[/math]. That's about 2.5 million tickets, which is far more than the theoretical lower bound, but it's also far less than the 43 million possible winning combinations.Of course, this is very wasteful. We made no use of the fact that each ticket can cover five [math]4[/math]-number combinations, not just one. A better approach is to use a standard trick in design theory or coding theory: impose a linear constraint.Specifically, consider those combinations where the sum of the numbers is divisible by [math]90[/math]. About [math]1/90[/math] of the combinations are special like that (The exact number is [math]488, 326[/math], which is just [math]N/90[/math] rounded up).Suppose you filled tickets with all of these special combinations. If the winning one happens to be special, you got it. If it's not, then in almost all cases it has four numbers in common with not only one but five of your special combinations.The reason is that given any winning combination [math]{a,b,c,d,e}[/math], you can keep [math]a,b,c[/math] and [math]d[/math] intact and find an appropriate fifth number [math]x[/math] (instead of [math]e[/math]) which makes the sum [math]a+b+c+d+x[/math] divisible by [math]90[/math]. The combination [math]{a,b,c,d,x}[/math] is then in your hand, unless it so happens that [math]x[/math] is identical to one of [math]a,b,c,d[/math]. In this case you can try picking another element of the winning combo, say [math]d[/math], and try [math]{a,b,c,y,e}[/math] whose sum is divisible by [math]90[/math]. Once again, we just need to hope that [math]y[/math] isn't identical to one of the other four numbers.For example, suppose the winning combination was [math]{1,2,3,42,60}[/math]. The quadruplet [math]{1,2,3,42}[/math] is nowhere to be found among the special combinations, because the missing fifth number would have been [math]42[/math] itself. However, that's ok because [math]{1,2,3,24,60}[/math] is special, and matches four of the numbers in the winning combination. We can't u201cfixu201d the [math]60[/math], but we can fix any of the other numbers.In very rare instances, a winning combination may not be u201cfixableu201d at all. For example, suppose that the lottery was played with three numbers instead of five. The winning combination [math]{10,40,70}[/math] cannot be modified into a special combination by changing any single number.If that had happened in our case, we would simply have added a few tickets to cover for those pathological cases. But I'm quite sure that's not necessary: as far as I can tell there arenu2019t any u201cbadu201d combinations of five numbers in the range 1 through 90.The set of special tickets guarantees winning the lottery, but itu2019s still about 4.7x larger than the theoretical lower bound. This isn't surprising because, as we said, most winning combinations are actually covered by 5 of our tickets, though sometimes it's just 4. That's where this factor of 4.7 comes from.We can seek various pruning techniques to find winning sets of fewer tickets, but I couldn't yet find one that'll take you down to around 110,000 tickets. I'm 100% sure this is addressed in the literature, and I'll update this answer if I find anything.Footnotes[1] Dominating set - Wikipedia[2] Johnson graph - Wikipedia
