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

[ny_quant]

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

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

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

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

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

Comments

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

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

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

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