Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
6  
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
12  
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
2  
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

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Thanks very much, domotorp! I am not sure why you were voted down. Seems to me your solution is correct. Just to make sure, "majority in any color" here means more than half of the total number of balls of one particular color. cheers. –  kiasncp Jan 19 '10 at 5:14
    
Yes, it means that. I would be interested to know whether this problem was motivated by or is connected to some research question, if you know. Also, if you liked my solution, here is a paper of mine that uses a similar idea but a much stronger lemma to prove another partition result. cs.elte.hu/~dom/cikkek/necklace.pdf –  domotorp Jan 19 '10 at 5:56
    
Thanks again for everyone who replied! @domotorp, I was told the problem was from one of the Russian Olympiad in the late nineteenth - didn't succeed to track it down though. So I'm not sure if this is related to any research idea. –  kiasncp Jan 21 '10 at 0:30
    
Previously I had a suggestion here to interpret the subsets as two trucks onto which the boxes could be loaded. (But the solution listed here as of now turned out to be incorrect...) –  Bjorn Poonen Jan 25 '10 at 5:56

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.