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

[ny_quant]

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

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

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

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

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

Comments

[ny-quant.livejournal.com]

I. Первый пират (П1) делит на три части (A, B and C) и согласен взять любую.

II. Второй пират (П2)

a. Выстраивает их в порядке своих предпочтений, скажем A>=B>=C.
b. Имеет право переложить кусочек из A в B так чтобы они в его глазах были равноценными. Обозначаем новые доли как A' and B' и П2 согласен на любую из этих двух.

Поскольку A'<=A and B'>=B, П1 в этот момент согласен взять или С или B'.

III. Третий пират (П3) может выбрать свою долю.

а. П3 выбирает A': Тогда П2 получает B', П1 получает C.
b. П3 выбирает B': Тогда П2 получает A', П1 получает C.
c. П3 выбирает C: Тогда П2 получает A', П1 получает B'.

[spamsink]

Поскольку A'<=A and B'>=B, П1 в этот момент согласен взять или С или B'.

Тут ошибка. Это же пираты, поэтому у П1 в этот момент возникает очевидное предпочтение B', и на C он больше не согласен.

[ny-quant.livejournal.com]

См. update.

Вообще-то можно пиратов заменить на интеллигентных старушек.

[spamsink]

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

[sthinks.livejournal.com]

Предлагаю заменить на Карлсонов и Малышей.

[ny-quant.livejournal.com]

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

Самый простой ответ на возражение П1, что он больше не согласен - П2 и П3 отвешивают ему дюлей и говорят, что если он еще раз свою поганую пасть раскроет, то они у него и С отберут ;)

[spamsink]

Стандартное решение при N участниках такое: первый отделяет то, что кажется ему 1/N. Если второму...энному кажется, что получилось не 1/N, а больше, то он может вернуть часть обратно. После того, как все имели возможность оценить и поправить, результат забирает тот, кто последним к нему прикасался, и выбывает из дальнейшего процесса. N := N-1; процесс повторяется.

[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) отдать эту (или тем более меньшую) часть кому угодно, вычеркнуть дурака из игры и продолжать участие в торгах.

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

[iz-chicago.livejournal.com]

Dirac, while still a student, attended a mathematical congress where the following problem was proposed:

Three fisherman were fishing on a secluded island. The fish briskly gobbled the bait; the fisherman were so absorbed that they did not notice that night had come and did not realize till too late what a mountain of fish they had hooked. So they had to spend the night on the island. Two fisherman quickly fell asleep, each nestled down under his boat, but the third had insomnia and decided to go home. He did not wake his comrades, but divided all the fish into three parts. There proved to be one extra fish. After a moment's thought, he threw it into the water, took his hare, and went home.

In the middle of the night, the second fisherman woke up. He did not know that the first fisherman had already left and also divided all the fish into three and, as before, there was one fish left over. As before, the fisherman threw the extra fish in the water, took his share, and went home.

By early morning, the third fisherman awoke. He did not notice that the other two fisherman had left, so he too divided all the fish into three and, as before, there was one fish left over. As did his comrades before him, the fisherman threw the extra fish in the water, took his share, and went home.

The problem was to determine the least number of fish that the fisherman could have caught. Dirac thought about the problem for a moment before coming to an answer: there were (-2) fishes.

His reasoning? After the first fisherman carried out the antisocial action of throwing a fish into the water there were -2-1 = -3 fish. The he went, carrying in his bag -1 fish, and there were -3-(-1) = -2 fish left behind. The other two fisherman merely repeated this procedure.

[ Related by V. Berezinsky in his article "How a theoretical physicist works," from Paths into the Unknown No. 2, 1968. ]

...Да в ней намёк...

[xaxam.livejournal.com]

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

Пусть x - число рыб. Тогда задача сводится к тому, чтобы найти целые y,z,w так, чтобы x=3y+1, 2y=3z+1, 2z=3w+1. Это - система линейных неоднородных уравнений, проблема - добиться целочисленности и неотрицательности. Как и в случае "обычных" систем, любое решение неоднородной системы получается из частного решения и любого решения однородной системы x=3y, 2y=3z, 2z=3w. Решения однородной системы легко описать: z=3/2 w, y=9/4 w, x=27/4 w. Чтобы оно было целочисленным, надо, чтобы w делилось на 4, и тогда получаем минимальное положительное решение x=27. Складывая с частным "решением Дирака", получаем x=25, и получаем минимальное "настоящее" решение.

[d-white1967.livejournal.com]

Любите вы, математики, всё усложнять. А всё просто - достать пистоль и выстрелить в одного из двух пиратов. Если попал, задача сводится к честной делёжке пополам, то есть к уже решённой. Если не попал - тоже, просто вас это уже волновать не будет :)

[messala.livejournal.com]

Делится на три кучки, один отворачивается, второй тычет пальцем в кучи в произвольном порядке, спрашивая: Это кому? - Джону. - А это? - Мне. Третий вопрос можно не задавать.

[xaxam.livejournal.com]

>>> С его точки зрения (моими словами): чтоб каждому казалось, что никто не получил больше, чем он.

Кажется, такое иногда бывает невозможно.

Соображения размерности: предположим, что есть n пиратов, и они делят между собой 1 кг товара двух типов, при этом каждый из пиратов имеет собственное представление о цене каждого из этих товаров, - p_1, ..., p_n и q_1, ... q_n. Дележка, когда i-ому пирату достаётся пакет (x_i, y_i), будет "справедливой" в альтернативном смысле, если p_i x_i+q_i y_i >= p_j x_j + q_j y_j при всех j \= i. Это система линейных неравенств в количестве n(n-1), наложенных на 2(n-1) переменных (сумма иксов, равно как сумма игреков, равна 1). Такая система в общем случае будет переопределённой при n>2, и нет никаких причин, почему она должна была бы иметь решение при любом выборе параметров p_i,q_i.

[ny-quant.livejournal.com]

Т.е. не иногда, а скорее никогда при n>2.

[xaxam.livejournal.com]

Нет: это всё-таки не равенства, а неравенства. Выпуклый многогранник в эн-мерном пространстве задаётся более чем эн неравенствами, если он ограничен (пересечение полупространств, отрезающих "лишнее").

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

Сказанное - не доказательство ни разу, но неплохая эвристика. Наверное, можно довести до аккуратного доказательства, но лень... очевидно же, что в общем случае "альтернативного" решения нет ;-)