Задача 105204

Темы:    [ Принцип Дирихле (прочее) ] [ Доказательство от противного ]

Сложность: 3 Классы: 7,8,9

Условие

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

Решение

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

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

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