Али Баба и 40 разбойников
Всем привет! Да озарит вас летнее Петербургское солнце :)
Лытдыбр
У меня дачный отпуск, поэтому могу тряхнуть стариной и написать в ЖЖ, который вроде ещё не умер, хотя и пал под натиском ВКонтакта и прочих FB. О моей счастливой жизни в роли молодого кормящего отца знают все близкие, поэтому я решил написать не об этом, а о чём-то интересном. Т.е., о работе и логической задачке с ней связанной :)
Последний месяц я (от лица своей компании) бьюсь в неравной битве с ЦДС, пытаясь разделить квадратные метры ещё не построенных квартир. Занятие увлекательное, но бесячее, т.к. "коллеги" из ЦДС не умеют толком ни в Excel считать, ни в AutoCAD рисовать, а потому раза три уже, достигнув просветления в том, как разделить квартиры, приходилось начинать всё сызнова, ибо выяснялось, что делить надо было нечто другое. И вот по этому поводу я вспомнил прекрасную логическую задачу, которую и предлагаю вашему вниманию.
Один делит, другой выбирает
Задача о делении между двумя заинтересованными сторонами многим известна с детства. Когда нам с братом требовалось разделить на двоих последнюю конфету мы следовали простому правилу: один делит, другой выбирает. Алгоритм безупречный. Позволяет справедливо разделить что угодно.
Главное, он позволяет делить вещи и в том случае, когда для разных людей они имеют разную ценность. Например, делите вы кусок торта с вишенкой. Это вам уже не однородная конфета, которую достаточно поделить на равные части. Кому-то вишенка может представляться крайне желанной, а кому-то - нет. Если вы непременно хотите получить вишенку, то придётся делить торт не на равные части, а, например, на 2/3 без вишенки, и 1/3 с вишенкой - в том случае, если для вас вишенка ценна, как треть торта. Тогда либо второй человек позарится на больший кусок и вы получите свою вишенку, либо вишенка вам не достанется, но вы будете утешать себя тем, что съели по-больше тортика. Можно, конечно, сжульничать и сделать вид, что на вишенку вам плевать; разделить всё (почти) поровну и молиться, что другой человек выберет кусочек без вишенки, ибо не любит приторную сладость марципана. Но что хорошо, этим манёвром можно улучшить или ухудшить свою долю, но нельзя навредить другой стороне.
Итого, этот алгоритм позволяет двоим разделить добро "по-справедливости" в следующем смысле:
- Каждый получает не меньше 1/2 (в своей системе ценностей)
- Каждый получает не больше 1/2 (в системе ценностей оппонента)
- Попытка схитрить (делить не по своей системе ценностей) не вредит оппоненту (не нарушает для него верность предыдущих двух утверждений)
- Знание системы ценностей оппонента (любит от вишенку или нет), также не может ему навредить, в упомянутом выше смысле (хотя и может позволить вам гарантированно получить больше 1/2 в собственной системе ценностей)
Алгоритм предполагает, что объект деления не содержит чрезмерно дорогих "артефактов", не поддающихся делению. Понято, что если для обоих ценна только вишенка (ценность торта - нулевая), причем резать вишенку нельзя, то поделить торт к радости обоих не получится.
Математическое обобщение
Каждый математик меня поймёт: если можно решить задачу при n=2, то надо пытаться решать её и при n=k :) Отсюда вопрос: можно ли провести справедливое деление между тремя сторонами? Между произвольным числом заинтересованных сторон?
n=k. В принципе, у задачи есть занудное решение. Следует предположить, что делению подлежит конечное число объектов, каждому из которых участники дележа втайне друг от друга выставляют (в цифрах или процентах) стоимость в их собственной системе ценностей. Тогда задача справедливого деления может быть сформулирована как задача линейного программирования и рутинно решена симплекс-методом. Такой подход позволяет выявить важные закономерности и ответить на ряд вопросов, но он полностью лишён той элегантности, что присуща короткому алгоритму "один делит, другой выбирает".
В частности, выясняется, что второе условие справедливости нельзя достигнуть даже при делении на троих. Т.е. возможна ситуация: вас вроде водкой не обделили, но у одного из соседей явно больше... (а у другого - меньше, но никто вроде не возражает за свою долю). А ещё можно в строгом математическом смысле описать, что значит моя фраза "объект деления не содержит чрезмерно дорогих артефактов". Ну и так далее...
Помимо неэлегантности это решение имеет ещё один недостаток: его нельзя применить к пресловутому торту с вишенкой. Ведь торт может быть неоднороден (где-то крема больше, где-то меньше), но ценность полученного кусочка торта может не определяться ценностью входящих в него коржей, крема и вишенки (как водится, симплекс-метод выдаст нам решения, целиком состоящие из крема, но не содержащие ни грамма коржей - спасибо, сами такое ешьте). Важен некий баланс всех ингредиентов, что выпадает за рамки линейных ограничений; не говоря уже о тех сложностях, с которыми сопряжена попытка приписать числовые значения ценностей для этих ингредиентов.
По счастью, у этой задачи есть и логическое решение, которое можно сформулировать в терминах "делит - выбирает", не опускаясь до уровня "распишите на бумажке, во сколько рублей вы оцениваете вишенку..." И вот над этим-то решением я и предлагаю вам подумать :)
Али Баба и 40 разбойников
Сорок разбойников наворовали кучу сокровищ, но чуть не передрались, когда настал черёд их делить. На их счастье, мудрый Али Баба знал секрет справедливого дележа - и этим выкупил своё право покинуть пещеру живым. Он поведал разбойникам, как разделить сокровища так, чтобы каждый был уверен, что получил не меньше 1/40 всех сокровищ. (Хотя после дележа кто-то и ворчал, что Хасану, как всегда, больше других досталось...)
По счастью сокровища содержали кучу золотого песка, поэтому проблем с "особо ценными артефактами" при дележе не возникало. При этом Али Баба учёл, что разбойники на то и разбойники, что могут при дележе хитрить и лукавить - но это никак не умаляло долю для других разбойников.
Так как же Али Бабе это удалось?
Али Баба и 3 разбойника
Я предлагаю тем немногим любителям загадок, что ещё читают мой дневник, попытаться решить эту задачу, разделив сокровища в терминах "делит - выбирает". Вы будете присылать решения, а я их критиковать. :) И давайте для простоты сначала делить сокровища между тремя разбойниками. Для затравки приведу пример обычного неправильного решения:
"Один разбойник делит сокровища на 3 равные кучи. Двое других выбирают, какая часть им нравится. Чтобы они не выбрали, останется одна не востребованная часть - она и достаётся тому разбойнику, который произвёл изначальное деление. Оставшееся сокровища 2 разбойника могут поделить между собой обычным способом (а если они выбрали разные доли, то деление, считай уже совершилось). Алгоритм легко обобщается на произвольное число разбойников. Так для 40: один делит, другие выбирают что им нравится; одну из невостребованных частей забирает инициатор деления и задача сводится к дележу для 39 разбойников - и далее по индукции."
Ошибочность этого решения легко увидеть, даже в случае, когда у всех трёх разбойников одинаковая система ценностей. Допустим, хитрый первый разбойник разделил сокровища в пропорции 50%, 49% и 1%. Два других разбойника сказали, что хотят ту часть, где 50%. А смиренный первый разбойник берёт себе 49%, оставляя двум другим 51% на двоих. В результате кто-то из них (а вероятно оба), получат менее 1/3.
Т.к. лето и отпуска, то решения готов ждать аж две недели (потом и у меня кончится отпуск, и снова будет не до ЖЖ). Комментарии скрыты, чтобы не смущать общественность. Неверные решения, с согласия авторов, будут разобраны в комментариях и открыты.