В классе 24 ученика, у каждого ровно 3 друга среди одноклассников. Однажды на каникулах 6 учеников подписались на канал по олимпиадной математике. После этого ученики стали общаться между собой. Когда ученик узнаёт, что хотя бы двое из его друзей уже подписались на канал, он также подписывается на этот канал. Могло ли в итоге случиться, что весь класс подписался на канал?
1 Ответ
Решение:
Предположим противное, что весь класс подписался на канал. Рассмотрим количество дружб среди подписчиков.
Каждый новый подписчик увеличивает его хотя бы на 2. С другой стороны, в итоге это количество составляет 24 — 3/2 = 36, а всего добавилось 24 — 6 = 18 подписчиков, а значит каждый добавлял ровно по 2 дружбы. Но последний подписчик добавил 3 дружбы — противоречие.
Ответ: Нет