# Balls in boxes (partition)

Given 100 boxes. Each contains arbitrary number of red, blue and green balls, i.e., 100 non-negative integer triples $(r_i,b_i,g_i)$.

Prove it's always possible to find 51 boxes so that the total number of balls of each color in these boxes is no less than the ones from the rest 49 boxes.

For n boxes, replace 51 with $\lfloor(n+3)/2\rfloor$, and prove that is the best lower bound.

This is a generalization of a high-school Olympiad question, which I was told to use pigeonhole principle. Could anyone shed light on how to apply it?

EDITED: Since this is not really related to the pigeon-hole principle, I have edited the title and the tag.

Besides the solution provided by domotorp, darij grinberg pointed to an elementary proof on mathlinks.

Also domotorp has found the origin of the problem (which was sort of buried in the comments).

-
Sharpness is shown by the case of 1 ball per box with 1 red, 1 blue, and the rest green. –  Douglas Zare Jan 18 '10 at 15:53
Sorry, I'm voting to close. I don't think this question is the right level for this site. Please see the FAQ for other places to get help. –  S. Carnahan Jan 18 '10 at 17:27
Ah ok. I apologize for asking such an elementary question here (thought it would get a quick answer). I asked on mathlinks (art of problems solving), but no answers. Could anyone point to me a more appropriate discussion group for this problem? –  kiasncp Jan 18 '10 at 20:19
I don't see what's wrong with the question, actually. It has already been asked at a "lower level site" without a response. If someone asks a well-written question that we find a little too easy, usually we send the questioner off with at least a sketch of the answer. Would someone be willing to do that in this case? (I don't find the question trivial, although I haven't thought about how to answer it: combinatorics is not really my bag.) –  Pete L. Clark Jan 18 '10 at 20:39
Is this really unanswered on MathLinks? I haven't read the last post at mathlinks.ro/Forum/viewtopic.php?t=32161 in detail, but it seems to contain a proof, which seems to generalize to the $n$-boxes case. –  darij grinberg Jan 21 '10 at 12:38

This proof uses a combinatorial equivalent of the Borsuk-Ulam theorem. I think that the proof is a little more complicated than the average proofs here, so please check my related paper if you have difficulties to understand.

Octahedral Tucker's lemma. If for any set-pair $A, B\subset [n], A\cap B=\emptyset, A\cup B\ne\emptyset$ we have a $\lambda(A,B)\in\pm[n-1]$ color, such that $\lambda(A,B)=-\lambda(B,A)$, then there are two set-pairs, $(A_{1},B_{1})$ and $(A_{2},B_{2})$, such that $(A_{1},B_{1})\subset (A_{2},B_{2})$ and $\lambda(A_{1},B_{1})=-\lambda(A_{2},B_{2})$.

We will use this lemma for n=100. If for the boxes in A, the sum of the red balls is more than half of the total number of red balls, then we set $\lambda(A,B)=+red$. If it is more than half in B, then we set $\lambda(A,B)=-red$. We do similarly for blue and green (if they are not set yet to red). We also set $\lambda(A,B)=\pm (|A|+|B|)$ if $|A|+|B|\le 96$ (if they are not set to anything else yet). This way the cardinality of the range of lambda is 99, just as in the lemma. It is easy to verify that it satisfies the conditions of the lemma, thus there must be a set-pair for which we did not set any value. But in that case either A or B must be bigger than 96/2=48, thus at least 49. We can put the remaining boxes to the other part and we are done.

Note that this proof easily generalizes to more colors.

-

The idea in domotorp's answer doesn't work. Suppose we have seven boxes, as follows: (9,0,0),(0,0,9),(2,0,2),(2,0,2),(2,0,2),(2,0,2),(2,0,2). We load the first two boxes onto separate trucks, and now we are stuck.

EDITED: OK, I just realised that seven is not equal to 100. To fix this, just load 93 empty boxes (0,0,0) onto the trucks before we start, 46 on one truck and 47 on the other.

PS I posted this as a comment to domotorp's answer, but as it was the sixth comment, it fell off the bottom of the page. I know such comments are still viewable, but I also know that not everybody notices them.

-