Avoid unecessary subsets from a set when aiming prizes of lower order

Question

_{Crossposted at MathOverflow}

---

I have a Lottery app and I'm implementing a feature to optimize the number of bets that are necessary to cover a subset of numbers since they can repeat on several bets.

What I have:

Supposing a lottery where you can select 6 numbers from 1 to 60. Then, 6 numbers are draw and you win if you correctly guess 4 or 5 or all 6 numbers.

When creating a bet, you can "emulate" a bet with 9 numbers by finding all possible combinations with them (combination without repetition). In this example:

$$ C_{6}^{9} = \frac{n!}{k!(n-k)!} = \frac{9!}{6!(9-6)!} = 84 $$

In other words, I need to create 84 bets to cover all combinations of 6 numbers among those 9.

I've already created the code to calculate and find all combinations.

Feature I want to implement

Supposing I not interested in the main prize (6) but on the lowest prize: 4. In this case, I don't need to create all 84 bets. With fewer bets, I can cover all combinations of 4 numbers from those 9 I started.

In the end, I want two things:

1. Find the minimum amount of bets (with 6 numbers) I need to create in order to cover all possible combinations of 4 numbers among those 9.

2. Generate those bets.

Some example

I found some samples on the internet but I didn't manage to implement the algorithm or find the math behind it. In the sample I found:

The 9 numbers I want to bet: $$ S = \\{ 07, 12, 24, 32, 37, 41, 42, 54, 55 \\} $$

Instead of creating 84 bets, I can create 12 bet and I would still win the 4-numbers prize if 4 of those 9 numbers are correct.

Result

$T_1 = \\{ 07, 12, 24, 32, 37, 41 \\}$	$T_2 = \\{ 07, 12, 24, 42, 54, 55 \\}$	$T_3 = \\{ 07, 12, 32, 37, 42, 54 \\} $
$T_4 = \\{ 07, 12, 32, 41, 54, 55 \\}$	$T_5 = \\{ 07, 12, 37, 41, 42, 55 \\}$	$T_6 = \\{ 07, 24, 32, 37, 54, 55 \\}$
$T_7 = \\{ 07, 24, 32, 41, 42, 55 \\}$	$T_8 = \\{ 07, 24, 37, 41, 42, 54 \\}$	$T_9 = \\{ 12, 24, 32, 37, 42, 55 \\}$
$T_{10} = \\{ 12, 24, 32, 41, 42, 54 \\}$	$T_{11} = \\{ 12, 24, 37, 41, 54, 55 \\}$	$T_{12} = \\{ 32, 37, 41, 42, 54, 55 \\}$

I would appreciate if someone give some direction because I'm not being able to move forward

Answer 1

$~\displaystyle \binom{9}{4} = 126~$ and $~\displaystyle \binom{6}{4} = 15.~$

This implies that it will take at least $~\displaystyle \left\lceil ~\frac{126}{15} ~\right\rceil = 9~$ (i.e. the ceiling function) separate 6-ticket bets to cover all combinations of $~4~$ numbers.

My approach was to

• index the elements as $~1,2,3,\cdots,9.$

• investigate various partitions of $~\{1,2,\cdots,9\}~$ into 3 subsets, with 3 elements in each subset.

• write a program to sanity check how I was doing.

So, I started with the partition of

P01 = 123   P02 = 456   P03 = 789

Then, I created three tickets as

P01--P02  P01--P03  P02--P03

I started with $~\displaystyle \binom{9}{4} = 126~$ 4-groups that had to be eliminated, where the best that I could hope for on each 6-ticket was deducting 15 more 4-groups.

The above three 6-tickets took the un-written 4-groups from $~126~$ down to $~81,~$ which signified that these three 6-tickets were functioning perfectly.

Then, I added the partition of

P04 = 147   P05 = 258   P06 = 369

Then, I created three tickets as

P04--P05  P04--P06  P05--P06

The above three 6-tickets took the un-written 4-groups from $~81~$ to $~69~$ to $~57~$ to $~45,~$ which signified that these three 6-tickets were not functioning perfectly, but might (or might not) be the best that I could do.

At this point, I visually inspected the $~45~$ missing 4-groups. This suggested (perhaps wrongly) that I should keep the existing two partitions in place, and re-examine the original tableau.

Doing this, I went diagonally down and to the right to create a third partition:

123           P07 = 159
456  ===>>>   P08 = 267
789           P09 = 348

Then, I created three tickets as

P07--P08  P07--P09  P08--P09

The above three 6-tickets took the un-written 4-groups from $~45~$ to $~18,$ which signified that these three 6-tickets were not functioning perfectly, but (again) might be the best that I could do.

Visually inspecting the $~18~$ missing 4-groups, I did not see any way that they could be hit with only two more 6-tickets. So, I repeated the previous strategy, creating a new partition. This time, I went diagonally down and to the left to create a fourth partition:

123           P10 = 168
456  ===>>>   P11 = 249
789           P12 = 357

Then, I created three tickets as

P10--P11  P10--P12  P11--P12

This brought the missing 4-groups down to $~0.~$ I then compared my 12 tickets with the 12 tickets of the original poster. They matched exactly.

My instinct is that this type of problem should be attacked by looking for symmetrical approaches, and by using computer assistance to look for patterns in the partial results.

I have no opinion whether the 6-ticket count of $~12~$ can be improved. Nor do I have an opinion on whether deeper analysis (as opposed to trial-and-error computer assistance) is viable.