Поделить на троих

[ny_quant]

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

Несмотря на то, что был сильно подшофе (или, возможно, благодаря этому), задачу я (как мне кажется) решил примерно за минуту, но он решения не понял и не принял, поэтому я ему сегодня его прислал снова в письменном виде.

Пафос не в самой задаче, хотя желающие поразвлечься are welcome. Я свое решение положу в комментарий ниже. Чур не подглядывать.

Пафос в том, что он продолжает упорно утверждать, что моё решение неверно - уже штук 7 имэйлов прислал с различными возражениями, которые мягко говоря не по делу. Чувак при этом математик по образованию, формально мой коллега по профессии, занимается на работе нетривиальными вещами - и вот на тебе.

UPDATE. Оказалось, мы по разному понимали условия задачи. Я понял так: организовать процесс дележки таким образом, чтобы каждый получил то, что ему кажется не менее, чем 1/3 сокровища вне зависимости от очередности. С его точки зрения (моими словами): чтоб каждому казалось, что никто не получил больше, чем он.

Comments

[ny-quant.livejournal.com]

Я не вижу чем это лучше. Выбывший после первого круга участник может с грустью наблюдать как кто-то другой получит (с его точки зрения) больше чем он и тоже ничего не сможет сделать.

[spamsink]

Традиционно формулируется так, что выбывший участник больше за процессом не наблюдает. Так или иначе, есть разница между уже имеющимся обладанием долей не менее чем 1/N и "наблюдением с грустью", и форсированием выбора меньшей из двух имеющихся долей, каждая из которой еще никому не принадлежит.

[ny-quant.livejournal.com]

Все равно не вижу существенной разницы. В моём варианте, П1 тоже может не наблюдать за процессом перехода массы из А в В. Он лишь выражает на первом этапе согласие принять любую из трех частей (как минимум), что и происходит. Форсированного выбора нет - П1 получает то, что осталось от разборок между П2 и П3, в соответствии с договором.

Не очень понятно почему выбывший пират в традиционной формулировке такая лапочка что соглашается взять свою долю и уйти, тогда как в моём варианте должен быть такой нечестный мерзавец, что сначала договорился, а потом пошел на попятную.

[spamsink]

Формально: на каждом этапе процесса есть набор еще не назначенных долей, и каждый агент предпочитает ту из долей, которую он считает максимальной, т.е. претензия не из предметной области, пираты там или старушки, и кто кому в каком случае навешает люлей, а чисто операционная: в момент назначения конкретной доли конкретному агенту не должно быть никакой доли, которую он бы предпочитал назначаемой.

[ny-quant.livejournal.com]

> в момент назначения конкретной доли конкретному агенту не должно быть никакой доли, которую он бы предпочитал назначаемой

Это (несколько искуственное на мой взгляд) дополнительное условие, которое заранее не оговаривалось. Я своё понимание постановки сформулировал в update.

Действительно, этому условию моё решение не удовлетворяет.

[spamsink]

А какое решение предлагает коллега?

[ny-quant.livejournal.com]

(сохраняя его spelling)

1. Один пират делит кучу на две части, как он думает справидливо.
2. Второй пират выбирает ту часть, которую он считает лудшей.
3. После этого, каждый из них делит полученную часть на 3 равные с их точки зрения доли.
4. Третий пират выбирает одну долю от первых двух, какие он считает лудшими.

Вашему условию оно тоже не удовлетворяет. Более того, оно не удовлетворяет и его собственному.

[spamsink]

Да, введение параллельности всё убивает, потому что может возникнуть кросс-зависть.

[ny-quant.livejournal.com]

Он делает вид, что не понимает. Или правда не понимает.

[xaxam.livejournal.com]

Такое решение индуктивно проще.

Если я отделил часть, которая с моей точки зрения в точности равна 1/N, то я соглашаюсь на обе опции: (1) взять себе эту часть без обиды, и наплевать на остаток торгов, (2) отдать эту (или тем более меньшую) часть кому угодно, вычеркнуть дурака из игры и продолжать участие в торгах.

В любом случае задача сводится к меньшему числу участников, что позволяет.