Question

В контрольной работе по математике Вовочка сделал 10 ошибок, а остальные ребята – меньше. Докажи, что по крайней мере четверо учеников сделали одинаковое число ошибок (быть может ноль), если известно, что в классе 33 ученика.

Answer 1

Так как все кроме вовочки сделали меньше 10 ошибок, то возможны 10 различных кол-ва ошибок(от 0 до 9). Тогда нам нужно распределить 32 учеников в 10 групп так чтобы ни в одной группе не было больше трех учеников. Но по правилу Дирихле это невозможно.

ЧТД

Answer 2

Для доказательства этого утверждения воспользуемся принципом Дирихле (или принципом ящиков и шаров). Этот принцип гласит, что если n объектов распределить по m контейнерам (ящикам), и при этом n > m, то как минимум в одном из контейнеров будет по крайней мере по одному объекту.

В данном случае, давайте рассмотрим 34 учеников (Вовочка и еще 33 ребенка) и число ошибок, которое каждый из них сделал на контрольной работе.

Если Вовочка сделал 10 ошибок, то остальные 33 - 10 = 23 ребенка сделали меньше ошибок, чем Вовочка.

Рассмотрим всех этих 23 ребенка как контейнеры и число ошибок, которое каждый из них сделал, как объекты. Теперь мы имеем 23 контейнера и 23 различных числа ошибок, меньших, чем 10.

Согласно принципу Дирихле, если мы разместим 23 объекта в 23 контейнерах, как минимум в одном из контейнеров будет по одному объекту. Это означает, что по крайней мере два ученика сделали одинаковое количество ошибок.

Один из этих двух учеников может быть Вовочка (если какой-то другой ребенок сделал 10 ошибок), но это также означает, что еще как минимум один ученик (из оставшихся 32) сделал то же самое количество ошибок, что и Вовочка.

Итак, у нас есть по крайней мере два ученика, сделавших одинаковое количество ошибок, и один из них может быть Вовочкой. Таким образом, по крайней мере четверо учеников сделали одинаковое количество ошибок.