Задача
В классе 25 человек. Известно, что среди любых трех из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.
Решение
Рассмотрим двоих учеников класса, которые не дружат между собой. (Если таких нет, то все ученики класса дружат между собой, значит, у каждого ученика имеется 24 друга, и задача решена.) Пусть этими двумя будут Вася и Петя. Тогда из оставшихся 23 учеников каждый дружит либо с Васей, либо с Петей. Действительно, если бы кто-то (скажем, Коля) не дружил бы ни с Васей, ни с Петей, то мы имели бы троих учеников, среди которых не было бы друзей. Теперь если предположить, что и Вася, и Петя имеют не более 11 друзей, то всего в классе, кроме этих двоих было бы не больше 22 человек (см. статью"Принцип Дирихле".). Полученное противоречие показывает, что один из школьников имеет не менее 12 друзей.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь