Balls in boxes (partition) - MathOverflow

Balls in boxes (partition)

2010-01-18T08:33:19Z

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

Answer by domotorp for Balls in boxes (partition)

2010-01-18T23:05:51Z

Warning this answer is incorrect as pointed out in the answer by TonyK, sorry for the bad answer. Using a more complicated method, as in the paper mentioned in my comment, I can prove 51-49, I will post it in another answer. I leave this answer here for archival reasons.

I am not sure that I would call this pigeon-hole principle but one simple proof goes as follows. We build two subset of boxes simultaneously such that none of them will have a majority in any color. Notice that there can be only one box that would create a red majority when added to ANY of the subsets. Similarly for green and blue. Thus there are only three boxes that cannot be added to any subsets, so until we have four boxes left, we can proceed. When there are three boxes left, one of the subsets must have 49 elements, add the remaining three boxes to the other subset and we are done.

Answer by TonyK for Balls in boxes (partition)

2010-01-21T07:53:33Z

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.

Answer by domotorp for Balls in boxes (partition)

2010-01-21T10:25:17Z

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.