Разделы 
Дополнительно
Задача по математике - 3375
2019-06-03 
В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если этот кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся.
На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре $k$-е место по числу голосов. Определите наибольшее возможное значение $k$, если Остап был избран а) в 1002-м туре; б) в 1001-м туре.
Решение:
а) Остап не мог занять последнее, 2002-е место в первом туре, поскольку иначе он сразу же выбыл бы из числа кандидатов. Поэтому $k \leq 2001$.
Пусть все кандидаты в первом туре набрали почти поровну, Остап занял предпоследнее место и в каждом следующем туре получал все голоса выбывшего кандидата. Тогда Остап победит в тот момент, когда количество выбывших кандидатов достигнет половины. Это случится как раз в 1002-м туре.
Выполним точный подсчет в случае, когда кандидаты в первом туре набрали $10^6, 10^6 + 1, \cdots , 10^6 + 2001$ голос. Тогда в 1001-м туре у Остапа еще меньше половины голосов, а именно: голоса всех кандидатов, занявших последние 1001 место в первом туре. Однако в 1002-м туре у него уже более половины всех голосов. Действительно,в 1002-м туре у Остапа
$10^6 + (10^6 + 1) + \cdots + (10^6 + 1001) = 1002 \cdot 10^6 + \frac{1001 \cdot 1002}{2} = 1002 \cdot 10^6 + 1001 \cdot 501 = 1 002 501 501$
голосов, а всего избирателей
$10^6 + (10^6 + 1) + \cdots + (10^6 + 2001) = 2002 \cdot 10^6 + \frac{2001 \cdot 2002}{2} = 2002 \cdot 10^6 + 2001 \cdot 1001 = 2 004 003 001$.
Нетрудно проверить, что это меньше удвоенного числа голосов Остапа.
б) Предположим, что $k > 1$. Тех, кто выбыл в первой тысяче туров, назовем аутсайдерами, а всех остальных кандидатов, кроме Остапа, - лидерами. Кандидата, занявшего первое место в первом туре, назовем фаворитом. Поскольку число аутсайдеров 1000, а лидеров 1001, то один из лидеров не получал голосов аутсайдеров. В первом туре (и позже) он имел больше голосов, чем любой аутсайдер (так как в конечном счете выбыл аутсайдер, а не этот лидер). Значит, фаворит тоже имел в первом туре больше голосов, чем любой аутсайдер. Поэтому фаворит является лидером.
Максимальное число голосов, которое Остап мог собрать к 1001-му туру, - это все голоса аутсайдеров на момент вылета каждого из них и голоса первоначальных избирателей Остапа. Любой из лидеров в любом из первой тысячи туров (а тем более в 1001-м) имеет больше голосов, чем аутсайдер этого тура. Фаворит заведомо имеет больше, чем имел Остап в первом туре. Поэтому лидеры и фаворит в сумме имеют в 1001-м туре больше голосов, чем Остап, и он не может стать победителем.
Ответ: а) $k = 2001$; б) $k = 1$.
В городе Удоеве выборы мэра проходят следующим образом. Если в очередном туре голосования никто из кандидатов не набрал больше половины голосов, то проводится следующий тур с участием всех кандидатов, кроме последнего по числу голосов. (Никогда два кандидата не набирают голосов поровну; если кандидат набрал больше половины голосов, то он становится мэром и выборы заканчиваются.) Каждый избиратель в каждом туре голосует за одного из кандидатов. Если этот кандидат вышел в следующий тур, то избиратель снова голосует за него. Если же кандидат выбыл, то все его избиратели голосуют за одного и того же кандидата из числа оставшихся.
На очередных выборах баллотировалось 2002 кандидата. Мэром стал Остап Бендер, занявший в первом туре $k$-е место по числу голосов. Определите наибольшее возможное значение $k$, если Остап был избран а) в 1002-м туре; б) в 1001-м туре.
Решение:
а) Остап не мог занять последнее, 2002-е место в первом туре, поскольку иначе он сразу же выбыл бы из числа кандидатов. Поэтому $k \leq 2001$.
Пусть все кандидаты в первом туре набрали почти поровну, Остап занял предпоследнее место и в каждом следующем туре получал все голоса выбывшего кандидата. Тогда Остап победит в тот момент, когда количество выбывших кандидатов достигнет половины. Это случится как раз в 1002-м туре.
Выполним точный подсчет в случае, когда кандидаты в первом туре набрали $10^6, 10^6 + 1, \cdots , 10^6 + 2001$ голос. Тогда в 1001-м туре у Остапа еще меньше половины голосов, а именно: голоса всех кандидатов, занявших последние 1001 место в первом туре. Однако в 1002-м туре у него уже более половины всех голосов. Действительно,в 1002-м туре у Остапа
$10^6 + (10^6 + 1) + \cdots + (10^6 + 1001) = 1002 \cdot 10^6 + \frac{1001 \cdot 1002}{2} = 1002 \cdot 10^6 + 1001 \cdot 501 = 1 002 501 501$
голосов, а всего избирателей
$10^6 + (10^6 + 1) + \cdots + (10^6 + 2001) = 2002 \cdot 10^6 + \frac{2001 \cdot 2002}{2} = 2002 \cdot 10^6 + 2001 \cdot 1001 = 2 004 003 001$.
Нетрудно проверить, что это меньше удвоенного числа голосов Остапа.
б) Предположим, что $k > 1$. Тех, кто выбыл в первой тысяче туров, назовем аутсайдерами, а всех остальных кандидатов, кроме Остапа, - лидерами. Кандидата, занявшего первое место в первом туре, назовем фаворитом. Поскольку число аутсайдеров 1000, а лидеров 1001, то один из лидеров не получал голосов аутсайдеров. В первом туре (и позже) он имел больше голосов, чем любой аутсайдер (так как в конечном счете выбыл аутсайдер, а не этот лидер). Значит, фаворит тоже имел в первом туре больше голосов, чем любой аутсайдер. Поэтому фаворит является лидером.
Максимальное число голосов, которое Остап мог собрать к 1001-му туру, - это все голоса аутсайдеров на момент вылета каждого из них и голоса первоначальных избирателей Остапа. Любой из лидеров в любом из первой тысячи туров (а тем более в 1001-м) имеет больше голосов, чем аутсайдер этого тура. Фаворит заведомо имеет больше, чем имел Остап в первом туре. Поэтому лидеры и фаворит в сумме имеют в 1001-м туре больше голосов, чем Остап, и он не может стать победителем.
Ответ: а) $k = 2001$; б) $k = 1$.
