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

Условие:

Среди 12 футбольных команд проводится турнир в один круг. Уже сыграно 23 матча. Докажите, что найдется тройка команд, в которой еще никто ни с кем не играл.

Решение:

Посмотрим на задачу, как на граф: команды — вершины, если две команды играли, то между ними проведем ребро. Переформулировка задачи: дан граф на 12 вершинах, в котором проведены 23 ребера. Доказать, что найдется "пустой" треугольник.

В этом графе могло быть максимум 12*11/2 = 66 ребер, но их всего 23, значит не проведены 43 ребера (назовем их "пустыми"). Пусть из каждой вершины выходит не более семи пустых ребер, значит всего в графе максимум 12*7/2 = 42 пустых ребра, что не так по условию. Значит, найдется вершина А, из которой выходит хотя бы 8 пустых ребер. Через М обозначим множество вершин, которые соединены пустым ребром с А (в М хотя бы восемь вершин). Пусть между любыми двумя вершинами из М проведено ребро. Этих ребер хотя бы 8*7/2 = 28. Значит, в исходном графе больше 23 ребер, противоречие. Получается, найдутся две вершины из М (назовем их В и С), между которыми нет ребра. Вершины А, В, С образуют пустой треугольник.