Справедливый делёж

[Руст]

n разбойников делят добычу. Среди добычи есть достаточное количество бесконечно делимого товара.
1. Показать, что они могут разделить добычу так, чтобы каждый считал, что ему досталось не меньше 1/n -ой части общей добычи.
2. При каких условиях можно разделить так, чтобы каждый считал, что его доля максимальная (т.е. не меньше, чем у кого либо другого)?

[Capella]

Обозначим добычу $x$. Допустим, что минимальная доля каждого разбойника $\frac x n$. Тогда добычу можно обозначить вот так: $ n \cdot \frac x n + r$, где $r$ переизбыток миниальной доли (остаточный член). Составляем уравнение и показываем, что оно выполняется при $r = 0$
Более полное уравнение: $x - \frac 1 n = (n-1) \frac {x - {\frac 1 n}} {n-1} + r$ . Должно выполняться для любого $n$ при $r \ne 0$. Но не выполняется

[Brukvalub]

Не поленюсь выписать достаточно известный (обычно еще со времени пребывания в школьных кружках по математике) алгоритм решения:
1)Если разбойников двое, то один делит добычу на две равные с его точки зрения части, а другой выбирает из них ту долю, которая кажется ему большей.Предположим теперь, что n разбойников уже умеют разделить добычу справедливо. Для n+1 разбойников: разделим справедливо всю добычу между n разбойниками (это они уже умеют) и затем пусть каждый из них разделит свою долю на n+1 равных ,на его взгляд, частей. Пусть теперь n+1-й разбойник выберет на свой вкус по одной из этих частей у каждого из n разбойников. Нетрудно понять, что все получилось.
2)Непонятно, как доказать необходимость каких-либо условий в ответе на второй вопрос - ведь это автоматически приведет к задаче алгоритмической неразрешимости, а такие задачи чаще всего очень трудны...

[незваный гость]

У нас есть три разбойника. $A$ разделил свою долю на $a1$, $a2$, и $a3$. $B$ -- на $b1$, $b2$, $b3$. $C$ выбрал $a3+b1$. Почему $A$ считает, что у $C$ не больше, чем у него?

[Brukvalub]

Продолжаю:
Третий разбойник уверен, что взял не менее, чем по одной третьей доле у каждого из первых двух разбойников, т.е. всего он получил не менее трети от всей добычи. Каждый из первых двух разбойников также получил, на его взгляд, не менее, чем половину от двух третьих, то есть не менее трети от всей добычи. Заменой цифры 2 на символ n и цифры три на символ n+1 разъясняется общий случай.

[незваный гость]

Почему доволен $C$ (третий), нет вопросов. Вопрос, почему доволен $A$ (первый)? Части $b1 \sim b2 \sim b3$ только с точки зрения $B$. С точки зрения $A$, может быть $b1 \gg b2 \sim b3$. Настолько, что $C$ получил больше чем он ($a3 \sim a1$, но вот $b1 \gg a2$)

[PAV]

$A$ знает, что он получил не менее $1/n$ от всей добычи. При данном способе он не может быть уверен, что его доля не меньше, чем у любого другого. Но он знает, что если у кого-то больше, чем у него, то это не за счет его части, а за счет чужих частей. Может, $B$ глуп и разделил свою долю не поровну, и $C$ этим воспользовался, либо наоборот, $C$ глуп и взял не самую выгодную часть.

[незваный гость]

Согласен. Я, как часто, увы, со мной бывает, невнимательно читал условие . Действительно, требуется не меньше $1/n$, а не не меньше остальных.

[Capella]

PAV писал(а):

А знает, что он получил не менее $\frac 1 n$ от всей добычи.

Это не верный аргумент. Дело в том, что А может думать - у В осталась наименьшая и вообще очень маленькая часть, но откуда А уверен, что его часть тоже дотягивает до $ \frac 1 n$? Ведь В мог так поделить добычу, что С мог забрать, например 90% его части.

[незваный гость]

Capella писал(а):

Дело в том, что А может думать - у В осталась наименьшая и вообще очень маленькая часть, но откуда А уверен, что его часть тоже дотягивает до $ \frac 1 n$?

Когда делили на $n-1$ частей, $A$ был уверен, что у него не меньше $1/(n-1)$. Теперь он сам поделил свою долю на равные с его собственной точки зрения части. Поэтому у него осталось $\frac{n-1}{n} \, (1/(n-1)) = 1/n$.

[PAV]

На первом этапе добычу делят $A$ и $B$. Дележ устроен так, что каждый считает, что у него половина добычи. После этого $A$ делит свою долю на 3 равные части. В его интересах разделить поровну, так как $C$ может забрать любую из его частей. Таким образом, у него остается $1/3$. Как далее между собой разберутся $B$ и $C$, его уже не волнует.

[Brukvalub]

Capella писал(а):

откуда А уверен, что его часть тоже дотягивает до $ \frac 1 n$? Ведь В мог так поделить добычу, что С мог забрать, например 90% его части.

Все это касается второго из поставленных Рустом вопросов. Я нигде не утверждал, что отвечаю на второй вопрос, более того, в своем первом посте по данной теме Я выразил сомнение в самой возможности такого ответа.

[Capella]

Да, ясно, я просто почему-то решила, что они все 3 обмениваются по одной части.

[sonte]

Лет пять назад я слушал доклад про эту задачу. Кажется, для n<7 известно всё, а для больших оставались какие-то открытые вопросы.
Есть даже целая книга: S. Brams, A. Taylor. Fair Division : From Cake-Cutting to Dispute Resolution. (1996)
Да и гугл много чего выдаёт по запросу Cake Cutting (например, статью с забавным названием Cutting a Pie Is Not a Piece of Cake).

[Руст]

sonte писал(а):

Лет пять назад я слушал доклад про эту задачу. Кажется, для n<7 известно всё, а для больших оставались какие-то открытые вопросы.
Есть даже целая книга: S. Brams, A. Taylor. Fair Division : From Cake-Cutting to Dispute Resolution. (1996)
Да и гугл много чего выдаёт по запросу Cake Cutting (например, статью с забавным названием Cutting a Pie Is Not a Piece of Cake).

На самом деле при достаточности делимого товара вопрос справедливого дележа в более сильной постановке 2 решается для любого n. Необходимым и достаточным условием для этого является то, чтобы существовало возможность сгруппирования неделимых товаров на n-1 групп так, чтобы каждый считал, что сумма стоимости любой из этих групп не больше суммы стоимости бесконечно делимого товара.