ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105136
Темы:    [ Математическая логика (прочее) ]
[ Суммы числовых последовательностей и ряды разностей ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если это кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся.
На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре k-е место по числу голосов. Определите наибольшее возможное значение k, если Остап Бендер был избран
а) в 1002-м туре;
б) в 1001-м туре.

Решение

а) Остап не мог занять последнее, 2002-е место в первом туре, поскольку иначе он сразу же выбыл бы из числа кандидатов. Поэтому k<2001.

Пусть все кандидаты в первом туре набрали почти поровну, Остап занял предпоследнее место и в каждом следующем туре получал все голоса выбывшего кандидата. Тогда Остап победит в тот момент, когда количество выбывших кандидатов достигнет половины. Это случится как раз в 1002-м туре.

Выполним точный подсчёт в случае, когда кандидаты в первом туре набрали 106, 106+1, ..., 106+2001 голос. Тогда в 1001-м туре у Остапа ещё меньше половины голосов, а именно: голоса всех кандидатов, занявших последние 1001 место в первом туре. Однако в 1002-м туре у него уже более половины всех голосов. Действительно, у Остапа
106+(106+1)+...+(106+1001)=
=1002*106+(1001*1002)/2=
=1002*106+1001*501=1002501501
голосов, а всего избирателей
106+(106+1)+...+(106+2001)=
=2002*106+(2001*2002)/2=
=2002*106+2001*1001=2004003001.
Нетрудно проверить, что это меньше удвоенного числа голосов Остапа.

б) Предположим, что k>1. Кандидата, занявшего первое место в первом туре, назовём фаворитом. Тех, кто выбыл в первой тысяче туров, назовём аутсайдерами, а всех остальных кандидатов, кроме Остапа, - лидерами. Поскольку число аутсайдеров 1000, а лидеров 1001, то один из лидеров не получал голосов аутсайдеров. В первом туре (и позже) он имел больше голосов, чем любой аутсайдер (так как в конечном счёте выбыл аутсайдер, а не этот лидер). Поэтому фаворит, набравший в первом туре наибольшее число голосов, не входит в число аутсайдеров.

Максимальное число голосов, которое мог собрать Остап к 1001-му туру, - это все голоса аутсайдеров на момент вылета каждого из них и голоса первоначальных избирателей Остапа. Любой из лидеров в любом из первой тысячи туров (а тем более в 1001-м) имеет больше голосов, чем аутсайдер этого тура. Фаворит заведомо имеет больше, чем имел Остап в первом туре. Поэтому лидеры в сумме имеют в 1001-м туре больше голосов, чем Остап, и он не может стать победителем.

Дополнительный вопрос (в условие предлагавшейся на олимпиаде задачи не входит): изменится ли ответ в задаче, если голоса выбывшего кандидата произвольно делятся между оставшимися?

Ответ

k=2001;
б) k=1.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 65
Год 2002
вариант
Класс 10
задача
Номер 5
олимпиада
Название Московская математическая олимпиада
год
Номер 65
Год 2002
вариант
Класс 11
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .