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

Question

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
                add a random number from pool\{quadri} to quadri to form a combination of 5
            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.

Answer 1

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$.