это примерно как каша из топора
Пропорциональный делёж
Основная статья: Пропорциональное деление торта
Для n человек с аддитивными оценками всегда существует пропорциональное разрезание. Наиболее используемые протоколы:
- Процедура «последний уменьшивший», протокол, который может гарантировать, что n кусков будут связными (то есть никто из участников не получит два или более отдельных кусков). В частности, если торт является одномерным интервалом, каждый участник получит интервал. Протокол дискретен и может быть осуществлён по раундам. Он требует
действий.
- Процедура «Движущийся нож»[en] Дубинса — Спеньера является непрерывной по времени версии протокола «Последний уменьшающий»[9].
- Протокол Финка (известный также как последовательные пары или одиночный выбирающий) является дискретным протоколом, который может быть использован для разрезания в режиме онлайн — если известно пропорциональное разрезание для n − 1 партнёров, при вступлении нового партнёра в игру протокол модифицирует существующее разрезание так, что пришедший участник и уже находящиеся в дележе участники получают по 1/n. Недостатком протокола является то, что каждый партнёр получает большое число отдельных кусочков.
- Протокол Ивена — Паза[en], основанный на непрерывном делении пополам торта и группы агентов и требующий всего
действий. Это самый быстрый возможный детерминированный протокол для пропорционального дележа и самый быстрый возможный протокол для пропорционального дележа, при котором гарантируется, чтобы все куски были связными.
- Протокол Эдмондса — Пруса является рандомизированным протоколом, который требует всего O(n) действий, но гарантирует только частично пропорциональное разрезание (каждый участник получает по меньшей мере 1/an, где a — некоторая константа), и может дать каждому участнику набор «крошек» вместо связного куска.
- Протокол дележа земли Бека может дать пропорциональный делёж спорной территории среди нескольких соседствующих стран. При этом каждая страна получает долю, которая и связна, и граничит с текущей территорией страны.
- Протокол суперпропорционального дележа Вудала даёт делёж, при котором каждый участник получает строго больше 1/n, если задано, что по меньшей мере два участника имеют разное мнение о ценности по меньшей мере одного куска.
Ну, если каждый по разу, каждому по 2 кусочка от каждого яблока.
Ну це ж вірна відповідь ? Хіба ні ?
В условии задачи сказано, что ножем можно воспользоваться один раз, но ничего не сказано как?
Воткнуть нож в стол (ну или в девочку, как тут предлагали) и уже потом резать о торчащий нож яблоки, например каждое на 4 части.потом уже делить поровну
На 4 вдоль яблока и еще каждый на 4 поперек - тогда им точно понравится)
это заморочка? вот разобраться в доказательстве Перельмана - во где заморочка
Ну тогда 16 на 3 получится) Ну хер с ним, по 5 кусочков, а лишний делителю в рот за работу
один берет нож, мочит любого из оставшихся двоих - одним ударом, насмерть. Двое живых берут по яблоку
Про яблоки - это как-то очень уж просто. Есть задачи и посложнее
А еще бывает и "завистливый дележ"!
А критерием справедливости служит отсутствие зависти в получившемся распределении — каждый агент должен получить набор объектов, ценность которых (как он считает) не меньше долей, полученных другими агентами. Поскольку объекты дальше неделимы, по условиям задачи, Envy-free распределения может не существовать.
