2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Справедливый делёж
Сообщение08.06.2006, 13:04 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 13:19 
Заслуженный участник
Аватара пользователя


09/10/05
1142
Обозначим добычу $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$. Но не выполняется

 Профиль  
                  
 
 
Сообщение08.06.2006, 21:26 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 21:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 22:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 22:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:05 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:10 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:14 
Заслуженный участник
Аватара пользователя


09/10/05
1142
PAV писал(а):
А знает, что он получил не менее $\frac 1 n$ от всей добычи.


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:19 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Capella писал(а):
Дело в том, что А может думать - у В осталась наименьшая и вообще очень маленькая часть, но откуда А уверен, что его часть тоже дотягивает до $ \frac 1 n$?

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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:21 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:21 
Заслуженный участник
Аватара пользователя


01/03/06
13122
Москва
Capella писал(а):

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

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

 Профиль  
                  
 
 
Сообщение08.06.2006, 23:30 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение09.06.2006, 01:21 


09/11/05
40
Лет пять назад я слушал доклад про эту задачу. Кажется, для 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).

 Профиль  
                  
 
 
Сообщение09.06.2006, 16:52 
Заслуженный участник


09/02/06
4342
Москва
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 групп так, чтобы каждый считал, что сумма стоимости любой из этих групп не больше суммы стоимости бесконечно делимого товара.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group