Олимпиадная задача по принципу Дирихле и доказательству от противного для 7–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'. Противоречие, значит требуемый школьник найдётся.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь