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

Условие:

В авиакомпании 17 пилотов. Известно, что среди любых трех пилотов хотя бы два летали в одном экипаже. Докажите, что есть пилот, который летал в одном экипаже не менее чем с восемью другими.

Решение:

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

Будем доказывать от противного. Пусть каждая вершина имеет степень не более семи. Возьмем любую вершину А, она не соединена хотя бы с девятью вершинами, назовем эти вершины хорошими. Среди хороших вершин возьмем любую вершину В. Она соединена максимум с семью вершинами, хороших вершин помимо В хотя бы восемь. Значит, найдется хотя бы одна хорошая вершина, не соединенная с В. Назовем ее С. Получается, мы нашли три попарно не соединенные вершины: А, В, С, противоречие.