Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
If k = n and each box contains a different kind of object then we need all boxes. –  Dan Brumleve Aug 16 '10 at 10:41
    
@Dan: The boxes can contain mixed types –  Casebash Aug 16 '10 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? –  Steve Kass Aug 16 '10 at 14:51
    
@Steve, @Dan: Updated the question –  Casebash Aug 16 '10 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. –  Gerry Myerson Aug 17 '10 at 4:29
add comment

3 Answers 3

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

share|improve this answer
    
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 –  Casebash Aug 17 '10 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. –  Gerry Myerson Aug 17 '10 at 12:56
    
@Gerry: His argument seems to assume no mixed types. If it works for mixed types, it needs to be expanded –  Casebash Aug 18 '10 at 6:22
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
The boxes may contain mixed types - ie. a box may have an apple and an orange –  Casebash Aug 17 '10 at 7:43
    
@Casebah-- but if boxes contain more than one item, that only makes it easier to get all the items you need. –  Hugh Thomas Aug 18 '10 at 15:06
1  
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... –  Aaron Meyerowitz Aug 19 '10 at 2:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.