Suppose we have a finite, 100-uniform system of sets such that any point is contained in at most 3 sets. Is it true that we can color the points such that every set contains 50 red and 50 blue points?

The question is by Thomas Rothvoss. A positive answer would solve the Three permutations problem of Beck, so a simple answer would be a counterexample...

  • 1
    $\begingroup$ I'm sorry, what is a "100-uniform system of sets"? Is that a system of sets, each of which contains exactly 100 elements? If so, why 100? Is the problem trivial for 98 (with each set containing 49 of each color)? Uninteresting for 102? It's certainly false for 2; consider the sets a-b, a-c, b-c, a 2-uniform system such that no point is in more than 3 (or even 2) sets, yet no way to color the points so each set has a red and a blue. $\endgroup$ – Gerry Myerson Jun 23 '10 at 13:05


Given sets $$ a_1,a_2,\dots,a_{99},b_1{\rm\ and\ }a_1,a_2,\dots,a_{99},b_2 $$ we see that $b_1$ and $b_2$ must be the same color, say, red. Then from $$ b_1,b_2,c_1,c_2,\dots,c_{98}{\rm\ and\ }d_1,d_2,c_1,c_2,\dots,c_{98} $$ we see $d_1$ and $d_2$ must both be red. Then from $$ d_1,d_2,e_1,e_2,\dots,e_{98}{\rm\ and\ }f_1,f_2,e_1,e_2,\dots,e_{98} $$ we see that $f_1$ and $f_2$ must both be red. Dot, dot, dot. You wind up with as many elements as you like, all of which must be red, and none of them are in more than two of the sets. Once you have more than 50 of them, you can put them in another set which will then have more than 50 red points.

Obviously, we can take 100 to be a variable in this problem and solution, provided we restrict its range to the positive even integers and understand 50 to be 100/2.

| cite | improve this answer | |
  • $\begingroup$ Wow, this was simpler than I thought, thanks! $\endgroup$ – domotorp Jun 24 '10 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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