Question

В класс 30 человек. В диктанте Витя Малеев сделал 12 ошибок, а каждый из остальных - не больше.Докажите, что по крайней мере трое учеников сделали одинаковое количество (быть может, и ноль) ошибок.

Answer 1

Так как количество ошибок не может быть отрицательным, то у нас есть несколько случаев количества ошибок:
0 1 2 3 4 5 6 7 8 9 10 11 12 - всего 13 случаев
Если каждый сделал разное количество ошибок, то это 13 человек
Если каждые два ученика сделали одинаковые ошибки, то это 26 человек.
Но 26 человек - это не весь класс, так как остается ешё 4 человека, значит обязательно найдётся трое учеников с одинаковыми ошибками.

Answer 2

Давайте докажем данное утверждение по принципу Дирихле, который утверждает, что если n+1 объектов распределены в n ящиках, то хотя бы в одном ящике будет более одного объекта.

В данном случае, у нас есть 30 человек, включая Витю Малеева. Пусть Витя сделал 12 ошибок, и остальные (30 - 1 = 29 человек) сделали не больше 12 ошибок каждый.

Теперь рассмотрим возможное количество ошибок, которое могли сделать остальные ученики:

0 ошибок: Мы не можем иметь более 29 человек без ошибок, потому что тогда Витя сделал бы не меньше 13 ошибок, что противоречит условию.

1 ошибка: Также не может быть больше 29 человек с одной ошибкой, потому что в этом случае у Вити было бы не менее 14 ошибок.

2 ошибки: Не может быть более 29 человек с двумя ошибками, иначе Витя имел бы не менее 15 ошибок.

3 ошибки: При 29 человеках с тремя ошибками Витя имел бы не менее 16 ошибок.

4 ошибки: При 29 человеках с четырьмя ошибками Витя имел бы не менее 17 ошибок.

...

12 ошибок: Все 29 человек могут сделать по 12 ошибок каждый, тогда у Вити также будет 12 ошибок.

Таким образом, мы видим, что невозможно иметь 30 человек с различным числом ошибок от 0 до 12, потому что для каждого числа ошибок у остальных учеников будет свой верхний предел, противоречащий условию.

Следовательно, хотя бы трое учеников сделали одинаковое количество ошибок, возможно и ноль. Это доказывает утверждение.