MathDB

All 3 element subsets are coloured

Source: ItaMO 2011, P6

February 14, 2012

combinatorics proposedcombinatorics

Problem Statement

Let

X = \{1, 2, 3, 4, 5, 6, 7, 8\}

. We want to color, using

k

colors, all subsets of

3

elements of

X

in such a way that, two disjoint subsets have distinct colors. Prove that: (a)

4

colors are sufficient; (b)

3

colors are not sufficient.