Выборы в совет директоров

Акционерное общество «Миноритарий», капитал которого разделен на $N$ обыкновенных акций, проводит выборы совета директоров, в который войдут $D$ человек. Выборы проходят по т.н. кумулятивной системе: владелец $n$ акций получает при голосовании $n\cdot D$ голосов, которые он распределяет между теми кандидатами, которых он хочет видеть в совете директоров. После голосования составляется рейтинг кандидатов по убыванию количества набранных ими голосов, и в совет директоров попадают первые $D$ человек по рейтингу. При этом если на последние несколько мест претендует большее число кандидатов, набравших одинаковое количество голосов, то эти несколько мест распределяются между такими кандидатами случайным образом.

Определите, сколько акций нужно иметь некоторому акционеру, чтобы гарантированно (вне зависимости от действий остальных акционеров) провести в совет директоров $d$ своих кандидатов (выразите это минимальное число акций через параметры $N$ , $D$ и $d$ ) в следующих двух случаях:
а) если голоса можно дробить;
б) если за каждого из кандидатов можно подать только целое число голосов.
По найденным формулам в каждом из двух случаев вычислите минимальное число акций при следующих наборах параметров: $(N=100, D=30, d=13)$ , $(N=100, D=30, d=17)$ .

Решение и ответ

а) Голоса можно дробить.

Из условия понятно, что нужно найти такое минимальное число акций, которое позволило бы нам получить в совете директоров ровно $d$ мест, даже если все остальные акционеры сговорятся и будут голосовать так, чтобы нам помешать. Эквивалентно, мы можем допустить избрание не более $D-d$ чужих кандидатов. Остальным акционерам удастся нам помешать, если они снабдят $D-d+1$ своих кандидатов количеством голосов, не меньшим, чем хотя бы у одного из наших $d$ кандидатов: тогда этот наш кандидат рискует не быть избранным, а мы рискуем не получить $d$ желанных мест.

Отсюда видно, что наша победа или поражение определяется количеством голосов у самого слабого нашего кандидата. Поэтому при любом числе имеющихся у нас голосов оптимальным распределением их между кандидатами является распределение поровну (при фиксированной сумме $d$ чисел мы максимизируем наименьшее из них). Таким образом, имея $nD$ голосов, мы отдадим за каждого из наших кандидатов $\frac{nD}{d}$ голосов. Стараясь помешать нам, остальные акционеры будут проводить $D-d+1$ своих кандидатов, за каждого из которых они отдадут $\frac{(N-n)D}{D-d+1}$ голосов: поскольку им необходимо, чтобы каждый из их кандидатов набрал голосов не меньше, чем какой-нибудь из наших, их успех также определяется количеством голосов у самого слабого их кандидата, и поэтому они также будут распределять голоса между своими кандидатами поровну.

Наших голосов хватит, чтобы гарантированно провести всех наших кандидатов, тогда и только тогда, когда $\frac{nD}{d} >\frac{(N-n)D}{D-d+1}$ : в этом случае любой из их кандидатов наберет строго меньше любого их наших. Решая это неравенство относительно $n$ , получим $n>\frac{Nd}{D+1}$ . Число акций, в отличие от числа голосов, конечно, целое, поэтому минимальное число акций, удовлетворяющее этом условию: $n_{\min} =\left[\frac{Nd}{D+1} \right]+1$ , где квадратные скобки обозначают целую часть числа.

б) За каждого из кандидатов можно подать только целое число голосов.

Все по-прежнему определяется количеством голосов, поданным за самого слабого из наших кандидатов, только теперь это количество равно $\left[\frac{nD}{d} \right]$ . Остаток от деления $nD$ на $d$ -- голоса, которые мы как-то разделим между некоторыми (не всеми) из наших кандидатов, но это уже ни на что не повлияет. Аналогично, за самого слабого из кандидатов противника будет подано $\left[\frac{D(N-n)}{D-d+1} \right]$ голосов. Необходимым и достаточным условием нашей победы является неравенство $\left[\frac{nD}{d} \right]>\left[\frac{D(N-n)}{D-d+1} \right]$ . Нам нужно найти минимальное $n$ , удовлетворяющее этому неравенству (не забываем, что $n$ целое). Просто выразить отсюда $n$ не получится, однако мы можем описать алгоритм отыскания этого минимального $n$ . Для этого рассмотрим пару свойств функции «целая часть числа»:

$\begin{array}{l} {[x]>[y]\Rightarrow x>y} \\ {x>y\Rightarrow [x]\ge [y]} \end{array}$

В их истинности нетрудно убедиться, мысленно разделив координатный луч на отрезки, ограниченные целыми числами. Функция «целая часть числа» переводит это число в левую границу отрезка, на котором находится наше число. Если $[x]>[y]$ , то $x$ и $y$ лежат на разных отрезках, причем $x$ правее. Если $x>y$ , то $x$ лежит правее, но эти числа либо лежат на одном отрезке, либо на разных.

Если $n$ -- решение нашей задачи ( $n$ удовлетворяет условию $\left[\frac{nD}{d} \right]>\left[\frac{D(N-n)}{D-d+1} \right]$ ), то для этого $n$ выполняется $\frac{nD}{d} >\frac{(N-n)D}{D-d+1}$ , что, как мы помним из пункта а), эквивалентно условию $n>\frac{Nd}{D+1}$ ; минимальное $n$ , удовлетворяющее этому условию, равно $\left[\frac{Nd}{D+1} \right]+1$ . Однако из выполнения условия $\frac{nD}{d} >\frac{(N-n)D}{D-d+1}$ не следует нужного нам $\left[\frac{nD}{d} \right]>\left[\frac{D(N-n)}{D-d+1} \right]$ , а следует только $\left[\frac{nD}{d} \right]\ge \left[\frac{D(N-n)}{D-d+1} \right]$ .

Возьмем $n=\left[\frac{Nd}{D+1} \right]+1$ и подставим в это неравенство. Если оно выполняется как строгое неравенство, значит данное $n$ -- искомое: имея $n$ акций, мы точно проведём $d$ своих кандидатов, а $n-1$ акций уже не будут удовлетворять необходимому условию.

Что же делать, если при данном $n$ неравенство выполняется как равенство? Увеличим $n$ на единицу. Нетрудно убедиться в том, что левая часть вырастет больше, чем на единицу, а правая часть уменьшится. Отсюда неизбежно следует, что неравенство станет строгим. Значит, $n=\left[\frac{Nd}{D+1} \right]+2$ -- искомое.