Выборы и шарики
На выборах президента страны Х соревнуются два кандидата. Главный вопрос, который стоит на повестке дня предвыборной кампании — сколько воздушных шариков развесить на главной площади столицы ко Дню независимости страны Х. Вечером накануне выборов кандидатам предстоит участвовать в теледебатах, на которых каждый из них должен будет окончательно объявить, сколько шариков он повесит на площади, если станет президентом. У каждого гражданина страны есть свое любимое число, и если какой-то из кандидатов предложит именно это число шариков, то избиратель проголосует за него (если любимое число будет предложено обоими кандидатами, гражданин сделает выбор, подбрасывая монетку). Если же любимого избирателем числа не будет среди предложенных вариантов, то он проголосует за того кандидата, который предложит число ближе к его любимому (если разница предложений с любимым числом будет одинаковая, то он тоже подбросит монетку). Самое распространенное любимое число — 50 шариков, его любят 51 человек. 49 и 51 шарик любят по 50 человек, 48 и 52 шарика — по 49 человек, и т. д., 0 и 100 шариков — по 1 человеку. Это распределение любимых чисел известно кандидатам. Чем закончатся дебаты, если оба кандидата стремятся выиграть выборы?
Решение
Для начала докажем, что если один из кандидатов назвал число 50, а второй назвал число X ≠ 50, то первый выиграет. Если X < 50, то за первого кандидата проголосуют по крайней мере все, чьи любимые числа 50, 51, … 100, то есть 51 + 50 + … + 1 = 1326 человек. Это уже больше половины от общего числа избирателей. Симметрично можно показать, что первый кандидат получит больше половины голосов, если X > 50. Дебаты закончатся тем, что оба кандидата назовут число «50». Если предположить, что это не так, можно показать, что кто-то из кандидатов действует неоптимально для себя. Рассмотрим варианты окончания дебатов, отличные от указанного выше: $\bullet$ Если оба кандидата назвали числа, отличные от 50, то $\circ$ если эти числа находятся на одинаковом расстоянии от 50 (в том числе если они равны), то исход выборов определяется монеткой, но любой кандидат, кто изменит свой выбор на 50, выиграет с определенностью; $\circ$ если эти числа находятся на разном расстоянии от 50, то победитель выборов определен однозначно, но в этом случае проигравший вел себя неоптимально: назвав число 50, он бы мог выиграть. $\bullet$ Если один из кандидатов назвал число 50, а другой отличное от 50 число, то второй вел себя неоптимально: так он гарантированно проиграет, а, назвав 50, мог бы выиграть с вероятностью 50%. Выходит, что в любом исходе, в котором хотя бы кто-то называет число, отличное от 50, кто-то ведет себя неоптимально. С другой стороны, если оба назовут число 50, то судьбу выборов определит монетка, но никто из кандидатов не мог бы повысить свои шансы на победу, назвав что-то другое: если он изменит свой выбор, то гарантированно проиграет.