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

Проект МЦНМО
при участии
школы 57
Задача 107802
Темы:    [ Числовые таблицы и их свойства ]
[ Принцип Дирихле (прочее) ]
[ Сочетания и размещения ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

a) Восемь школьников решали восемь задач. Оказалось, что каждую задачу решили пять школьников. Докажите, что найдутся такие два школьника, что каждую задачу решил хотя бы один из них.
б) Если каждую задачу решили четыре ученика, то может оказаться, что таких двоих не найдётся.


Решение

  a) Будем тройку из двух учеников и задачи, которую они оба не решили, называть отмеченной. Поскольку каждую задачу не решили трое учеников, каждой задаче соответствуют три отмеченные тройки. Значит, всего отмечено 24 тройки. С другой стороны, имеется  7·8 : 2 = 28  пар учеников. Следовательно, есть пара учеников, не входящая ни в одну в отмеченную тройку. Это и значит, что они решили все задачи.

  б) Пример:

Замечания

1. Баллы: 3 + 3.

2. Аналогичные рассуждения позволяют доказать, что если среди n школьников каждую из p задач решило не менее  n – m  человек и  n(n – 1) > pm(m – 1),  то некоторые двое решили (вместе) все задачи, а если  n(n – 1)...(n – k + 1) > pm(m – 1)...(m – k + 1)  для некоторого  k > 1,  то найдутся k школьников, которые вместе решили все задачи.

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

журнал
Название "Квант"
год
Год 1996
выпуск
Номер 3
Задача
Номер М1547
олимпиада
Название Московская математическая олимпиада
год
Номер 59
Год 1996
вариант
Класс 8
задача
Номер 6
олимпиада
Название Турнир городов
Турнир
Дата 1995/1996
Номер 17
вариант
Вариант весенний тур, основной вариант, 8-9 класс
Задача
Номер 5

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

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