# How to find a set of combinations of 5 that cover all the combinations of 3 once?

I have a set of n numbers (e.g. 1 to n). For the sake of clarity, in the remaining I will use n = 10.

From these 10 numbers there is $$\binom{10}{3} = 120$$ combinations of 3, for instance (1, 3, 5), (3, 5, 10),...

Every combination of 5 covers 10 combinations of 3, as $$\binom{5}{3} = 10$$. For instance (3, 6, 10, 4, 7) covers : (3, 6, 10), (3, 6, 4), (3, 6, 7), (3, 10, 4), (3, 10, 7), (3, 4, 7), (6, 10, 4), (6, 10, 7), (6, 4, 7) and (10, 4, 7).

What I am trying to do is to generate a set of combinations of 5, that cover all the combinations of 3 once. Since there is 120 combinations of 3 and each combination of 5 covers 10 combinations of 3, I assume that I can reach my goal with 12 combinations of 5 but I am still struggling to find a way to do that.

I tried a method, but it always fails as I keep ending up with more than 12 combinations of 5 and therefore some combinations of 3 being covered more than once. Here is the pseudo code that I used.

pool: set of numbers (here 1 to 10) allComb3: list of all the (120) combinations of 3
uncoveredComb3: list of combinations of 3 not yet covered, this list is initially equal to allComb3. As combination of 3 get covered, this list shrinks until it is empty.
candidatesFor4th: for a given (not covered) combination of 3, this is a list of numbers such that when any of them is appended to the combination of 3, it forms a combination of 4, that covers (4) uncovered trinoms (those still found in uncoveredComb3)
candidatesFor5th: for a given combination of 4, this is a list of numbers such that when any of them is appended to the combination of 4, it forms a combination of 5 that covers (10) uncovered trinoms (those still found in uncoveredComb3)

while there are members of allComb3 not covered
for member in allComb3
if member is covered
go to next member
else
look for candidatesFor4th
if candidatesFor4th is not empty
Select randomly one number from candidatesFor4th to form a combination of 4: quadri
else
add a random number from pool\{member} to member to form a combination of 4: quadri
end if

look for candidatesFor5th
if candidatesFor5th is not empty
Select randomly one number from candidatesFor5th to form a combination of 5
else
end if
end if
end for
end while


Implementing this algorithm (in matlab) never led to hit the goal. For instance it can yield 19 combinations of 5 with some of the combinations of 3 covered 4 times, many others covered twice. Is there another way of solving this? Any suggestion on how to achieve this would be greatly appreciated. Thanks in advance.

• You only really know you have to have $12$ or more such $5$-sets. Oct 9, 2021 at 23:51
• For example, there are $8$ triples that contain $\{1,2\},$ so you need at least $3$ $5$-sets to cover those $8.$ But that means there is one of those triples covered more than once. So you are going to need at least $13.$ Oct 10, 2021 at 0:11

What you are looking for is called a covering design. Let $$N$$ be a set of size $$n$$. If we let $$C(n,k,t)$$ be the size of the smallest collection of subsets of $$N$$ of size $$k$$, such that every subset of size $$t$$ is contained in a set in the collection, then you are looking for $$C(n,5,3)$$. It is a hard open problem to determine this number in general, but Dan Gordon maintains a table of small covering designs and known bounds at https://www.dmgordon.org/cover/. For example, if you fill in $$v=10$$, $$k=5$$ and $$t=3$$ at that page, you will receive a covering design using $$17$$ sets, along with matching lower bound of $$C(10,5,3)\ge 17$$, so the covering is optimal. He seems to have coverings for up to $$n=99$$.