Разделы 
Дополнительно
Задача по математике - 3222
2019-05-27 
a) Восемь школьников решали 8 задач. Оказалось, что каждую задачу решили 5 школьников. Докажите, что найдутся такие два школьника, что каждую задачу решил хотя бы один из них.
б) Если каждую задачу решили 4 ученика, то может оказаться, что таких двоих не найдется (приведите пример).
Решение:
Первый способ. a) Рассмотрим два случая.
1) Предположим, что найдется школьник, решивший хотя бы 6 задач. Докажем, что найдется школьник, решивший оставшиеся 2 задачи. Действительно, каждую из этих двух задач решили 5 школьников, а так как всего школьников 8<5+5, найдется школьник, решивший обе.
2) Предположим, что каждый школьник решил не более 5 задач. Докажем сначала, что каждый школьник решил ровно 5 задач. Действительно, так как в каждой из восьми задач было по 5 решений, то всего решений 40. Но если каждый из восьми школьников решил не более 5 задач, причем кто-то решил меньше 5 задач, то решений меньше 40.
Итак, пусть каждый школьник решил 5 задач. Пусть первый школьник решил задачи 1, 2, 3, 4, 5. Докажем, что найдется школьник решивший задачи 6, 7 и 8. В противном случае, каждый школьник решил не менее трех из первых пяти задач, тогда имеется не менее, чем 5+7×3=26 решений первых пяти задач. Но нам известно, что каждую из этих задач решили 5 школьников, значит, всего решений 25. Противоречие.
Второй способ. a) Последний шаг можно доказать иначе. Опять же, пусть первый школьник решил задачи 1, 2, 3, 4, 5. Каждую из задач 6, 7 и 8 не решили 3 школьника. Значит, каждую из них не решили 2 школьника, не считая первого. Значит, всего школьников, не решивших одну из задач 6, 7 или 8, не более семи (включая первого). Так как всего школьников 8, найдется школьник, решивший задачи 6, 7 и 8.
б) Эту задачу можно решить подбором (см. таблицу «успеваемости»):
a) Восемь школьников решали 8 задач. Оказалось, что каждую задачу решили 5 школьников. Докажите, что найдутся такие два школьника, что каждую задачу решил хотя бы один из них.
б) Если каждую задачу решили 4 ученика, то может оказаться, что таких двоих не найдется (приведите пример).
Решение:
Первый способ. a) Рассмотрим два случая.
1) Предположим, что найдется школьник, решивший хотя бы 6 задач. Докажем, что найдется школьник, решивший оставшиеся 2 задачи. Действительно, каждую из этих двух задач решили 5 школьников, а так как всего школьников 8<5+5, найдется школьник, решивший обе.
2) Предположим, что каждый школьник решил не более 5 задач. Докажем сначала, что каждый школьник решил ровно 5 задач. Действительно, так как в каждой из восьми задач было по 5 решений, то всего решений 40. Но если каждый из восьми школьников решил не более 5 задач, причем кто-то решил меньше 5 задач, то решений меньше 40.
Итак, пусть каждый школьник решил 5 задач. Пусть первый школьник решил задачи 1, 2, 3, 4, 5. Докажем, что найдется школьник решивший задачи 6, 7 и 8. В противном случае, каждый школьник решил не менее трех из первых пяти задач, тогда имеется не менее, чем 5+7×3=26 решений первых пяти задач. Но нам известно, что каждую из этих задач решили 5 школьников, значит, всего решений 25. Противоречие.
Второй способ. a) Последний шаг можно доказать иначе. Опять же, пусть первый школьник решил задачи 1, 2, 3, 4, 5. Каждую из задач 6, 7 и 8 не решили 3 школьника. Значит, каждую из них не решили 2 школьника, не считая первого. Значит, всего школьников, не решивших одну из задач 6, 7 или 8, не более семи (включая первого). Так как всего школьников 8, найдется школьник, решивший задачи 6, 7 и 8.
б) Эту задачу можно решить подбором (см. таблицу «успеваемости»):
