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