Областная олимпиада по математике, 2000 год, 11 класс

Множество $X$ состоит из шести элементов. Каждое из множеств $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, $A_6$ — трехэлементные подмножества множества $X$. Докажите, что можно раскрасить элементы множества $X$ в два цвета так, что не все элементы каждого из множеств $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, $A_6$ будут одинакового цвета.

Комментарий/решение

Каждое множество $A_{n}$ делит множество X на два равных по кол-ву членов подмножества. Мы также делим X два подмножества те красим только 3 элемента в один цвет. Видно что если $A_{n}$ и мы разделили X по разному то не все элементы множества $A_{n}$ будут одного цвета. Всего моржно разделить шесть элементов на две подгруппы где в каждой группе 3 элемента 10 способами т.к .

$\dfrac{6*5*4}{3*2*1*2}$=10

10>6 значит всегда есть как минимум 4 способа перекрасить элементы так чтобы они удволитворяли условию.