Условие
В гоночном турнире 12 этапов и n участников. После каждого этапа все
участники в зависимости от занятого места k получают баллы ak (числа ak натуральны, и a1 > a2 > ... > an). При каком наименьшем n устроитель турнира может выбрать числа a1, ..., an так, что после предпоследнего этапа при любом возможном распределении мест хотя бы двое участников имели шансы занять первое место.
Решение
Оценка. Предположим, что участников не больше 12.
Пусть при этом один из участников (назовём его A) выиграл все 11 этапов, а каждый из оставшихся хотя бы раз занял последнее место.
Тогда участник A после 12 этапов наберёт не меньше 11a1 + an очков, а каждый из оставшихся – не больше an + 10a2 + a1 очков, что меньше чем
11a1 + an.
Следовательно, только A может занять первое место. Поэтому для выполнения условия участников должно быть не менее 13.
Пример. Пусть участников 13, тогда устроителю достаточно выбрать числа a1 = 1011, a2 = 1010, ..., a12 = 1000, a13 = 1.
Рассмотрим участника, набравшего наибольшее количество очков после 11 этапов (назовём его A). Тогда среди 12 оставшихся найдётся по крайней мере один, который не занимал последнего места ни на одном из этапов (назовём его B). Заметим, что A набрал не более 1011·11 = 11121 очков, а B не менее 1000·11 = 11000 очков. То есть после 11 этапов A опережает B не более чем на 121 очко.
Очевидно, что после 11 этапа A имеет шансы занять первое место. Однако, если на 12 этапе A займёт последнее место, то B наберёт на 12 этапе хотя бы на 999 очков больше, чем A и обгонит его.
Ответ
При n = 13.
Источники и прецеденты использования
|
олимпиада |
Название |
Всероссийская олимпиада по математике |
год |
Год |
2006 |
Этап |
Вариант |
4 |
Класс |
Класс |
11 |
задача |
Номер |
06.4.11.3 |