В классе 25 учеников. Известно, что каких бы троих из них не выбрать, среди них обязательно найдется хотя бы одна пара друзей, а третий не будет дружить ни с одним из них. Докажите, что в классе есть ученик, у которого среди одноклассников более 11 друзей.
Ответ
Возьмем любую тройку учеников. В ней (по условию) есть два школьника, которые не дружат друг с другом. Каждый из оставшихся 23 одноклассников будет дружить хотя бы с одним из нашей двойки, поскольку в противном случае нашлась бы тройка, где нет друзей, что противоречит условию задачи.
Невозможно распределить 23 дружеские связи на две группы так, чтобы ни в одну из них не попало более 12 связей, поэтому один из двух школьников будет дружить как минимум с 12 одноклассниками.