Дружба в классе и теория графов: четыре взаимные связи — олимпиадная з
Задача
В классе 20 учеников, причём каждый дружит не менее, чем с 14 другими.
Можно ли утверждать, что найдутся четыре ученика, которые все дружат между собой?
Решение
Соберём весь класс в одной комнате. Рассмотрим некоторого человека А. Пусть теперь из комнаты выйдут все ученики, которые не дружат с А. По условию таких не более пяти. Поэтому в комнате осталось по крайней мере 15 учеников. Выберем из оставшихся в комнате ученика B, отличного от А. Пусть из комнаты выйдут все ученики, которые не дружат с B. После этого в комнате осталось не меньше 10 учеников. Наконец, выберем из оставшихся в комнате ученика C, отличного от А и от B. Пусть из комнаты выйдут все ученики, которые не дружат с C. После этого в комнате осталось не меньше пяти учеников. Эти пять учеников – это А, B, C и еще два ученика D и E, которые дружат с А, B, C. Искомая четвёрка учеников – это, например, А, B, C, D.
Ответ
Можно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь