Соответствия, сравнения, количества

Проинтерпретируем задачу следующим образом: дано несколько синих и красных множеств, в каждом ровно элементов. Известно, что любое синее и любое красное множество имеют непустое пересечение. Надо доказать, что все элементы множеств можно покрасить в три цвета (назовём эти цвета и ) так, чтобы в каждом множестве были элементы всех трёх цветов.

Причешем задачу. По-очереди выкинем все множества, которые совпадают с какими-то другими. Но сделаем это так, чтобы после всех выкидываний или осталось одно множество, или остались множества двух цветов. Понятно, что если решить задачу для новой системы множеств, то и для исходной она тоже будет решена.

Случай Остались и синие, и красные множества. Выберем такие два множества — синее и красное — пересечение которых содержит больше всего элементов; пусть элементов. Отметим, что

) Если то раскрасим в цвет два элемента из и в цвет все остальные элементы не из в цвет Эта раскраска подходит. Действительно, любое множество пересекается или с или с то есть его элементы не могут быть только -го цвета. Но и только -го или -го цвета они быть не могут, так как -го цвета ровно элементов, а -го цвета – элемента.

) Если то раскрасим в цвет по одному элементу из и тоже в цвет а остальные элементы из и в цвет все остальные элементы не из в цвет Эта раскраска подходит. Действительно, любое множество пересекается или с или с то есть его элементы не могут быть только -го цвета. Но и только -го или второго цвета они быть не могут. Докажем это. Почему все элементы из не могут быть цвета Пусть могут. Есть всего элемента -го цвета, поэтому множество из элементов -го цвета при вообще существовать не может, а при оно пересекается с и с по элементам, что противоречит выбору и как пары разноцветных множеств с максимальным пересечением. Почему все элементы из не могут быть цвета Пусть могут. Пусть для определенности – красное множество. Тогда и пересекаются не более чем по элементам цвета (из выбора пары и как пары разноцветных множеств с максимальным пересечением). Значит, должно пересекаться с не менее чем по элементам цвета но в всего элемент цвета

Случай Осталось только одно множество. Как угодно покрасим его элементы в два цвета.