Карабас Барабас-мэр города

[Александр Кремень]

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

[Um_nik]

а) Показать скрытый текст

2001

б) Показать скрытый текст

1

Симпатично

[Александр Кремень]

А вот ответ. Карабас не мог занять последнее, 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.

[Smith]

странный Кремень отчасти...

зы: странно, что Умнику вообще удалось встрять между вопросом и ответом 

[☭-Изделие 20Д]

странный Кремень отчасти...

зы: странно, что Умнику вообще удалось встрять между вопросом и ответом 

Не  более странно чем то, что ответ в 6 утра "сегодня", а вопрос в 16 вечера 11 мая

[Амели]

а бывает 16 утра?