2
$\begingroup$

A positive integer $n > 2$ is chosen, and each of the numbers $1, 2, \dots, n$ is colored red or blue. Show that it is possible to color each subset of $N=\{1,2,\ldots,n\}$ either red or blue so that each red number lies in more red subsets than blue subsets, and each blue number lies in more blue subsets than red subsets.

Attempt of solving

Say element of $N$ is bad, if it lies in at most sets of its color as of the sets pf oposite color.

Randomly color each set $N$. As we have $2^n$ set, we have $2^{2^n}$ different colorings. Take an arbitrary $m$ from $N$, say it is blue and claculate probabilty it is bad. We have $2^{n-1}$ sets with $m$, so we have at least $2^{n-2}$ red set. So some coloring is bad for $m$ if we have

  • $0$ blue and $2^{n-1}$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 0} \cdot 2^{2^{n-1}}$$

  • $1$ blue and $2^{n-1}-1$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 1} \cdot 2^{2^{n-1}}$$

  • $2$ blue and $2^{n-1}-2$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 2} \cdot 2^{2^{n-1}}$$

    $$\vdots $$

  • $2^{n-2}$ blue and $2^{n-2}$ red sets with $m$, so the number of colorings in this case is $${2^{n-1}\choose 2^{n-2}} \cdot 2^{2^{n-1}}$$

So the number of all bad colorings for $m$ is $$ \sum _{i=0}^{2^{n-2}}{2^{n-1}\choose i} \cdot 2^{2^{n-1}} = {1\over 2} \Big(2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \Big)\cdot 2^{2^{n-1}}$$ so the probability $m$ is bad is: $$P = {2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \over 2\cdot 2^{2^{n-1}}}$$ So the probability that at least one elements is bad in bounded by : $$n\cdot {2^{2^{n-1}} + {2^{n-1}\choose 2^{n-2}} \over 2\cdot 2^{2^{n-1}}}$$ which is clearly more than 1 so the union bound does not apply here.

I was wondering if Lovasz local lemma can be aplied here? Any help?

$\endgroup$
  • $\begingroup$ I'd be tempted to try induction. Assuming I've solved the problem for the same colors on the first $n-1$ integers. Now we add in $n$ colored, say, blue. All we need to do is to color one more than half the subsets containing $n$ blue. Can I not do this evenly for all the other elements? The subset consisting of $n$ alone will be blue, so I just need to be $50-50$ for all the others. $\endgroup$ – lulu Aug 28 at 12:35
  • $\begingroup$ The problem of course is that there is an odd number of subsets containing $n$, and excluding $(n)$. So we can't get $50-50$ exactly. If, in my prior coloring, every number was only ahead by one in the count, this would cause a problem. So the inductive statement needs to ensure that at least one element is ahead by at least two. Happily, the construction ensures that $n$ will end up at least two ahead so there is still hope. $\endgroup$ – lulu Aug 28 at 12:46
  • $\begingroup$ What is a red subset? Is it a subset where at least half of the elements are colored red? $\endgroup$ – Mike Aug 28 at 19:16
  • 1
    $\begingroup$ No, arbitrary subset can be red, there is no rule to color a subset. Coloring of elements and set are not connected. @Mike $\endgroup$ – Aqua Aug 28 at 19:20
4
$\begingroup$

You shouldn't expect a naive application of the local lemma to work, because:

  • In a uniformly random coloring, the probability that a number is contained in more red sets than blue sets is a constant: approximately $\frac12$.
  • However, the number of dependencies is not constant: it grows exponentially with $n$.

In fact, the high probability of failure is an obstacle with any probabilistic coloring method.


A deterministic coloring works. Suppose $R$ is the set of red elements and $B$ is the set of blue elements. Begin by coloring a set $S$ red if $|R \cap S| > \frac12|R|$, and blue otherwise. The quality of the result depends on the parity of $r := |R|$.

  • When $r$ is odd, red elements are ahead by $\binom{r-1}{(r-1)/2}2^{n-r}$ of the sets containing them, and blue elements have an equal number of red and blue sets that contain them.
  • When $r$ is even, red elements have an equal number of red and blue sets that contain them, and blue elements are ahead by $\binom{r}{r/2}2^{n-r}$ of the sets containing them.

Ties are bad, so in either case, we'll have to fix the coloring slightly. When $r$ is odd (and $r \ne n$, so blue elements exist), boost blue elements by $1$ by coloring the set $\{1, 2, \dots, n\}$ blue instead of red.

When $r$ is even, or if the previous step brought the red elements down to an even split (which happens for instance if $r=1$ and $n=2$), boost red elements by $1$ by coloring each singleton set $\{x\}$ for $x \in R$ red, instead of blue. This is a free action: it doesn't hurt blue elements at all, but gives red elements the boost they needed.

$\endgroup$
  • $\begingroup$ When $r$ is odd, do you mean to color $\{1, 2, \dots, n-1\}$ blue or to color $\{1, 2, \dots, n\}$ blue? What if $n$ is blue? $\endgroup$ – saulspatz Aug 28 at 18:47
  • $\begingroup$ @saulspatz I mean $\{1,2, \dots,n\}$. I don't know why I wrote $n-1$. $\endgroup$ – Misha Lavrov Aug 28 at 19:00

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.