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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
1
|
||||||||||||||||
|
|
1
|
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$. |
|||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
0
|
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. |
|||||||||||
|
|
1
|
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 |
||
|
|
