ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34913
Темы:    [ Доказательство от противного ]
[ Перебор случаев ]
Сложность: 2+
Классы: 7,8
В корзину
Прислать комментарий

Условие

Среди любых десяти из шестидесяти ребят найдутся трое одноклассников. Докажите, что среди всех них найдутся 15 одноклассников.


Подсказка

Предположите, что из каждого класса присутствует не более 14 ребят.


Решение

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

Источники и прецеденты использования

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .