Форум умных людей

Два программиста пошли обедать в суши-бар и заказали набор из 12 суши 4 видов (по 3 суши каждого вида). Естественно, встал вопрос: как их делить? Было решено, что каждому достанется по 6 суши - осталось выяснить, каких конкретно. Каждый из программистов в различной степени ценит различные виды суши: он может, например, любить суши первого вида, относиться равнодушно к суши второго и третьего, и люто, бешено ненавидеть суши четвёртого вида.

К ним подошёл официант. За небольшую прибавку к чаевым он предложил разрешить их проблему следующим образом: каждый из программистов пишет на листочке, какие 6 суши он бы выбрал, если бы всё зависело только от него, затем официант проанализирует эти данные и на их (и только их) основании предложит компромиссное решение, которое устроит обоих.

Стоит ли программистам доверять официанту?

оба любят суши №1, №2 и №3 и ненавидят №4
что должен ответить официант?

В идеале - что-то вроде (2,2,1,1) (1,1,2,2)
кто-то из программистов неизбежно получит лишнюю "ненавистную" сушку - соответственно, такое решение можно считать компромиссным

Ит депендс.

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

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

ЕСЛИ ЖЕ заказ "суши" был контролируем и логичен, то

"все равно",
ведь каждый заказал по 6 ролов. Логично предположить, что кадый заказывал только те, которые любит и не заказывал равнодушные и ненавистные ролы.
Отсюда логично, что ровно 2 вида по 3 рола заказал первый и ровно 2 ДРУГИХ вида по 3 рола - второй программер. А значит, будет их делить официант или сами - не имеет никакой разницы - разделение будет четким и легким...
Но зачем тогда платить больше?

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

Ок, смотрим мой первый вариант

сомневаюсь, что это устроит обоих
меня бы не устроило :)

дайте определение, какие решения считаются устраивающими обоих, а какие - нет

Anatol.
Хорошо, разбор по пунктам:
"Нет"
1) Почему нет, если решение официанта будет оптимально?
2) Почему нет, если решение официанта будет оптимально?
3) Откуда очевидно, что решение официанта не будет оптимально?
"Да"
Стороннее решение хорошо, лишь если оно будет оптимально.

iPhonograph, пожалуйста. Каждому виду суши (1<=i<=4) присваиваются величины у_1,i и у_2,i, символизирующие удовольствие, получаемое первым или вторым программистом соответственно от съедания одной такой сушки. Оптимальным решением называется то, которое максимизирует суммарное удовольствие двух программистов от поедания набора. Вру, надо подумать.

Скорее так: оптимальное решение минимизирует по модулю разницу удовольствий.

а в чём тогда задача?
вы своим определением только что дали алгоритм поиска решения
если программисты не хотят выполнять перебор вариантов сами, пусть платят официанту :)

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

удастся это ему или нет - вот в чём вопрос

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

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

Я же описал принцип. Конкретного решения (например с вероятностями) тут добиться наверное можно, но только путем длительных вычислений и подстановок.

А раз задача в разделе "Логических", то предлагаю логический принцип решения.
Лишь немного разверну.

Мы имеем по условию задачи:
Т.е. варианты предпочтения как минимум троякие:
1) Люблю
2) Все равно
3) Ненавижу
Или же они еще более дискретизированы (например по шкале от -10 до +10)
Шкала в любом случае должна быть оцифрована, ибо по-другому мы не добьемся возможности сравнения степени "комплексного удовлетворения"
Удобнее для решения представить шкалу как-можно более дискретизированной. -10...+10 подойдет

В этом случае степень "комплексного удовольствия" считается как:
+10+10+6+3-8-8 = 13 (цифры - наугад и исключительно для примера)
У другого программера например получилась степень удовольствия 18.
Это значит, что у второго нужно отобрать "вкусных ролов" на сумму 2-3 "единицы удовольствия" и отдать их первому. В результате получим что-то вроде 15 приблизительно равно 16.
Т.е. мы добились приблизительной равности "удовольствия"

В случае с официантом все по-другому
Фактически предлагается то же самое, что и в первом варианте, но дискретизирование удовольствий очень грубое. Назвал ролл = +1. Не назвал = 0.
В результате после вычислений официанта каждый программер может получить "набор удовольствий" со значением о 0 до 6 с дискретизацией 1.

Чем это хуже?
В случае с официантом минимальное возможное удовольствие оценивается как 0. Максимальное - как 6. Степень дискретности: 1/6. Т.е. сравнить 2 набора "удовольствий" можно с точностью 1/6 "максимального удовольствия"

В случае недоверия официанту и использования шкалы -10...+10:
Минимум удовольствия = -60
Максимум удовольствия = +60
Дискретизация равна 1
Т.е. сравнить 2 набора удовольствий можно с точностью 1/120, что явно точнее, чем 1/6 официанта.

Даже если берем шкалу "люблю-все равно-ненавижу", оцифруем в виде -1...0...1, то имеем
Минимум = -6
Максимум = +6
Степень точности: 1/12, что тоже круче чем 1/6 официанта
Показать скрытый текст

В общем, поскольку я не знаю, как строго выразить оптимальность, изложу авторское решение (которое, в общем-то, строгой формализации не требует).

Пусть первый программист любит суши видов 1, 2, 3 и ненавидит суши вида 4.
Второй любит 1, 2, 4 и ненавидит 3.

Монопольные выборы могут быть такими: (3, 3, 0, 0), (3, 3, 0, 0).

Соответственно, официант, знающий лишь монопольные выборы, не имеет никакой информации, позволяющей ему прийти к оптимальному решению: (3, 0, 3, 0), (0, 3, 0, 3). Следовательно, он шарлатан, и надо его отмудохать)

У меня все красивее )