1
$\begingroup$

We make combinations of 4 distinct numbers (without repetition) out of $[1..20]$ integer range.

We need to identify minimal (in terms of number of 4-combinations) combination sets which cover all $190$ pairs in that range (numbers in $[1..20]$ range make $binomial(20,2)$ pairs).

It means that each 4-numbers combination shall contain such 6 pairs that were absent in all previously chosen 4-numbers combinations.

Given 190 pairs in total and that each 4-numbers combination has exactly 6 pairs, $190/6$ = 32 4-numbers combinations guarantee that we covered all pairs - it means that there is such a 32-combination set that if we have it, then whatever 4 numbers are given from the range, our set is 100% to contain at least 1 pair (out of 6 pairs from the given 4 numbers).

I need an algorithm helping to generate such sets and I'd like to understand how many such sets can I make and what I can vary:

there are $binomial(20,4) = 4845$ total 4-number combiantions so there could be $4845 / 32$ = 151 such sets.

Here are all those 190 pairs:

[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[1, 7]
[1, 8]
[1, 9]
[1, 10]
[1, 11]
[1, 12]
[1, 13]
[1, 14]
[1, 15]
[1, 16]
[1, 17]
[1, 18]
[1, 19]
[1, 20]
[2, 3]
[2, 4]
[2, 5]
[2, 6]
[2, 7]
[2, 8]
[2, 9]
[2, 10]
[2, 11]
[2, 12]
[2, 13]
[2, 14]
[2, 15]
[2, 16]
[2, 17]
[2, 18]
[2, 19]
[2, 20]
[3, 4]
[3, 5]
[3, 6]
[3, 7]
[3, 8]
[3, 9]
[3, 10]
[3, 11]
[3, 12]
[3, 13]
[3, 14]
[3, 15]
[3, 16]
[3, 17]
[3, 18]
[3, 19]
[3, 20]
[4, 5]
[4, 6]
[4, 7]
[4, 8]
[4, 9]
[4, 10]
[4, 11]
[4, 12]
[4, 13]
[4, 14]
[4, 15]
[4, 16]
[4, 17]
[4, 18]
[4, 19]
[4, 20]
[5, 6]
[5, 7]
[5, 8]
[5, 9]
[5, 10]
[5, 11]
[5, 12]
[5, 13]
[5, 14]
[5, 15]
[5, 16]
[5, 17]
[5, 18]
[5, 19]
[5, 20]
[6, 7]
[6, 8]
[6, 9]
[6, 10]
[6, 11]
[6, 12]
[6, 13]
[6, 14]
[6, 15]
[6, 16]
[6, 17]
[6, 18]
[6, 19]
[6, 20]
[7, 8]
[7, 9]
[7, 10]
[7, 11]
[7, 12]
[7, 13]
[7, 14]
[7, 15]
[7, 16]
[7, 17]
[7, 18]
[7, 19]
[7, 20]
[8, 9]
[8, 10]
[8, 11]
[8, 12]
[8, 13]
[8, 14]
[8, 15]
[8, 16]
[8, 17]
[8, 18]
[8, 19]
[8, 20]
[9, 10]
[9, 11]
[9, 12]
[9, 13]
[9, 14]
[9, 15]
[9, 16]
[9, 17]
[9, 18]
[9, 19]
[9, 20]
[10, 11]
[10, 12]
[10, 13]
[10, 14]
[10, 15]
[10, 16]
[10, 17]
[10, 18]
[10, 19]
[10, 20]
[11, 12]
[11, 13]
[11, 14]
[11, 15]
[11, 16]
[11, 17]
[11, 18]
[11, 19]
[11, 20]
[12, 13]
[12, 14]
[12, 15]
[12, 16]
[12, 17]
[12, 18]
[12, 19]
[12, 20]
[13, 14]
[13, 15]
[13, 16]
[13, 17]
[13, 18]
[13, 19]
[13, 20]
[14, 15]
[14, 16]
[14, 17]
[14, 18]
[14, 19]
[14, 20]
[15, 16]
[15, 17]
[15, 18]
[15, 19]
[15, 20]
[16, 17]
[16, 18]
[16, 19]
[16, 20]
[17, 18]
[17, 19]
[17, 20]
[18, 19]
[18, 20]
[19, 20]
$\endgroup$
2
$\begingroup$

You want to solve what is sometimes called the $(n,4,2)$ design cover problem.

This problem was settled in a series of two papers by W.H MIlls.

paper 1

paper 2

As you can see the result is that $C(n,4,2) = \lceil \frac{n}{4} \lceil \frac{n-1}{3} \rceil \rceil$ for all $n$ except $7,9,10$ and $19$.

We hence conclude the minimum number of sets we can have is $\lceil 5 \times 7 \rceil=35$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

There is no such set of $32$ subsets of $\{1,\ldots,20\}$. Such a set would contain $32\times\binom{4}{2}=192$ pairs, and hence to contain all $\binom{20}{2}=190$ pairs there are at most two pairs that are included more than once. Hence there is an element such that all pairs containing it are included precisely once. There are of course $19$ pairs in $\{1,\ldots,20\}$ containing it. But the number of pairs from the $32$ sets containing it is a multiple of $3$; for each of the $32$ sets containing it there are three pairs, and by assumption/construction they are all distinct. A contradiction; no such collection of $32$ sets exists.

————————————————-

Your argument implicitly assumes that any $6$ pairs from $\{1,\ldots,20\}$ can be obtained as the set of pairs from a $4$-tuple, but this is of course not true.

The argument above shows that each element must be contained in at least $7$ sets, and hence that you will need at least $35$ sets.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.