Решение задачи 155

Условие:

В компании из 9 девушек некоторые поссорились. Оказалось, что нет такой тройки девушек, в которой каждая девушка поссорилась с каждой. Докажите, что найдутся 4 девушки, среди которых ни одна пара еще не ссорилась.

Решение:

Поскольку это задача на графы, то будет полезно считать, что каждая девушка - вершина графа. Ребра графа покрасим в 2 цвета: между двумя девушками ребро красного цвета, если они в ссоре, иначе, между ними ребро зеленого цвета. Тогда наша задача состоит в том, чтобы показать, что найдется четырёхугольник с диагоналями полностью зеленого цвета (и диагонали и стороны четырёхугольника зеленого цвета), при условии, что нет красных треугольников.

Как уже говорилось в подсказке, рассмотрим 2 случая:

1) Нашлась вершина, из которой выходит по крайней мере 4 красных ребра:

В таком случае никакая пара из этих четырех вершин не может быть окрашена в красный цвет (сразу же образуется красный треугольник из этих двух вершин и "звёздочки"). Поэтому эти 4 вершины обязаны быть попарно соединены зелеными рёбрами:

То есть полный зеленый четырёхугольник нашёлся!

2) Из каждой вершины выходит не более трех красных рёбер.

Покажем, что найдется вершина из которой выходит не менее 6 зелёных рёбер. Последнее утверждение равносильно тому, что найдется вершина, из которой выходит не более двух красных рёбер. Это правда, поскольку, если предположить, что из всех вершин выходит ровно по 3 красных ребра, то общее число красных ребер: 3*9/2 - не является целым числом. Рассмотрим вершину "звёздочка", из которой выходит не менее шести зелёных ребер. Обратим внимание отдельно на граф на этих 6 вершинах. Далее просто пользуемся задачей 154. Она гласит нам, что в любом полном графе на 6 вершинах с двухцветными рёбрами есть одноцветный треугольник. Поскольку в этом графе по условию не может быть красного треугольника, то обязательно найдётся зелёный треугольник. Этот треугольник вместе с зелёными ребрами из "звёздочки", образует полный зеленый четырёхугольник:

Мы показали, что в таком графе обязательно найдётся зеленый четырёхугольник!