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

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

Из условия понятно, что нужно найти такое минимальное число акций, которое позволило бы нам получить в совете директоров ровно $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$ -- искомое.

Выполним этот алгоритм для двух наборов параметров из условия:

1) $N=100, D=30, d=13$.

$\left[\frac{Nd}{D+1} \right]+1=[41,94]+1=42$

$\begin{array}{l} {\left[\frac{nD}{d} \right]=[96,92]=96} \\ {\left[\frac{D(N-n)}{D-d+1} \right]=[96,67]=96} \end{array}$

Раз целые части получились одинаковые, надо увеличить число акций до 43:

$\begin{array}{l} {\left[\frac{nD}{d} \right]=[99,23]=99} \\ {\left[\frac{D(N-n)}{D-d+1} \right]=[95]=95} \end{array}$

Отметим, что при возможности дробления голосов нам хватило бы 42-х акций.
2)$N=100, D=30, d=17$

$\left[\frac{Nd}{D+1} \right]+1=[54,84]+1=55$

$\begin{array}{l} {\left[\frac{nD}{d} \right]=[97,06]=97} \\ {\left[\frac{D(N-n)}{D-d+1} \right]=[96,43]=96} \end{array}$

При данных параметрах минимальное число акций составит 55 как в случае дробления голосов, так и при запрете на дробление.