Разделы 
Дополнительно
Задача по математике - 1914
2019-01-22 
В некоторой группе из 12 человек среди каждых 9 найдутся 5 попарно знакомых. Докажите, что в этой группе найдутся 6 попарно знакомых.
Решение:
Возьмем граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы.
Если в этом графе нет циклов нечетной длины, то его вершины можно разбить на две части, в каждой из которых вершины не будут соединены (см., например, лемму к задаче 1617), и поэтому найдутся 6 попарно знакомых.
Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пусть его длина равна:
а) 3. Тогда, если среди 9 человек, не входящих в этот цикл, есть два незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходить через эту вершину, иначе среди 4 человек не найдутся трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых.
б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся 3 знакомых, и среди этих 7 найдутся 6 знакомых.
в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если есть человек из цикла, знакомый со всеми этими 5, то все доказано. В противном случае, каждый из цикла не знаком с кем-то из оставшихся. Так как $7 > 5$, то найдется человек $A$ из оставшихся, не знакомый с двумя из цикла $B, C$. Из того, что мы взяли нечетный цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть «незнакомы через одного $D$» (см. рис.). Но тогда $D$ знаком со всеми из пяти оставшихся, потому что удаляя из цикла $D$ и заменяя на $A$, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы.
г) Цикла длины 9 не может быть по условию задачи.
д) Цикл длины 11. Тогда, как и выше при рассмотрении циклов длины 7, мы видим, что оставшийся человек может быть не знаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся.)
В некоторой группе из 12 человек среди каждых 9 найдутся 5 попарно знакомых. Докажите, что в этой группе найдутся 6 попарно знакомых.
Решение:
Возьмем граф на 12 вершинах, которые соответствуют людям, две его вершины соединены, если люди незнакомы.
Если в этом графе нет циклов нечетной длины, то его вершины можно разбить на две части, в каждой из которых вершины не будут соединены (см., например, лемму к задаче 1617), и поэтому найдутся 6 попарно знакомых.
Предположим теперь, что в графе есть циклы нечетной длины. Рассмотрим нечетный цикл минимальной длины. Пусть его длина равна:
а) 3. Тогда, если среди 9 человек, не входящих в этот цикл, есть два незнакомых, то среди оставшихся 7 человек из каждых 4 найдутся три знакомых. Таким образом, в подграфе на 7 вершинах каждые два ребра имеют общую вершину. Любое третье ребро обязано проходить через эту вершину, иначе среди 4 человек не найдутся трех знакомых. Поэтому все ребра имеют общую вершину, и, удаляя эту вершину, мы получаем 6 попарно знакомых.
б) 5. Тогда, как и выше, среди оставшихся 7 из каждых 4 найдутся 3 знакомых, и среди этих 7 найдутся 6 знакомых.
в) 7. Тогда среди 5 человек, не входящих в этот цикл, все попарно знакомы. Если есть человек из цикла, знакомый со всеми этими 5, то все доказано. В противном случае, каждый из цикла не знаком с кем-то из оставшихся. Так как $7 > 5$, то найдется человек $A$ из оставшихся, не знакомый с двумя из цикла $B, C$. Из того, что мы взяли нечетный цикл минимальной длины, следует, что эти два незнакомых из цикла должны быть «незнакомы через одного $D$» (см. рис.). Но тогда $D$ знаком со всеми из пяти оставшихся, потому что удаляя из цикла $D$ и заменяя на $A$, мы получаем снова цикл длины 7, а в дополнении к циклу длины 7 все попарно знакомы.
г) Цикла длины 9 не может быть по условию задачи.
д) Цикл длины 11. Тогда, как и выше при рассмотрении циклов длины 7, мы видим, что оставшийся человек может быть не знаком максимум с двумя из цикла. Но тогда в цикле легко найти 5 человек, знакомых между собой и с оставшимся. (Например, взяв идущих через одного по циклу и знакомых с оставшимся.)
