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

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

Условие

На олимпиаде m>1 школьников решали n>1 задач. Все школьники решили разное количество задач. Все задачи решены разным количеством школьников. Докажите, что один из школьников решил ровно одну задачу.

Решение

Если нашёлся школьник, не решивший ни одной задачи, то не будем его рассматривать. Затем, если есть задача, не решённая ни одним из школьников, то не будем её рассматривать. По-прежнему все школьники решили разное количество задач, все задачи решены разным количеством школьников. Пусть осталось m' школьников и n' задач. Тогда m'$ \ge$1, n'$ \ge$1. Если каждый из m' школьников решил от 2 до n' задач и все решили разное количество задач, то m'$ \le$n' - 1. Так как каждая из n' задач решена от 1 до m' школьниками, и все задачи решены разным количеством школьников, то n'$ \le$m'. Противоречие, значит требуемый школьник найдётся.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 62
Год 2006
вариант
Класс 9
задача
Номер 2

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

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