Неравенство в гильдии
В компьютерной игре у Алекса есть несколько друзей в гильдии. В начале дня у одного из друзей было 5 единиц ресурса "золото", а у остальных (включая Алекса) — 0. После совместного прохождения подземелья каждый из друзей Алекса получил бонус 4 золота, но Алекс бонуса не получил из-за бага в системе. Чтобы исправить это, администратор сервера вручил Алексу некоторое количество золота. Будучи знатоком теории игр, администратор хотел, чтобы Алекс обрадовался (получил много золота), но чтобы неравенство распределения золота в гильдии не выросло. Он выдал Алексу 21 золото, и индекс Джини распределения золота в гильдии не увеличился. Найдите максимальное количество человек в рассматриваемой гильдии.
Индекс Джини можно выразить через площадь A под кривой Лоренца:
G=1-2A.
Отсюда условие «неравенство не выросло» эквивалентно
G_{\text{после}} \le G_{\text{до}} \;\Longleftrightarrow\; A_{\text{после}} \ge A_{\text{до}}
Мы будем сравнивать площади под кривыми Лоренца до и после исправления бага, не используя формулу для G.
1. Распределения "до" и "после"
Пусть у Алекса m друзей. Тогда всего в гильдии n=m+1 человек.
До вмешательства администратора:
Сначала у одного друга было 5 золота, остальные (включая Алекса) - по 0.
После подземелья каждый друг получил 4 золота, Алекс ничего не получил.
Итого до выдачи 21 золота Алексу: у одного друга: 5+4=9, у остальных m-1 друзей: по 4, у Алекса: 4.
Отсортированное распределение:
(0,\; \underbrace{4,\dots,4}_{m-1\ \text{человек}},\; 9)
Общий доход:
I_{\text{до}} = 0 + 4(m-1) + 9 = 4m + 5.
Выделим три группы:
Группа 1 : Алекс ( 1 человек), доход 0.
Группа 2 : остальные друзья с 4 (их m-1 ), суммарный доход 4(m-1).
Группа 3 : самый богатый друг с 9.
Доли населения:
x_1^{(\text{до})} = \frac{1}{n}, \qquad x_2^{(\text{до})} = \frac{1+(m-1)}{n} = \frac{m}{n}, \qquad x_3^{(\text{до})} = 1.
Доли суммарного дохода:
y_1^{(\text{до})} = \frac{0}{T_{\text{до}}} = 0, \qquad y_2^{(\text{до})} = \frac{4(m-1)}{4m+5}, \qquad y_3^{(\text{до})} = 1.
Кривая Лоренца до выдачи проходит через точки
(0,0), \qquad \left(x_1^{(\text{до})}, y_1^{(\text{до})}\right) = \left(\frac{1}{n}, 0\right), \qquad \left(x_2^{(\text{до})}, y_2^{(\text{до})}\right) = \left( \frac{m}{n}, \frac{4(m-1)}{4m+5} \right), \qquad (1,1).
Это ломаная из трёх отрезков (см. иллюстрацию в конце).
После вмешательства администратора
Администратор выдал Алексу 21 золото.
Тогда распределение становится:
\left( \underbrace{4,\dots,4}_{m-1\ \text{человек}}, 9,\,21 \right) так как теперь Алекс самый богатый.
Общий доход:
I_{\text{после}} = 4(m-1) + 9 + 21 = 4m + 26.
Группы:
Группа 1 : m-1 человек с доходом 4, суммарный доход 4(m-1).
Группа 2 : один человек с 9.
Группа 3 : Алекс с 21.
Доли населения:
x_1^{(\text{после})} = \frac{m-1}{n}, \qquad x_2^{(\text{после})} = \frac{m}{n}, \qquad x_3^{(\text{после})} = 1.
Суммарные доходы первых k групп:
\text{Группа 1: } 4(m-1), \qquad \text{Группы 1+2: } 4(m-1) + 9 = 4m + 5, \qquad \text{Все: } 4m + 26.
Соответствующие доли дохода:
y_1^{(\text{после})} = \frac{4(m-1)}{4m+26}, \qquad y_2^{(\text{после})} = \frac{4m+5}{4m+26}, \qquad y_3^{(\text{после})} = 1.
Кривая Лоренца после выдачи проходит через точки
(0,0), \qquad \left(x_1^{(\text{после})}, y_1^{(\text{после})}\right) = \left( \frac{m-1}{n}, \frac{4(m-1)}{4m+26} \right) \quad \left(x_2^{(\text{после})}, y_2^{(\text{после})}\right) = \left( \frac{m}{n}, \frac{4m+5}{4m+26} \right), \qquad (1,1).
Опять получаем ломаную из трёх отрезков.
2. Площади под кривыми Лоренца: треугольник + две трапеции
Площадь до исправления бага:
Точки: (0,0), \qquad \left(\frac{1}{n}, 0\right), \qquad \left(\frac{m}{n}, y_2\right),
где y_2 := y_2^{(\text{до})} = \frac{4(m-1)}{4m+5}.
Первый отрезок от x=0 до x=1/n идёт по оси x, высота нулевая, площадь равна 0.
Вторая фигура - трапеция между x=1/n и x=m/n, нижняя высота 0, верхняя - y_2, основание: \frac{m}{n} - \frac{1}{n} = \frac{m-1}{n}.
Площадь:
S_2^{(\text{до})} = \frac{m-1}{n} \cdot \frac{0 + y_2}{2} = \frac{m-1}{2n}\, y_2.
Третья фигура - трапеция между x=m/n и x=1, высоты y_2 и 1, основание
1 - \frac{m}{n} = \frac{n-m}{n} = \frac{1}{n}.
Площадь:
S_3^{(\text{до})} = \frac{1}{n} \cdot \frac{y_2 + 1}{2} = \frac{y_2 + 1}{2n}.
Таким образом, общая площадь:
A_{\text{до}} = S_2^{(\text{до})} + S_3^{(\text{до})} = \frac{m-1}{2n} y_2 + \frac{y_2 + 1}{2n}.
Подставляем n=m+1 и y_2 = \frac{4(m-1)}{4m+5} :
A_{\text{до}} = \frac{1}{2(m+1)} \left( (m-1)\frac{4(m-1)}{4m+5} + \frac{4(m-1)}{4m+5} + 1 \right).
Складываем первые два слагаемых:
(m-1)\cdot 4(m-1) + 4(m-1) = 4(m-1)\big((m-1)+1\big) = 4(m-1)m
Тогда
A_{\text{до}} = \frac{1}{2(m+1)} \left( \frac{4(m-1)m}{4m+5} + 1 \right) = \frac{1}{2(m+1)} \cdot \frac{4(m-1)m + (4m+5)}{4m+5}.
Числитель:
4(m-1)m + 4m + 5 = 4m^2 - 4m + 4m + 5 = 4m^2 + 5.
Таким образом,
A_{\text{до}} = \frac{4m^2 + 5}{2(m+1)(4m+5)}
Площадь после исправления бага:
Точки:
(0,0), \quad \left(\frac{m-1}{n}, y_1'\right), \quad \left(\frac{m}{n}, y_2'\right)
где
y_1' = y_1^{(\text{после})} = \frac{4(m-1)}{4m+26}, \qquad y_2' = y_2^{(\text{после})} = \frac{4m+5}{4m+26}.
Теперь уже первый отрезок даёт ненулевую площадь: треугольник под отрезком между x=0 и x=\frac{m-1}{n}.
Треугольник от 0 до \frac{m-1}{n}, высота на правом конце y_1', площадь:
S_1^{(\text{после})} = \frac{1}{2} \cdot \frac{m-1}{n} \cdot y_1' = \frac{m-1}{2n} y_1'.
Первая трапеция между x=\frac{m-1}{n} и x=m/n, высоты y_1' и y_2', основание
\frac{m}{n} - \frac{m-1}{n} = \frac{1}{n}.
площадь:
S_2^{(\text{после})} = \frac{1}{2} \cdot \frac{1}{n} \cdot (y_1' + y_2') = \frac{y_1' + y_2'}{2n}.
Вторая трапеция между x=m/n и x=1, высоты y_2' и 1, основание
1 - \frac{m}{n} = \frac{1}{n}
площадь: S_3^{(\text{после})} = \frac{1}{2} \cdot \frac{1}{n} \cdot (y_2' + 1) = \frac{y_2' + 1}{2n}.
Таким образом,
A_{\text{после}} = S_1^{(\text{после})} + S_2^{(\text{после})} + S_3^{(\text{после})} = \frac{m-1}{2n} y_1' + \frac{y_1' + y_2'}{2n} + \frac{y_2' + 1}{2n}
или
A_{\text{после}} = \frac{1}{2n} \left( (m-1)y_1' + y_1' + y_2' + y_2' + 1 \right) = \frac{1}{2n} \left( m y_1' + 2y_2' + 1 \right)
Подставляем n=m+1, \quad y_1' = \frac{4(m-1)}{4m+26}, \qquad y_2' = \frac{4m+5}{4m+26} :
A_{\text{после}} = \frac{1}{2(m+1)} \left( m \cdot \frac{4(m-1)}{4m+26} + 2 \cdot \frac{4m+5}{4m+26} + 1 \right).
Вынесем общий знаменатель 4m+26 в скобке:
A_{\text{после}} = \frac{1}{2(m+1)} \left( \frac{4m(m-1)+2(4m+5)}{4m+26} +1 \right)
Считаем числитель:
4m(m-1)+2(4m+5) = 4m^2-4m+8m+10 = 4m^2+4m+10.
Тогда
A_{\text{после}} = \frac{1}{2(m+1)} \left( \frac{4m^2+4m+10}{4m+26} +1 \right) = \frac{1}{2(m+1)} \cdot \frac{4m^2+4m+10+(4m+26)}{4m+26}.
Числитель:
4m^2+4m+10+4m+26 = 4m^2+8m+36 = 4(m^2+2m+9).
Получаем
A_{\text{после}} = \frac{1}{2(m+1)} \cdot \frac{4(m^2+2m+9)}{4m+26} = \frac{2(m^2+2m+9)}{(m+1)(4m+26)}.
Заметим, что 4m+26 = 2(2m+13) :
A_{\text{после}} = \frac{m^2+2m+9}{(m+1)(2m+13)}
3. Неравенство площадей и максимальное m
Требуем, чтобы индекс Джини не увеличился:
A_{\text{после}} \ge A_{\text{до}}.
Подставляем найденные выражения:
\frac{m^2+2m+9}{(m+1)(2m+13)} \ge \frac{4m^2+5}{2(m+1)(4m+5)}.
Заметим, что (m+1)>0 для m\geq 1, поэтому можно сократить на (m+1).
Перенесём всё в одну сторону и приведём к общему знаменателю, но удобнее сразу перемножить ``крест-накрест'' (зная, что знаменатели положительны при m\geq 1 ):
2(m^2+2m+9)(4m+5) \ge (4m^2+5)(2m+13).
Раскроем скобки.
Слева:
(m^2+2m+9)(4m+5) = 4m^3+5m^2+8m^2+10m+36m+45 = 4m^3+13m^2+46m+45
Умножаем на 2 : \text{Левая часть} = 8m^3+26m^2+92m+90.
Справа: (4m^2+5)(2m+13) = 8m^3+52m^2+10m+65.
Неравенство превращается в
8m^3+26m^2+92m+90 \ge 8m^3+52m^2+10m+65.
Вычитаем правую часть:
0 \ge (8m^3+26m^2+92m+90) - (8m^3+52m^2+10m+65) = -26m^2+82m+25.
То есть
-26m^2+82m+25 \ge 0 \;\Longleftrightarrow\; 26m^2-82m-25 \le 0.
Решим квадратное неравенство.
Сначала корни уравнения
26m^2 - 82m - 25 = 0.
Дискриминант:
D = (-82)^2 - 4 \cdot 26 \cdot (-25) = 6724 + 2600 = 9324 = 36 \cdot 259.
значит \sqrt{D} = 6\sqrt{259}.
Тогда
m_{1,2} = \frac{82 \pm 6\sqrt{259}}{52} = \frac{41 \pm 3\sqrt{259}}{26}.
m_1 \approx -0{,}28, \qquad m_2 \approx 3{,}43.
Так как коэффициент при m_2 положителен, неравенство
26m^2 - 82m - 25 \le 0
выполняется между корнями: m_1 \le m \le m_2.
При m\geq 1 остаётся 1\leq m\leq 3,43...
то есть целые m : \quad m=1, \ 2, \ 3 .
Но нас интересует максимально возможное m, значит m_{max}=3.
Тогда максимальное количество людей в гильдии - 4.
4. Иллюстрация кривых Лоренца (пример для m=3 )
Ниже — пример кривых Лоренца до и после для случая m=3 (всего n=4 человека). Числа на рисунке не строго по масштабу, рисунок иллюстративный (синяя и красная кривая на среднем участке в действительности накладываются друг на друга).
На рисунке видно, что кривая L_{\text{после}} (красная) не лежит ниже L_{\text{до}} (синяя) при m=3, что соответствует условию A_{\text{после}} \ge A_{\text{до}} до для этого случая.
Ответ: 4.