М1. Выборы

Задача из журнала «Квант» (1970 год, 1 выпуск)

Задача

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

Ответ: Да, сможет.

Прежде всего разберемся, как может на «многоступенчатых» выборах победить кандидат, за которого голосует меньшинство. (Кстати, по такой системе голосуют во многих капиталистических странах.) Самый простой пример такой ситуации изображен на рисунке 1: здесь девять избирателей — четыре «черных» и пять «голубых» — разбиты на три группы потри избирателя так, что в двух группах побеждают черные, и поэтому в результате таких «двухступенчатых выборов» будет избран кандидат черных, хотя число его сторонников составляет только $\frac{4}{5}$ от общего числа избирателей. (Нетрудно сообразить,что при двухступенчатых выборах с большим числом избирателей процент голосов, достаточный для победы, может быть еще меньше, но все-таки заведомо больше $25\%.$) Ясно, что при трехступенчатой системе выборов этот процент можно сделать еще ниже. Например, если заменить на рисунке $1$ каждого избирателя группой из ста человек, причем так, что в голубой группе все сто избирателей голубые, а в черной — $51$ черный и $49$ голубых, то мы получим пример ситуации, где черные составляют только $49\%$ от общего числа избирателей и тем не менее побеждают.

После этих предварительных соображений приведем решение задачи.

Разобьем всех избирателей на 5 групп по 4 миллиона в каждой так, что две группы целиком состоят из противников Мирафлореса (назовем эти группы «голубыми», а три остальные — «черными»). Каждую из этих групп «первого ранга» снова разобьем на 5 групп второго ранга, причем из пяти групп, составляющих черную группу первого ранга, три— черных и т.д., как указано в таблице.

Ясно, что при таком разбиении для победы Мирафлореса достаточно, чтобы за него проголосовала $\frac{3^{11}}{2^8\cdot5^7} = \frac{177147}{20000000} < \frac{1}{100}$ часть всех избирателей. Тем самым, поскольку армия составляет $\frac{1}{100}$ часть избирателей и поддерживает Мирафлореса, он сможет победить.

Ранг группы $r$ 1 2 3 4 5 6 7 8 9
Общее число групп ранга $r$ $5$ $5^{2}$ $5^{3}$ $5^{4}$ $5^{5}$ $5^{6}$ $5^{7}$ $2^{4}\cdot5^{7}$ $2^{8}\cdot5^{7}$
Сколько из них черных $3$ $3^{2}$ $3^{3}$ $3^{4}$ $3^{5}$ $3^{6}$ $3^{7}$ $3^{9}$ $3^{11}$
Сколько человек в 1 группе ранга $\:r$ $4\cdot 10^{6}$ $8\cdot 10^{5}$ $16\cdot 10^{4}$ $32\cdot 10^{3}$ $64\cdot 10^{2}$ $1280$ $256$ $16$ $1$
На сколько групп ранга $r+1$ разбивается группа ранга $r$ 5 5 5 5 5 5 16 16
Сколько черных подгрупп ранга $r+1$ у черной группы ранга $r$ 3 3 3 3 3 3 9 9

Некоторые читатели пытались решить следующий, более общий вопрос: какое наименьшее число сторонников должен иметь Мирафлорес, чтобы победить на «демократических выборах», если общее количество избирателей $N$. Разумеется, ответ на этот вопрос зависит не столько от величины числа $N$ , сколько от того, как оно раскладывается на множители. Если, скажем, $N$ — число простое, то избирателей вообще никак нельзя разбить на равные группы (кроме тривиального способа: $N$ групп по одному человеку) и для победы нужно иметь простое большинство. Покажем, как ответить на этот вопрос для любого $N$ .

Рассмотрим такое разбиение $N$ человек на группы (1-го, 2-го и т. д. ранга), при котором побеждает Мирафлорес и число его сторонников — наименьшее из возможных. Очевидно, можно считать, что в группах, голосующих против него, нет ни одного его сторонника и что все черные группы одного ранга разбиты совершенно одинаково. Удобно использовать обозначение $\left[\:\right]$ — «целая часть» $\left[x\right]$ — наибольшее целое число, не превосходящее $x$; например, $\left[2\right] = 2,\left[3\frac{1}{2}\right] = 3.$ Ясно, что если некоторая черная группа состоит из $k$ групп следующего ранга, то среди них должно быть не менее $\left[\frac{k}{2}+1\right]$ черных. Пусть каждая группа $r$-го ранга $\left(r = 1,2,\ldots ,m—1\right)$ разбита на $k_{r}$, групп меньшего, ранга, а группы последнего $m$-го ранга состоят из 1 человека. Тогда для победы черных необходимо иметь по крайней мере. $B = \left(\left[\frac{k_{1}}{2}\right]+1\right)\left(\left[\frac{k_{2}}{2}\right]+1\right)\ldots \left(\left[\frac{k_{m}}{2}\right]+1\right)$ черных голосов. Наша задача свелась к такой: разложить данное $N$ в произведение таких сомножителей $k_{1},k_{2},\ldots ,k_{m},$ чтобы произведение $B$ было минимально. Пусть $N = k_{1}k_{2}\ldots k_{m}$ — такое разложение. Как показывает следующая лемма, можно предполагать, что в этом разложении нет сомножителей $k$ вида $k = pq$, где $p$ и $q$ больше 2 (если такие есть, можно провести дальнейшее разложение, не увеличивая $В$).

Лемма.
$\left(\left[\frac{p}{2}\right]+1\right)\left(\left[\frac{q}{2}\right]+1\right)\leqslant\frac{pq}{2}+1$ для всех целых $p$ и $q$ больших 2.

Доказательство. Если $p$ и $q$ оба четны, то неравенство можно переписать так $\left(\frac{p}{2}+1\right)\left(\frac{pq}{2}+1\right)\leqslant\frac{pq}{2}+1,$ $\left(p+2\right)(\left(q+2\right)\leqslant 2pq+4,$ $pq-2q-2p+4\geqslant4,$ $(p-2)(q-2)\geqslant4$ что, очевидно, верно для $p>2$ и $q>2$. В случае, когда одно из чисел $p,q,$ например $р$, четно, а другое нечетно, имеем:$\left(\frac{p}{2}+1\right)\left(\frac{q}{2}+\frac{1}{2}\right)\leqslant\frac{pq}{2}+1,$ $\left(p+2\right)\left(q+1\right)\leqslant2pq+4,$ $pq-2q-p+2\geqslant0,\left(p-2\right)\left(q-1\right)\geqslant 0$

Случай, когда $p$ и $q$ нечетны, разбирается аналогично. Лемма доказана. (отсюда сразу следует, что нечетные $N$ надо раскладывать на простые множители «до конца».) Осталось разобраться с двойками.

Можно считать, что в разложении нет сомножителей вида $2q$, где $q$ нечетно, поскольку $2\left(\left[\frac{q}{2}\right]+1\right) = \left[\frac{2q}{2}\right]+1$

Отсюда из леммы вытекает, что из четных сомножителей можно ограничиться только двойками, четверками и восьмерками. Далее ясно, что $2\cdot2$ хуже, чем $4$, поскольку $\left(\left[\frac{2}{2}\right]+1\right)^{2}=4>\left[\frac{4}{2}\right]+1=3$ Выгодно $2\cdot4$ заменить на 8, поскольку $2\cdot3 = 5>5; 4\cdot4$ лучше, чем $2\cdot8$, поскольку $3\cdot3 = 9; 2\cdot5 = 10$ и, наконец, $4\cdot4\cdot4$ менее выгодно, чем $8\cdot8$, поскольку $3\cdot3\cdot3 =27;$ $5\cdot5 = 25,$ так что больше двух четверок оставлять нельзя Итак, окончательный ответ такой: пусть $N = 2^{d}p_{1},\ldots ,p_{m}$, где $m\geqslant0,d\geqslant0$ — целые, $p_{1},\ldots,p_{m}$ — нечетные простые числа. Обозначим произведение $\frac{p_{1}+1}{2}\ldots \frac{p_{m}+1}{2}$ через $P$.

Тогда наименьшее число сторонников Мирафлореса, достаточное для победы, равно

  • $B = 2P,$ если $d = 1$(т.е. $N = 2p_{1}\ldots p_{m}$);
  • $B = 5^{n}P,$ $d = 3n\left(N=8^{n}p_{1}\ldots p_{m}\right);$
  • $B = 3\cdot5^{n}P$ $d = 3n+2\left(N=4\cdot8^{n}p_{1}\ldots p{m}\right);$
  • $B = 9\cdot5^{n}P$ $d = 3n+4\left(N=4^{2}\cdot8^{n}p_{1}\ldots p_{m}\right);$
здесь $n$-целое число,$n\geqslant0.$

Этот ответ нашли ученик 9-го класса из Томска А.Гришков и (в другой форме) еще несколько читателей в частности, для $N = 20000000 = 2^{8}\cdot5^{7}=4\cdot8^{2}\cdot5^{7}$ получаем $B=3\cdot5^{2}\cdot3^{7} = 164025$

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *