В классе 25 человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что есть ученик, у которого не менее 12 друзей.

Первое решение. Рассмотрим ученика А, число друзей которого меньше 12. Тогда число его не-друзей не меньше 13. Но в тройке из А и двух его не-друзей по условию есть хотя бы одна пара друзей, поэтому все не-друзья А попарно дружат между собой. Тогда у каждого не-друга А имеется не менее12 друзей.

Второе решение. Рассмотрим двух учеников А и В, которые не дружат между собой. Из оставшихся 23 человек каждый дружит хотя бы с одним из этих двоих учеников. Но если у каждого из этих двоих учеников меньше 12 друзей, то тогда суммарное число их дружественных связей не превышает 22: противоречие.