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

[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]

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

[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. ]

[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.