Minimum number of containers needed to express every combination of 2 integers, given a contain size m and n integers to fill them with.

52 Views Asked by At

Example: Given $n=20$ there are $C(20,2) = 190$ possible combinations of two integers. Now let's assume we have a container that can fit 18 integers in it. By filling it with 1-18 we can express $C(18,2) = 153$ of the possible $190$. Hence, our first set is:

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

Now we must add more containers to express the $37$ remaining combinations involving $19$ and $20$ that were not expressed in the first container. As duplicates do not matter and the set must be full, we get the next container as:

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

As we had to remove $17$ and $18$ to provide space for $19$ and $20$, we are missing the combinations of ${(17,19),(17,20),(18,19),(18,20)}$. So we have one last container:

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

We needed a minimum of three containers to express all $C(20,2) = 190$ combinations. Is there a general formula for the minimum number of containers given $n$ and $m$ such that $n>m$.

Possible Solution:

$$Containers = C(\lceil \frac{n}{0.5 \cdot m} \rceil , 2) $$