Отзывы пользователей

гдз

Олимпиадная задача по математике из коллекции задач Турнира Ломоносова на темы: Турниры и турнирные таблицы, Подсчет двумя способами.

Условие

В соревнованиях участвуют 10 фигуристов. Соревнования судят трое судей следующим способом: каждый судья по-своему распределяет между фигуристами места (с первого по десятое), после чего победителем считается фигурист с наименьшей суммой мест. Какое наибольшее значение может принимать эта сумма у победителя (победитель единственный)?


Решение

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

Докажем сначала первое утверждение. Для этого посчитаем двумя способами сумму мест, присужденных всеми судьями всем участникам соревнований. С одной стороны, поскольку каждый из трех судей распределил набор мест с первого по десятое, эта сумма равна 3 • (1 + 2 + ... + 10) = 165. С другой стороны, ее же мы должны получить, сложив сумму мест, полученных каждым фигуристом. Если предположить, что победитель получил сумму не меньше 16, тогда все остальные получили сумму мест не меньше 17, и рассматриваемая общая сумма не меньше, чем 16 + 9 • 17 = 169. Полученное противоречие доказывает, что сумма мест победителя не больше 15.

Для доказательства второго утверждения достаточно привести пример судейства, при котором сумма мест победителя равна 15. Такой пример приведен ниже в виде таблицы:

 
Поделиться: