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

Проект МЦНМО
при участии
школы 57
Задача 103780
Темы:    [ Принцип Дирихле (прочее) ]
[ Перебор случаев ]
[ Разбиения на пары и группы; биекции ]
[ Неопределено ]
Сложность: 3
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Среди любых десяти из шестидесяти школьников найдётся три одноклассника. Обязательно ли среди всех шестидесяти школьников найдётся
  а) 15 одноклассников;
  б) 16 одноклассников?


Решение

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

  б) Не обязательно. Пример: по 15 школьников из четырёх классов.


Ответ

а) Обязательно; б) не обязательно.

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

олимпиада
Название Математический праздник
год
Год 1994
класс
1
Класс 6
задача
Номер 7

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

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