Неравенство в гильдии
В компьютерной игре у Алекса есть несколько друзей в гильдии. В начале дня у одного из друзей было единиц ресурса "золото", а у остальных (включая Алекса) — . После совместного прохождения подземелья каждый из друзей Алекса получил бонус золота, но Алекс бонуса не получил из-за бага в системе. Чтобы исправить это, администратор сервера вручил Алексу некоторое количество золота. Будучи знатоком теории игр, администратор хотел, чтобы Алекс обрадовался (получил много золота), но чтобы неравенство распределения золота в гильдии не выросло. Он выдал Алексу золото, и индекс Джини распределения золота в гильдии не увеличился. Найдите максимальное количество человек в рассматриваемой гильдии.
Ответ
Индекс Джини можно выразить через площадь под кривой Лоренца:
.
Отсюда условие «неравенство не выросло» эквивалентно
Мы будем сравнивать площади под кривыми Лоренца до и после исправления бага, не используя формулу для .
Распределения "до" и "после"
Пусть у Алекса друзей. Тогда всего в гильдии человек.
До вмешательства администратора:
Сначала у одного друга было золота, остальные (включая Алекса) - по .
После подземелья каждый друг получил золота, Алекс ничего не получил.
Итого до выдачи золота Алексу: у одного друга: , у остальных друзей: по , у Алекса: .
Отсортированное распределение:
Общий доход:
.
Выделим три группы:
Группа : Алекс ( человек), доход .
Группа : остальные друзья с (их ), суммарный доход .
Группа : самый богатый друг с .
Доли населения:
Доли суммарного дохода:
.
Кривая Лоренца до выдачи проходит через точки
.
Это ломаная из трёх отрезков (см. иллюстрацию в конце).
После вмешательства администратора
Администратор выдал Алексу золото.
Тогда распределение становится:
так как теперь Алекс самый богатый.
Общий доход:
.
Группы:
Группа : человек с доходом , суммарный доход .
Группа : один человек с .
Группа : Алекс с .
Доли населения:
.
Суммарные доходы первых групп:
.
Соответствующие доли дохода:
.
Кривая Лоренца после выдачи проходит через точки
.
Опять получаем ломаную из трёх отрезков.
Площади под кривыми Лоренца: треугольник + две трапеции
Площадь до исправления бага:
Точки: ,
где .
Первый отрезок от до идёт по оси , высота нулевая, площадь равна .
Вторая фигура - трапеция между и , нижняя высота , верхняя - , основание: .
Площадь:
.
Третья фигура - трапеция между и , высоты и , основание
Площадь:
.
Таким образом, общая площадь:
.
Подставляем и :
.
Складываем первые два слагаемых:
Тогда
.
Числитель:
.
Таким образом,
Площадь после исправления бага:
Точки:
где
.
Теперь уже первый отрезок даёт ненулевую площадь: треугольник под отрезком между и .
Треугольник от до , высота на правом конце , площадь:
.
Первая трапеция между и , высоты и , основание
.
площадь:
.
Вторая трапеция между и , высоты и , основание
площадь: .
Таким образом,
или
Подставляем , :
.
Вынесем общий знаменатель в скобке:
Считаем числитель:
.
Тогда
.
Числитель:
.
Получаем
.
Заметим, что :
Неравенство площадей и максимальное
Требуем, чтобы индекс Джини не увеличился:
.
Подставляем найденные выражения:
.
Заметим, что для , поэтому можно сократить на .
Перенесём всё в одну сторону и приведём к общему знаменателю, но удобнее сразу перемножить ``крест-накрест'' (зная, что знаменатели положительны при ):
.
Раскроем скобки.
Слева:
Умножаем на : .
Справа: .
Неравенство превращается в
.
Вычитаем правую часть:
.
То есть
.
Решим квадратное неравенство.
Сначала корни уравнения
.
Дискриминант:
.
значит .
Тогда
.
.
Так как коэффициент при положителен, неравенство
выполняется между корнями:
При остаётся
то есть целые : .
Но нас интересует максимально возможное , значит .
Тогда максимальное количество людей в гильдии - .
Иллюстрация кривых Лоренца (пример для )
Ниже — пример кривых Лоренца до и после для случая (всего человека). Числа на рисунке не строго по масштабу, рисунок иллюстративный (синяя и красная кривая на среднем участке в действительности накладываются друг на друга).
На рисунке видно, что кривая (красная) не лежит ниже (синяя) при , что соответствует условию до для этого случая.
Ответ: