Разбойники не поделили добычу и умерли)

Ian · Сообщение **Ian** » 30 авг 2014, 17:13

Три разбойника захватили добычу, бесконечно делимую (например, золотой песок), и у каждого есть свои представления о сравнительной ценности двух кучек (не где больше песка смотрят, а где, им кажется, больше блеска). Как им поделить, чтобы каждый считал, что у него не меньше доля, чем у каждого из остальных?
Решение, где каждый считает, что получил не менее 1/3 добычи -уже лет 100 ходит и по школьным мат. кружкам и вот по таким: http://dxdy.ru/topic2975.html
Но разбойники еще и завистливые, любой из них, посчитав, что у другого больше, непременно его попытается убить. А третьему это не понравится.
Кто хочет именно нагуглить а не придумать, инглиш в помощь. На русском я не видел правильных решений в сети. И кстати, Брамс и Тейлор и после 1996 года кое- что писали)

Ian · Сообщение **Ian** » 06 сен 2014, 17:39

Неделя прошла. Грустно девушки (с)12
Грусть не относится к двум участникам, которые и так знали решение.
Вот такой способ

ivashenko · Сообщение **ivashenko** » 27 окт 2014, 20:01

Пусть разбойник А разделил добычу на 3 примерно равные части, а разбойник B выберет себе любую из 3х частей, затем разбойник С выберет из 2х оставшихся. Затем все три части кладутся на стол, на места А,В, С ссоответственно. Разбойник В делит каждую из частей ещё раз примерно на 3 равные части. Разбойник С выбирает из части В и из части А, понравившуюся ему часть и кладет её рядом со своей частью, Разбойник А также выбирает из частей В и С по части и кладет рядом со своей частью. Разбойник В забирает оставшиеся две части у А и С. В итоге у каждого из разбойников оказывается по 3 примерно одинаковые части. После чего разбойник С делит каждую из 9- ти частей на 3 примерно равные части. Разбойник А выбирает по одной из 9- ти частей разбойников В и С и кладет её рядом со своей, затем разбойник В выбирает по одной из 9-ти частей А и С и также кладет рядом со своей добычей, после чего С выбирает по одной из 9- ти частей каждого из разбойников А и В. Такой цикл повторяется, пока все три части не окажутся лежащими рядом с добычей разбойников. После чего разбойник А делит каждую из 27 частей каждого из разбойников на 3 примерно равные части и начиная с разбойника В каждый выбирает себе по 2 части из добычи оппонентов и кладет рядом со своей добычей, процесс продолжается, пока вся добыча не перейдёт в кучи, лежащие рядом. Затем следующий разбойник каждую из 81 части делит на 3 примерно равные части и начиная со следующего, происходит по кругу выбор из частей оппонентов и откладывание выбранных частей в кучи рядом с добычей. Процесс длится бесконечно и в пределе у каждого из разбойников окажется ровно по трети добычи. Чтобы ускорить процесс и исключить возможность какого- либо из разбойников халтурить, деление на 3 части в каждом цикле можно также как и выбор из 3х частей производить по кругу, а не одним разбойником.

Ian · Сообщение **Ian** » 27 окт 2014, 21:45

Любопытно.Но не учтен такой момент. Если у С, по мнению его самого, собралось 40% ценностей, но у В 45% а у А 15% (это все по мнению С) -С все равно будет недоволен, так как завидует В.
В частном случае, если В и С одинаково оценивают каждую песчинку, процесс должен обеспечивать дележ точно пополам, в пределе. Но У Вас в алгоритме как угодно далеко имеются этапы, когда дележ производит А, по совершенно несовпадающим с остальными критериям он может случайно сделать части сильно неравными с точки зрения В и С. И потом С выбирает каждый раз позже В, это, возможно,по окончании этапа приведет к неравенству в пользу В, величина которого не меньше некоторой фиксированной до начала дележа величины.Тогда по критерию Коши размеры долей у В и С(измеренные ими) не являются сближающимися. Может это и можно модифицировать, но Вам как автору надо еще и доказать, что цель будет достигнута...

ivashenko · Сообщение **ivashenko** » 27 окт 2014, 22:18

Какими бы неравными не делались части, в пределе, при бесконечном делении у всех окажется поровну. Т.е. чтоб разбойники не убили друг друга, они должны делить добычу бесконечно и видеть, что результат деления стремится к одной трети

ivashenko · Сообщение **ivashenko** » 27 окт 2014, 22:21

Если деление не окончено, то разбойники не могут завидовать друг другу и соответственно убить друг друга.

Dredd · Сообщение **Dredd** » 28 окт 2014, 05:07

Один делит добычу- второй выбирает. Это золотое правило наркомана. Поскольку разбойники завистливые и жадные, то тот, кто делит, будет делить добычу до тех пор, пока не будет уверен в том, что кучки одинаковые. Ну а тот, кто выбирает- выберет кучку, которая ему покажется не меньшей. В задачке три разбойника правда, а не два

Ian · Сообщение **Ian** » 28 окт 2014, 06:23

Бесконечные дискретные процессы здесь можно использовать, но например так: в 1ю секунду выполняется 1й шаг, в следующие полсекунды второй, в следующую четверть секунды третий...И вот объявляется что через две секунды все поделено поровну (если сам процесс был задуман сходящимся к чему надо)
Одна из тестовых ситуаций для проверки. Золотой песок блестит по-разному с разных сторон, так вот добыча составляет 2N песчинок : N с уровнем блеска 2 для А и 1 для В и С, и N с уровнем блеска 1 для А, 2 для В и С. Считать процесс сходящимся, если разница долей В и С стремится даже не к 0, а к o(N). И здесь при проверке иметь в виду, что разбойник А не имеет понятия о ценности для В и С, иначе ему было бы выгодно соблюсти и их интересы. Но бесконечное число раз включается в раздел поровну. Если мы предположим, что он нечаянно делит максимально неравноценно для В и С, размер колебаний долей не будет стремиться к 0.
Спасибо что интересуетесь)

ARRY · Сообщение **ARRY** » 28 окт 2014, 06:53

Доброе утро. Хочу внести свои 5 коп.
Сначала - уточнение. Скажите, Ian, разбойники должны обязательно видеть перед собой равные кучки, чтобы сравнить их относительную ценность, или же они способны оценить величину трети от общей кучи?
Если так, то, как мне кажется, решение упрощается. Один из них отсыпает из общей кучи небольшую кучку рядом. как только она приблизится к 1/3, любой из разбойников (в том числе и раздающий) может крикнуть: "Хватит!" Он не может оттянуть этот момент в надежде хапнуть более трети, т. к. кто-то другой крикнет раньше него и хапнет (по представлению первого) таки действительно больше трети. Поэтому крикнувший забирает свою долю и уходит. А делёжка на двоих тривиальна - один делит, второй выбирает.
Что не так?

ivashenko · Сообщение **ivashenko** » 28 окт 2014, 07:22

ARRY писал(а):Source of the post Доброе утро. Хочу внести свои 5 коп.
Сначала - уточнение. Скажите, Ian, разбойники должны обязательно видеть перед собой равные кучки, чтобы сравнить их относительную ценность, или же они способны оценить величину трети от общей кучи?
Если так, то, как мне кажется, решение упрощается. Один из них отсыпает из общей кучи небольшую кучку рядом. как только она приблизится к 1/3, любой из разбойников (в том числе и раздающий) может крикнуть: "Хватит!" Он не может оттянуть этот момент в надежде хапнуть более трети, т. к. кто-то другой крикнет раньше него и хапнет (по представлению первого) таки действительно больше трети. Поэтому крикнувший забирает свою долю и уходит. А делёжка на двоих тривиальна - один делит, второй выбирает.
Что не так?

На мой взгляд есть несколько засад:
1. Сложно сравнить кучи размером в 1/3 и 2/3, может оказаться, что в первой кучке, после раздела второй пополам окажется больше и обделенные разбойники убьют своего собрата.
2. Хотя добыча и может делиться непрерывно, но произнесение слова хватит не мгновенно. Поэтому от начала произнесения до прекращения "насыпания" может насыпаться больше и разбойники убьют своего товарища, а если же окажется, что насыпалось меньше, то он убьет того кто сыпал, мотивировав тем, что он после того как услышал букву х, стал сыпать медленнее.

yourdomain.com