0
$\begingroup$

I have 10 boxes, and each box can hold items. I also have 5 different types of objects. Each item can hold 2 objects.

No box can hold more then 1 of the same object, but it is possible for it to hold none. Also each object should be paired with the each other type of object as well (but only once). What is an algorithm to determine the least amount of boxes required to store the all combinations of objects?

Worst case:

B1 -> [O1 O2]
B2 -> [O1 O3]
B3 -> [O1 O4]
B4 -> [O1 O5]
B5 -> [O2 O3]
B6 -> [O2 O4]
B7 -> [O2 O5]
B8 -> [O3 O4]
B9 -> [O3 O5]
B10 -> [O4 O5]

Best Case (What I want to achieve):

B1 -> [O1 02] [O3 O4] 
B2 -> [O1 O3] [O4 05]
B3 -> [O1 04] [O2 O5] 
B4 -> [O1 O5] [O2 04]
B5 -> [O3 O5] [O2 04]

The number of boxes, types of objects can both change. While for the sake of the actual formula the number of objects per item can change, I only need to deal with the scenario where there is 2.

$\endgroup$
1
$\begingroup$

If you have $n$ kinds of object, there are $\frac 12n(n-1)$ pairs of objects. Each box can hold $\lfloor \frac n2 \rfloor$ pairs. If $n$ is even, you could hope to get by with $n-1$ boxes. If $n$ is odd, you need $n$ boxes. To prove we can make this work for the even case, imagine a long table. Put item $0$ at one end and all the rest around the table in order. Each object gets paired with the one facing it. That is your first boxs. Now leave $0$ fixed and have each object move one seat clockwise. Again pair facing objects and that makes your second box. Keep going and after $n-2$ movements you have all the pairs. For odd $n$, do the same for $n+1$ and delete the pair including $n+1$ The bridge players call this a Howell movement.

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