Question

В олимпиаде 9 участников, за решёную задачу- 2 балла, за нерешёную- -1 балл. Всего 10 задач. Докажите, что по крайней мере у двух участников количество баллов одинаковое.

Answer 1

Ну например:
два ученика решили все правильно
или
два ученика решили все неправильно
или же
решили одинаковое количество задач.

Answer 2

Для решения данной задачи, воспользуемся принципом Дирихле (Теорема о кратности в олимпиадных задачах). Принцип Дирихле утверждает, что если n+1 объектов распределить по n ящикам, то хотя бы в одном из ящиков окажется два или более объекта.

В данной задаче у нас 9 участников и 10 задач. Предположим, что каждому участнику присваиваются различные баллы, тогда общее количество баллов у всех участников будет составлять:

2 балла * 9 участников = 18 баллов.

Также у нас есть 10 задач, и каждая задача может быть либо решена (2 балла), либо нерешена (-1 балл). Максимальное количество баллов, которое можно набрать за все задачи:

2 балла * 10 задач = 20 баллов.

Теперь рассмотрим два случая:

1. Если у всех участников количество баллов различно, то минимальное количество баллов, которое можно набрать за все задачи:

-1 балл * 10 задач = -10 баллов.

2. Если у каких-то двух участников количество баллов одинаковое, то сумма баллов всех остальных участников будет на 2 балла больше (поскольку за каждую задачу, решенную этими двумя участниками, будет начислено по 2 балла, и за каждую нерешенную задачу -1 балл):

2 балла * 2 задачи = 4 балла.

Теперь общее количество баллов у всех остальных участников:

18 баллов - 4 балла = 14 баллов.

Таким образом, если у двух участников количество баллов одинаковое, то общее количество баллов у остальных будет равно 14 баллов. Но мы знаем, что максимальное возможное количество баллов за все задачи - 20 баллов. Это значит, что второй случай невозможен, и у всех участников количество баллов различно.

Поскольку мы рассмотрели все возможные случаи, и ни один из них не приводит к ситуации, когда у двух участников количество баллов одинаковое, то это противоречит принципу Дирихле.

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