Задание олимпиады: доказательство от противного про одноклассников
Задача
Среди любых десяти из шестидесяти ребят найдутся трое одноклассников. Докажите, что среди всех них найдутся 15 одноклассников.
Решение
Разделим ребят на группы одноклассников. Предположим, что в каждой группе не более 14 ребят. Тогда в четырёх самых больших по количеству группах не более 4·14 = 56 ребят.
Если в каждой из этих групп не менее двух человек, то можно взять по два школьника из этих четырёх групп и добавить двух школьников из оставшихся (их не менее 60 – 56 = 4). Среди этих 10 школьников нет трёх одноклассников, что противоречит условию.
Если хотя бы в одной из этих четырёх групп меньше двух человек, то имеется не менее 60 – 3·14 = 18 школьников, которые учатся в разных классах. Это также противоречит условию.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь