В классе 25 учеников. Известно, что каких бы троих из них не выбрать

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

Ответ

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

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

Опубликовано: 22.09.2020 Обновлено: 22.09.2020
Поделись с друзьями

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

10 − 5 =