|
|
 |
Условие
В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.
Решение
Возьмём граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы.
Если в этом графе нет циклов нечётной длины, то его вершины можно разбить на две части, в каждой из которых вершины не будут соединены (см. лемму к задаче 110038, и поэтому найдутся шесть попарно знакомых.
Предположим, что в графе есть циклы нечётной длины. Рассмотрим нечётный
цикл минимальной длины. Пусть его длина равна n. Рассмотрим все возможные случаи.
1) n = 3. Тогда, если среди девяти человек, не входящих в этот цикл, есть двое незнакомых, то среди оставшихся семи человек из каждых четырёх найдутся трое знакомых (добавим к этим четырём двух незнакомых из девятки и трёх незнакомых из цикла). Отсюда следует, что в подграфе на семи вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходить через эту вершину, иначе среди четырёх человек не найдутся трое знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем шесть попарно знакомых.
2) n = 5. Тогда, как и выше, среди оставшихся семи
из каждых четырёх найдутся трое знакомых, и среди этих семи найдутся шесть знакомых.
3) n = 7. Тогда среди пяти человек, не входящих в этот цикл, все попарно знакомы (если есть двое незнакомых, то, добавив к ним семерых из цикла, получим противоречие с условием). Если есть человек из цикла, знакомый со всеми этими пятью, то все доказано. В противном случае каждый из цикла не знаком с кем-то из оставшихся. Так как 7 > 5, то найдётся человек A из оставшихся, не знакомый с двумя из цикла B, C.
Из того, что мы взяли нечётный цикл минимальной длины, следует, что B и C должны быть "незнакомы через одного". Пусть это D, см. рис.
4) Цикла длины 9 нет по условию задачи.
5) n = 11. Тогда, как и выше при рассмотрении циклов длины 7, мы видим, что оставшийся человек может быть не знаком максимум с двумя из цикла. Но тогда в цикле легко найти пять человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся.)
