I think Gerry's answer is correct.
If there are any empty boxes, they can be ignored. Say we have $k$ types of items with $n_1, ..., n_k$ items of each time. Suppose we need less than $M$ boxes for this distribution. Consider adding $n_{k+1}$ items of a new type $k + 1$. At worst, these items can be placed in new boxes, with one item per box. In that case, we will need $lceil frac{n_{k + 1}}{2} rceil$ new boxes. Thus, by induction the most boxes we will need, assuming each box contains one item is:
$$lceil frac{n_1}{2} rceil + ... + lceil frac{n_{k+1}}{2} rceil leq frac{n_1 + ... + n_{k + 1}}{2} + frac{k}{2} leq frac{n + k}{2}$$
If more than one item is placed per box, then the number of boxes we need will not increase. Hence the upper bound is solid and by Gerry's argument tight.
No comments:
Post a Comment