Задачка о системах выборов и голосования

← →
Alx2 © (2005-05-22 15:38) [0]

Преамбула:

В центре столицы Венесуэлы Каракасе, около дворца правительства Мирафлорес, в преддверии решения о проведении плебисцита по отношению к президенту Уго Чавесу прошли массовые манифестации. Как передает РИА “Новости”, в ходе беспорядков, которые, по неподтвержденным данным, были организованы сторонниками нынешнего президента, сожжены три автобуса. Кроме того, по зданию мэрии были произведены несколько выстрелов из автомата. Мэр города, общавшийся в это время с журналистами, был вынужден прервать свое интервью.

Как правительство, так и оппозиционные силы заявляют о своей победе в ходе подсчета голосов, прошедшего на этой неделе, по отношению к главе государства. Обе стороны пытаются уличить друг друга в подлоге данных по проведению национального референдума об отставке президента. По словам лидера oрганизации "Демократическая координация" Энрике Мендосы, оппозиции удалось собрать голосов против Уго Чавеса больше, чем это необходимо для проведения плебисцита. В то же время министр информации Джессе Чакон утверждает, что результат сбора подписей будет "благоприятен" для президента.

Как сообщил вице-президент Национального избирательного совета Эсекиель Самора, результаты подсчета голосов должны быть официально обнародованы в пятницу. В случае если оппозиции удастся получить 20% голосов избирателей, референдум состоится 8 августа. Это станет последним шансом оппозиции лишить полномочий Уго Чавеса досрочно до проведения следующих выборов 2006 года.

А теперь задачка, 35-летней давности (почти пророчество):

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

Порешаем? :)

← →
Alx2 © (2005-05-22 15:39) [1]

Ссылка на "преамбулу": http://www.polit.ru/news/2004/06/04/suale.html

← →
MBo © (2005-05-24 13:34) [2]

Для простоты наброска решения возьмем требуемое для выигрыша соотношение 2:1, а число избирателей 14348907 (3^15, степень тройки, ближайшая к 20000000)
В финальном туре нужно обеспечить двух сторонников и одного противника:
1) 2:1
2) 2:1 2:1 3
3) 2:1 2:1 3/2:1 2:1 3/ 3 3 3
4) 2:1 2:1 3/ 2:1 2:1 3/3 3 3//2:1 2:1 3/ 2:1 2:1 3/3 3 3//3 3 3/3 3 3/3 3 3
...
(двойки относятся к сторонникам, тройки и единицы - к оппозиции)
Видно, что в n)-ом туре от конца участвует 3^n человек, из них
2^n сторонников, остальные - противники.
Построение дерева можно закончить, когда требуемое число сторонников станет менее одного процента от всех

2^n/(3^n-2^n)<0.01
(3/2)^n-1>100
(3/2)^n>99
n*ln(3/2)>ln(99)
n>11.3
т.е. достаточно 12 уровней выборов.
При этом получается 4096 групп сторонников и 527345 групп оппозиции (по 27 избирателей в группе)
Это решение избыточно за счет того, что группы сторонников "чистые", чего в общем-то не требуется, и 2/3 существенно больше требуемых 50%+Epsilon, но показывает возможность осуществления плана Мирафлореса.

← →
MBo © (2005-05-24 13:36) [3]

> 2^n/(3^n-2^n)

Зря здесь в знаменателе 2^n отнимал, и далее 99 на 100 нужно заменить, но непринципиально

← →
Alx2 © (2005-05-24 13:51) [4]

>MBo © (24.05.05 13:36) [3]
20 000 000 на три равных группы не разделить. Переход от 3^n ?

← →
nikkie © (2005-05-24 14:05) [5]

20 000 000 = 2^8 * 5^7
на верхних уровнях образуем группы-пятерки с соотношением 3:2.
таких уровней можем организовать 7. в основании необходимо иметь 3^7 "наших".
дальше образуем группы-четверки с соотношением 3:1.
таких уровней можем организовать 4. для победы надо иметь 3^7 * 3^4 "наших".
в результате имеем
3^7 * 3^4 = 177147 "наших" - менее 1 процента.

>nikkie © (24.05.05 14:05) [5]
У меня также :)

Чтобы выбрать нужного президента, необходимо голосование большинства выборщиков. Пусть f(n) - количество нужных избирателей.
Делим наши 20 000 000 на пять частей (почти от балды, можно и на четыре)
и требуем, чтобы в трех победили. В итоге количество
нужных избирателей: f(n) = 3 * f(n/5)
Когда -нибудь деление на 5 частей станет невозможным, так как
20 000 000 = 2^8*5^7
Тогда делим на четыре и требуем, чтобы в трех победили. Т.е.
f(n) = 3 * f(n/4) Так получаем, что
f(20 000 000) =f(2^8*5^7) = f(4^4*5^7) = 20 000 000 * (3/4)^4*(3/5)^7 = 3^11

Осталось про минимальное количество в общем случае подумать :)

>20 000 000 на три равных группы не разделить
А ты азартен, Парамоша ;) (© Бег)
3:2, (7 туров, пока делится нацело на 5), потом 3:1

Задачка о системах выборов и голосования Найти похожие ветки