0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ If k = n and each box contains a different kind of object then we need all boxes. $\endgroup$ Aug 16, 2010 at 10:41
  • $\begingroup$ @Dan: The boxes can contain mixed types $\endgroup$
    – Casebash
    Aug 16, 2010 at 10:43
  • $\begingroup$ @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? $\endgroup$
    – Steve Kass
    Aug 16, 2010 at 14:51
  • $\begingroup$ @Steve, @Dan: Updated the question $\endgroup$
    – Casebash
    Aug 16, 2010 at 20:46
  • $\begingroup$ 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. $\endgroup$ Aug 17, 2010 at 4:29

3 Answers 3

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Casebash
    Aug 17, 2010 at 7:40
  • $\begingroup$ @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. $\endgroup$ Aug 17, 2010 at 12:56
  • $\begingroup$ @Gerry: His argument seems to assume no mixed types. If it works for mixed types, it needs to be expanded $\endgroup$
    – Casebash
    Aug 18, 2010 at 6:22
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The boxes may contain mixed types - ie. a box may have an apple and an orange $\endgroup$
    – Casebash
    Aug 17, 2010 at 7:43
  • $\begingroup$ @Casebah-- but if boxes contain more than one item, that only makes it easier to get all the items you need. $\endgroup$ Aug 18, 2010 at 15:06
  • 1
    $\begingroup$ 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... $\endgroup$ Aug 19, 2010 at 2:30

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.