|
|
 |
Условие
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 |
