co.combinatorics - Picking collections to get over half the number of each type of object

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.

• Next teaching - Pedagogical question about linear algebra
• Previous at.algebraic topology - Applications of the Brown Representability Theorem