Внекоторой авиакомпании работает 27 пилотов известно что среди любых 3 пилотов хотя бы два летали в одном экипаже. доказать что есть пилот который летал в одном экипаже не менее чем с 13 другими
Посмотрим на эту задачу, как на граф: пилоты это вершины, если два пилота летали в одном экипаже, то между соответствующими вершинами проводим ребро. В условии задачи утверждается, что нет "пустых треугольников", то есть нет таких трех вершин, что между этими тремя вершинами нет ни одного ребра. Надо доказать, что найдется вершина степени хотя бы 13
Будем доказывать от противного. Пусть каждая вершина имеет степень не более семи. Возьмем любую вершину А, она не соединена хотя бы с девятью вершинами, назовем эти вершины хорошими. Среди хороших вершин возьмем любую вершину В. Она соединена максимум с семью вершинами, хороших вершин помимо В хотя бы восемь. Значит, найдется хотя бы одна хорошая вершина, не соединенная с В. Назовем ее С. Получается, мы нашли три попарно не соединенные вершины: А, В, С, противоречие.
27-26=1(п)
Посмотрим на эту задачу, как на граф: пилоты это вершины, если два пилота летали в одном экипаже, то между соответствующими вершинами проводим ребро. В условии задачи утверждается, что нет "пустых треугольников", то есть нет таких трех вершин, что между этими тремя вершинами нет ни одного ребра. Надо доказать, что найдется вершина степени хотя бы 13
Будем доказывать от противного. Пусть каждая вершина имеет степень не более семи. Возьмем любую вершину А, она не соединена хотя бы с девятью вершинами, назовем эти вершины хорошими. Среди хороших вершин возьмем любую вершину В. Она соединена максимум с семью вершинами, хороших вершин помимо В хотя бы восемь. Значит, найдется хотя бы одна хорошая вершина, не соединенная с В. Назовем ее С. Получается, мы нашли три попарно не соединенные вершины: А, В, С, противоречие.