# Picking collections to get over half the number of each type of object

I would like to know if this question on Stack Exchange can be generalised. We generalise the problem as follows. There are k types of object and n boxes each which may contain any number of objects (a box may contain different types of objects). We are allowed to look inside the boxes, then have to select a set of boxes that contains at least half the number of each type of object. What is the least number of boxes for any given k and n to guarantee that this is possible, regardless of the distribution of the objects?

• If k = n and each box contains a different kind of object then we need all boxes. Aug 16, 2010 at 10:41
• @Dan: The boxes can contain mixed types Aug 16, 2010 at 10:43
• @Casebash: Not sure what your comment is saying. Dan is correct. Your question isn't clear, so Dan may not have answered it. Do you mean "Given a known distribution, what is the number B (which depends on the distribution) so that every subset of B boxes contains at least half of each type, and B is minimal (some B-1 boxes fail to contain half of each type)?" If this is the question, there are some distributions for which B=n (everything in one box and n-1 empty boxes), and some distributions for which B = n/2 (identical boxes). What is your question? Aug 16, 2010 at 14:51
• @Steve, @Dan: Updated the question Aug 16, 2010 at 20:46
• I think it's an interesting question if you fix $k$ and imagine $n$ large compared to $k$. For $k=1$ it's trivial; you may need $\lceil n/2\rceil$ boxes, you never need more. But for $k=2$ it's already not clear (to me) what the answer might be. I can see where you may need $(n/2)+1$, I can't see if you may need more. Aug 17, 2010 at 4:29

If $n=km$ with $m$ odd, and for each type of object you have $m$ boxes with one object of that type and no objects of the other types, then you need $(n+k)/2$ boxes. I couldn't think up any situation where you'd need more, so I'll go out on a limb and suggest that maybe $(n+k)/2$ is the answer. It certainly works in the trivial cases $k=1$ and $k=n$.

• This is only a really small subcase as the boxes can contain different types of objects. For example, if you have apples and oranges, a box may have 4 apples and 5 oranges Aug 17, 2010 at 7:40
• @Casebash, I understand that. I only claim to have established a lower bound for the correct answer. I didn't see any way that putting more than one type in a box could make things worse, but I didn't claim to have proved this. Artem does claim to have proved that mixing types in a box can't force you to use more boxes - I think you should read Artem's argument carefully. Aug 17, 2010 at 12:56
• @Gerry: His argument seems to assume no mixed types. If it works for mixed types, it needs to be expanded Aug 18, 2010 at 6:22

I agree with Gerry's conjecture. I am stymied in proving it though. I'd further conjecture that $\lfloor{k+\alpha(n-k)}\rfloor$ boxes (but no less) are always enough to get at least $\alpha$ of each type (here $0 \le \alpha \le 1$ ). I think that using the ceiling instead of the floor allows strictly greater than $\alpha$. That is true for $0 \le \alpha \le \frac{1}{n}$ but I didn't see how to continue that to an induction proof.

A reformulation which is not really any more general: You are given $n$ non-negative real vectors with sum the all ones vector, how many do you need for the sum to have all entries at least 1/2 (or $\alpha$)?. The $2^n$ points corresponding to subset sums sit in the (solid) unit k-cube (perhaps some on top of each other). Draw a segment between two points if they correspond to sets related by adding in one more vector and/or removing one. The $n$ segments leaving the origin each yield n-t congruent parallel segments going from t-sets to t+1-sets. The $\binom{n}{2}$ segments between points corresponding to 1-sets (some perhaps degenerate) each yield $\binom{n}{t-1}$ congruent parallel segments going between t-sets. The average of the points corresponding to t-sets has all entries t/n. Complementary sets are symmetric about the middle. At this point I grind to a halt

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.

• The boxes may contain mixed types - ie. a box may have an apple and an orange Aug 17, 2010 at 7:43
• @Casebah-- but if boxes contain more than one item, that only makes it easier to get all the items you need. Aug 18, 2010 at 15:06
• I don't see that mixing objects or having more than one object in a box always makes it easier. We start with n boxes and $n_1$ objects of type 1 spread between them. Clearly we take take the $\lfloor \frac{n+1}{2} \rfloor$ fullest boxes and have more than half the type 1 items. Now spread $n_2$ type 2 objects in the same boxes. Why is it obvious that we can use $\lfloor \frac{n+2}{2} \rfloor$ boxes, still have at least half the type 1 objects but also have at least half the type 2 objects? Maybe a fruitful question is How many ways are there to choose $\frac{n+k}{2}$ boxes so that... Aug 19, 2010 at 2:30