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](http://mathlinks.ro/Forum/viewtopic.php?t=32161/).


Also domotorp has found the [origin](http://turgor.ru/lktg/2005/4/index.htm) of the problem (which was sort of buried in the comments).



Balls in boxes (partition)
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](http://www.cs.elte.hu/~dom/cikkek/necklace.pdf) 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.


