Задача.
В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В Анчурии 20 000 000 избирателей, из которых только один процент (армия Анчурии) поддерживает Мирафлореса. Он хочет быть демократически избранным. "Демократическим голосованием" Мирафлорес называет вот что: всех избирателей разбивают на несколько равных групп, затем каждую из этих групп вновь разбивают на некоторое количество равных групп, затем эти последние группы снова разбивают на равные группы и так далее; в самых мелких группах выбирают представителя группы — выборщика, затем выборщики выбирают представителей для голосования в ещё большей группе и так далее; наконец, представители самых больших групп выбирают президента. Мирафлорес сам делит избирателей на группы. Может ли он так организовать выборы, чтобы его избрали президентом? (При равенстве голосов побеждает оппозиция.)
Решение.
Спойлер (Отобразить)Да, сможет. Если 9 избирателей разбиты на три группы по три
избирателя так, что в двух группах есть по два сторонника Мирафлореса, то победят
сторонники Мирафлореса, хотя их — 4 из 9. Значит, на многоступенчатых выборах
может победить кандидат, за которого проголосовало меньшинство.
Нетрудно сообразить, что при двуступенчатых выборах с большим числом избирателей процент голосов, необходимый для победы, может быть ещё меньше, но
всё-таки заведомо больше 25%. При трёхступенчатой системе этот процент можно
сделать ещё ниже. Например, заменив в предыдущей конструкции каждого избирателя группой из 100 человек так, что все группы противников Мирафлореса состоят
только из его противников, а в группах сторонников — 51 сторонник и 49 противников, то мы получим пример ситуации, где сторонники Мирафлореса составляют
только (4/9)*(51/100)=(17/75) от общего числа избирателей и тем не менее побеждают.
После этих предварительных замечаний перейдём непосредственно к решению задачи. Разобьём всех избирателей на 5 групп по 4 миллиона в каждой так, что две группы целиком состоят из противников Мирафлореса. Каждую из этих групп "первого ранга" разобьём на 5 групп второго ранга, причём из пяти групп, составляющих любую группу сторонников первого ранга, три — сторонников. Поскольку
20 000 000= 5^7 * 4^4,
то удобно проводить выборы в 7+4 = 11 туров; для победы Мирафлореса достаточно, чтобы за него проголосовало 3^11 = 177 147 избирателей, что меньше одного процента. Впрочем, воспользовавшись разложением
20 000 000= 5^7 * 8^2 * 4,
видим, что Мирафлоресу достаточно иметь 3^7 * 5^2 * 3 = 164 025 сторонников.
Задачка из физико-математического журнала "Квант":
http://kvant.info/zkm_sol/0001/0001.pdf (Отредактировано автором: 12 Октября, 2011 - 20:38:55) |