0
$\begingroup$

Is the following statement true or false?

For every $n > 0$, such $N$ exists, that no matter how we "color" all of the subsets of the set with $N$ elements(we only use two colors), No matter how we color the subsets of the N-elemented set with two colors, we can always find an n-elemented subset, whose subsets have the same colour, sorry I wrote it wrong.

I am just confused how should I start this task, my guess is false, but I can't really begin anything. Any help appreciated :)

$\endgroup$
4
  • $\begingroup$ Just to make it clear. You color every subset - all $2^N$ of them. Then you want to find $n$ subsets that all have the same color ? Or $n$ individual elements that all have the same color ? If so, what's the point of coloring subsets ? $\endgroup$
    – Manuel Lafond
    Commented Mar 30, 2015 at 17:23
  • $\begingroup$ No matter how we color the subsets of the N-elemented set with two colors, we can always find an n-elemented subset, whose subsets have the same colour, sorry I wrote it wrong. $\endgroup$
    – Atvin
    Commented Mar 30, 2015 at 17:30
  • $\begingroup$ Ok. So you need to find a set $X$ of $n$ elements, such that all $2^n$ subsets of $X$ have the same color. In particular, all one-element subsets of $X$ have the same color - so in fact all elements of $X$ must be the same color. Does that sound right ? $\endgroup$
    – Manuel Lafond
    Commented Mar 30, 2015 at 18:25
  • $\begingroup$ Yes that is correct $\endgroup$
    – Atvin
    Commented Mar 30, 2015 at 18:30

1 Answer 1

Reset to default
2
$\begingroup$

The statement is false for all $n > 0$ because one can color the subsets according to the parity of their sizes, that is, if the size of the subset is odd, then color it blue, otherwise red.

$\endgroup$
2
  • $\begingroup$ Can you give me an example for $n=5$ please? :) $\endgroup$
    – Atvin
    Commented Mar 30, 2015 at 17:58
  • $\begingroup$ Color all $5$ singleton sets, all ${5\choose 3}$ $3$-subsets and $1$ $5$-subset blue and all the rest of the subsets red. $\endgroup$
    – Zilin J.
    Commented Mar 30, 2015 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .