В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 миллионов избирателей, из которых только один процент поддерживает Мирафлореса (регулярная армия Анчурии). Мирафлорес, естественно, хочет быть избранным, но, с другой стороны, он хочет, чтобы выборы были "демократическими". "Демократическим голосованием" Мирафлорес называет вот что: все избиратели разбиваются на равные группы; каждая из этих групп вновь разбивается на некоторое количество равных групп, причём большие группы могут разбиваться на разное количество меньших групп, затем эти группы снова разбиваются и т.д. В самых мелких группах выбирают представителя группы "выборщика" для голосования в большей группе: выборщики в этой большей группе выбирают выборщика для голосования в ещё большей группе и т.д. Наконец, представители самых больших групп выбирают президента. Мирафлорес делит избирателей на группы по своей воле и инструктирует своих сторонников, как им голосовать. Сможет ли он так организовать "демократические" выборы, чтобы его выбрали? (В каждой группе выборщики выбирают своего представителя простым большинством. При равенстве голосов побеждает оппозиция.)
Эта задача была предложена в 1969 году на Московской математической олимпиаде. Эта же задача получила №1 в Задачнике "Кванта".
Оказывается, Мирафлорес может при такой системе быть избранным. Приведу алгоритм для его возможных действий.
Разобьём всё население на группы по 5 человек. Таких групп будет 4 000
000. В 66 666 групп отправим по трое военных.
После первого круга голосования у Мирафлореса будет уже 66 666 выборщиков из четырёх миллионов.
На втором круге голосование проведём аналогично. Групп по 5 выборщиков будет 800 000, а в 22 222 группах окажется по трое военных.
На третьем круг выборщиков останется 160 000, а среди них будет 7407 тех, кто поддерживает Мирафлореса.
Продолжим так действовать.
На четвёртом круге выборщиков останется 32000, среди которых 2469 военных.
На пятом круге выборщиков 6400, а военных - 823.
На шестом - выборщиков 1280, а военных - 274.
На седьмом - выборщиков будет 256, а военных среди них - 91.
Теперь разобьём выборщиков в группы по 8 человек. Чтобы Мирафлоресу получить в таких группах большинство, ему в группы надо отправить по 5 военных.
Групп будет 32, а поддерживать президента будет 18 человек.
Вот она, "демократическая" победа!
На самом деле, победить таким способом можно и когда сторонников ещё меньше, а именно, 164 025. Почему ровно столько?
Подумайте, дорогие читатели!