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, Bsubset [n], Acap B=emptyset, Acup Bneemptyset$ we have a $lambda(A,B)inpm[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.
No comments:
Post a Comment