Олимпиадная задача про выборы мэра в Удоеве и Остапа Бендера: последовательности и логика
Задача
В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если это кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся. На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре k-е место по числу голосов. Определите наибольшее возможное значение k, если Остап Бендер был избран а) в 1002-м туре; б) в 1001-м туре.
Решение
а) Остап не мог занять последнее, 2002-е место в первом туре, поскольку иначе он сразу же выбыл бы из числа кандидатов. Поэтомуk<2001.Пусть все кандидаты в первом туре набрали почти поровну, Остап занял предпоследнее место и в каждом следующем туре получал все голоса выбывшего кандидата. Тогда Остап победит в тот момент, когда количество выбывших кандидатов достигнет половины. Это случится как раз в 1002-м туре. Выполним точный подсчёт в случае, когда кандидаты в первом туре набрали 106, 106+1, ..., 106+2001 голос. Тогда в 1001-м туре у Остапа ещё меньше половины голосов, а именно: голоса всех кандидатов, занявших последние 1001 место в первом туре. Однако в 1002-м туре у него уже более половины всех голосов. Действительно, у Остапа
106+(106+1)+...+(106+1001)= =1002106+(10011002)/2= =1002106+1001501=1002501501
голосов, а всего избирателей
106+(106+1)+...+(106+2001)= =2002106+(20012002)/2= =2002106+20011001=2004003001.
Нетрудно проверить, что это меньше удвоенного числа голосов Остапа. б) Предположим, что k>1. Кандидата, занявшего первое место в первом туре, назовём фаворитом. Тех, кто выбыл в первой тысяче туров, назовём аутсайдерами, а всех остальных кандидатов, кроме Остапа, - лидерами. Поскольку число аутсайдеров 1000, а лидеров 1001, то один из лидеров не получал голосов аутсайдеров. В первом туре (и позже) он имел больше голосов, чем любой аутсайдер (так как в конечном счёте выбыл аутсайдер, а не этот лидер). Поэтому фаворит, набравший в первом туре наибольшее число голосов, не входит в число аутсайдеров.
Максимальное число голосов, которое мог собрать Остап к 1001-му туру, - это все голоса аутсайдеров на момент вылета каждого из них и голоса первоначальных избирателей Остапа. Любой из лидеров в любом из первой тысячи туров (а тем более в 1001-м) имеет больше голосов, чем аутсайдер этого тура. Фаворит заведомо имеет больше, чем имел Остап в первом туре. Поэтому лидеры в сумме имеют в 1001-м туре больше голосов, чем Остап, и он не может стать победителем. Дополнительный вопрос (в условие предлагавшейся на олимпиаде задачи не входит): изменится ли ответ в задаче, если голоса выбывшего кандидата произвольно делятся между оставшимися?
Ответ
а)k=2001; б)k=1.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь