Задача о президентских выборах

[Trotil]

Посвящена новой избирательный системе )

Как это делалось в Анчурии
В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 миллионов избирателей, из которых только один процент поддерживает Мирафлореса (регулярная армия Анчурии). Мирафлорес, естественно, хочет быть избранным, но, с другой стороны, он хочет, чтобы выборы были демократическими. ``Демократическим голосованием'' Мирафлорес называет вот что: все избиратели разбиваются на равные группы; каждая из этих групп вновь разбивается на некоторое количество равных групп, причём большие группы могут разбиваться на разное количество меньших групп, затем эти группы снова разбиваются и т.д. В самых мелких группах выбирают представителя группы — выборщика — для голосования в большей группе: выборщики в этой большей группе выбирают выборщика для голосования в ещё большей группе и т.д. Наконец, представители самых больших групп выбирают президента. Мирафлорес делит избирателей на группы по своей воле и инструктирует своих сторонников, как им голосовать. Сможет ли он так организовать ``демократические'' выборы, чтобы его выбрали? (В каждой группе выборщики выбирают своего представителя простым большинством. При равенстве голосов побеждает оппозиция.)

Решение этой задачи такое:

сначала разберем условие задачи на "тройках":

1 уровень: 2 "за", 1 против. Побеждает "за". Потребовалось 66% голосов "за".

2 уровень: формируем 2 тройки по принципу 1-ого уровня, третья тройка может быть состоять из одних противников - она ни на что не влияет:
2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за"
0 "за", 3 против. -> "против"

4 "за" 5 "против" Потребовалось только 44,4% числа сторонников.

3 уровень:формируем 2 "девятки" по принципу 2-ого уровня, третья девятка может быть состоять из одних противников - она ни на что не влияет:

2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за"
0 "за", 3 против. -> "против"

2 "за", 1 против. -> "за"
2 "за", 1 против. -> "за" -------> "за" --------> "за"
0 "за", 3 против. -> "против"

0 "за", 3 против. -> "за"
0 "за", 3 против. -> "за" -------> "против"
0 "за", 3 против. -> "против"

8 "за", 19 "против" - побеждает "за", хотя их 30% и так далее...

"ЗА" "Против" "Выборщиков" "% За"
2 1 3 66.67%
4 5 9 44.44%
8 19 27 29.63%
16 65 81 19.75%
32 211 243 13.17%
64 665 729 8.78%
128 2 059 2 187 5.85%
256 6 305 6 561 3.90%
512 19 171 19 683 2.60%
1 024 58 025 59 049 1.73%
2 048 175 099 177 147 1.16%
4 096 527 345 531 441 0.77%
8 192 1 586 131 1 594 323 0.51%
16 384 4 766 585 4 782 969 0.34%
32 768 14 316 139 14 348 907 0.23%
65 536 42 981 185 43 046 721 0.15%

Но нам нужно разбивать 20 миллионов (на тройки разбить не получится), поэтому этот алгоритм нужно модифицировать.

И еще интересен общий вопрос: какое наименьшее число сторонников должен иметь Мирафлорес, чтобы победить на демократических выборах'', если общее количество избирателей N?