Али Баба и 40 разбойников - решение
Ну что, пора рассказать уже как же решается задача о делении - и так я задержался с ответом. К тому же на работе как раз закончилась эпопея справедливого (почти) деления квадратных метров :). И чтобы отблагодарить публику за затянувшееся ожидание, я поведаю вам сразу 3 решения: неправильное, простое и заумное.
Неправильное решение
Начнём все же с неправильного решения, которое подскажет нам то направление, в котором надо искать решение правильное. Алгоритм прост: один делит на 40 равных частей, остальные по очереди выбирают части, которые им нравятся из тех, что ещё никто не выбрал до них. В результате остаётся последняя часть, на которую никто не покусился - она-то и достаётся инициатору деления, т.к. явно никому не нужна, и никто не будет против отдать эту долю первому разбойнику. Остальные части смешиваются и делятся между оставшимися 39 разбойниками (разумеется, если текущий выбор кого-то не устраивает).
Между прочим, это решение является корректным, если у всех разбойников одинаковая система ценностей. Но если ценности разные, то алгоритм не сработает. Покажем это на контр-примере для 3 разбойников.
Разбойник №1 делит сокровища на три (пусть равные для него) части, которые мы обозначим A, B и C. Разбойник №2 оценивает их (в процентах) так: A=50, B=10, C=40; а разбойник №3 оценивает иначе: A=80, B=11, C=9. Согласно алгоритму сначала выбирает 2 разбойник: он выделяет себе часть A. Логично, думает 3 разбойник (он её тоже бы себе приметил), и из оставшихся частей выбирает часть B, которая на его взгляд всё-же получше. В результате часть C уходит разбойнику №1.
После чего начинается драка с мордобоем. Текущее деление не устраивает 3 разбойника (он застолбил часть ценой 11). А продолжить делить оставшееся части не готов 2 разбойник: на его взгляд в пуле осталось лишь 50+10=60% от изначальной доли, т.е. при честном делении ему достанется 30%, что меньше трети.
Чему нас учит этот пример с Кадавром? Тому что, главная идея - выделить часть, на которую не претендует никто, кроме делившего. Только надо быть уверенным, что она, действительно, никому не нравится. Вот, собственно, это и подводит нас к простому решению.
Простое решение
Это решение озвучил kosovsky_family в частной беседе. Всё гениальное просто. Первый разбойник выделят из груды то, что считает 1/40 частью. Оставшиеся по порядку либо соглашаются отдать эту часть ему, либо заявляют, что она несправедливо больше; в последнем случае они должны уменьшить эту часть сокровища так, как считают нужным, и с этого момента уже они являются претендентами на нее. Т.к. часть уменьшилась, то все ранее соглашавшиеся расстаться с этой частью разбойники не будут ущемлены. Ещё не выносившие суждения разбойники имеют те же возможности: либо отдать часть претенденту, либо взять инициативу на себя, уменьшить долю до справедливой 1/40 и стать новым претендентом на неё. После того как все разбойники выскажутся, последний деливший разбойник получает свою долю, с которой, согласно алгоритму, все согласны расстаться. Оставшаяся груда сокровищ теперь делится между 39 разбойниками аналогичным способом.
Решение простое и понятное. У него есть лишь один недостаток. Помните, рассказывая о задаче я говорил, что подход через линейное программирование позволяет строго сформулировать критерий "делимости" сокровищ? В постановке задачи я обошёл этот момент, сказав, что "пусть в сокровищах будет достаточно золотого песка, чтобы у разбойников не возникало проблем с делимостью". Так вот, в данном решении постоянные отрезания от 1/40 небольших долей, которые совершают перехватывающие претендентство разбойники, требуют от сокровищ гораздо более гибкой "делимости", чем то минимально необходимо. Таким образом, решение правильное, но накладывает более жёсткие ограничения на сокровища, чем требуется.
Например, допустим в случае трёх разбойников один из них выбрал себе 10 одинаковых изумрудов. По мнению другого разбойника это больше, чем 1/3, но 9 изумрудов - меньше 1/3, а потому он не может отрезать необходимую часть. Он мог бы выбрать долю в 9 изумрудов и немножко золотого песка, но это нарушит наш алгоритм: долю можно было только уменьшать; если в неё прибавить что-то из общей груды сокровищ, то уже нельзя будет говорить о согласии ранее высказавшихся разбойников передать эту "уменьшенную" долю новому претенденту. (Возникающие здесь коллизии иллюстрирует пример из неправильного решения.)
В то же время, более сложный механизм деления, который я опишу ниже, позволяет без проблем обойтись с этой долей в 10 изумрудов: её просто придётся поделить пополам (по счастью, 10 на 2 делится). Справедливости ради отметим, что в описанном примере всё же остаётся возможность для решения: надо позволить разбойнику сформировать долю в 9 изумрудов и горку песка, и заного начать опрашивать всех разбойников, согласны ли они с такой долей или нет. Когда очередь дойдёт до разбойника, оценивавшего долю в 10 изумрудов, тому придётся либо согласиться с ней, либо, допустим, убрать из доли немного песка.
Заумное решение
Решение для троих разбойников предложила nutsyrax, за что ей огромное спасибо, а то бы я скучал без комментариев к своей задаче. Ниже приводится обобщение, которое мы когда-то выработали совместно с женой tata2109.
Это решение более традиционно, в том плане, что сводится к механизму деления (всей груды) сокровищ и последующему выбору. Заметим, что механизм "один делит, другой выбирает" в классической задаче для двоих позволяет делить сокровища не только поровну, но и в любой оговорённой пропорции. Например, если двум людям надо поделить сокровища в отношении 2:3, то один делит его на 5 частей, а другой выбирает причитающиеся ему 2 (или 3) части из выделенных. Это важный момент: в той индукции, что мы будем строить, нам придётся уметь делить сокровища в неравных частях.
Для примера поделим сокровища между 5 разбойниками. Пусть первый разбойник разделил сокровища на 5 частей, обозначим их литерами от A до E:
Теперь каждому разбойнику дайют 4 бирки, которыми он может застолбить те выделенные части, которые ему понравились. Иными словами, каждый разбойник выбирает ту часть, которая ему не нравится. Пусть разбойникам №№ 2 и 3 не понравилась часть E, тогда они втыкают свои бирки так:
Разбойнику № 4 не понравилась часть A, и он добавляет свои бирки:
А разбойнику №5 не понравилась часть C:
Теперь, когда все разбойники расставили свои бирки, части, в которых оказалось менее 4 бирок, дополняются бирками 1-го разбойника:
Теперь для каждого разбойника бирками отмечены те части сокровищ, которые в сумме дают не менее 4/5 в системе ценностей этого разбойника. Поэтому если мы разделим каждую из пяти части между претендующими на неё четырьмя разбойниками, то сложив все доли каждый разбойник получит не менее 1/4*4/5 = 1/5. Что нам и требовалось.
Поэтому задача свелась к пятикратному делению на 4 части. С частями A-D всё ясно: они теперь по аналогии делятся между четырьмя разбойниками. Давайте проследим, что будет с частью E, которую надо поделить непропорционально.
Часть E надо разделить между тремя разбойниками (№4, №5 и №1), но в пропорции 1:1:2. Нет проблем: делим на 4 части, считая, что разбойник №1 имеет два "голоса". Для этого, кто-то делит эту долю на 4 части. В принципе, это может снова сделать первый разбойник. Пусть мы получили новые части, обозначенные F-I (простите, на этот раз без картинок). Разбойник №4 отверг часть H, разбойник №5 - часть I. Разбойнику №1 принадлежат два голоса, поэтому один раз он выбирает на правах со всеми, допустим, отвергая часть I. А потом оставшиеся места заполняются его бирками, т.к. он делал первое деление.
В нашем примере части имели бы следующие бирки: F ~ 4,5,1; G ~ 4,5,1; H ~ 5,1,1; I ~ 4,1,1. Отметим, что результат не зависит от того, в каком порядке разбойники указывают нелюбимые части. Первый разбойник мог поделить и тут же указать, какая часть ему не нравится, проставив бирки в остальные части. Это не помешает разбойникам №№ 4 и 5 проставить свои бирки, после чего свободные места будут заполнены бирками делившего долю разбойника №1. Если бы первое деление делал не он, а разбойник №4 или №5, то у разбойника №1 было бы два голоса, и он дважды отвергал бы какую-то часть (может быть одну и ту же, а может быть разные), и в два круга проставлял бы три свои бирки на неотвергнутые части.
Итак, задача сводится к делению на ещё меньшее количество частей. Части F и G делятся между тремя разбойниками поровну. Части H и I делятся в пропорции 1:2 между, соответственно, разбойниками №№ 5 и 1 в первом случае, и №№ 4 и 1 во втором. А такое деление между двумя разбойниками возможно, как мы указывали выше.
Алгоритм деления для 40 разбойников. Первый разбойник делит сокровища на 40 равных частей. После этого каждый разбойник указывают ту часть, которая ему ненравится; а на оставшиеся части можно повесить бирки с номером разбойника (39 бирок по числу оставшихся частей), мол, он на них претендует. Когда все 39 разбойников выскажутся, у нас на любой части может быть максимум 39 бирок разных разбойников. Но будут части, на которых бирок меньше - это те, которые кому-то не приглянулись. На эти части мы навешаем бирки с номером 1 (номером делившего разбойника) - причём можем навесить несколько таких бирок, доведя общее число бирок до 39. Несложно посчитать, что потратив 39 бирок с #1 мы заполним все 40 частей полным комплектом из 39 бирок. Теперь каждая из 40 частей делится между теми претендентами, чьи бирки на них указаны. Но теперь сокровища надо делить на 39 претендентов; а это уже проще :). Причём какие-то части будут делится не поровну между разбойниками (это те части, где было несколько бирок с номером 1). Всё. Задача сводится к непропорциональном делению на меньшее количество людей.
Поймём почему это деление всех устроит: каждый разбойник оставили свои бирки в 39 частях, которые в сумме составляют 39/40 от всех сокровищ или более (ведь та часть, что он отверг, была меньше либо равна 1/40). Если мы по индукции поделим выбранные разбойником части, и в каждой он получит не менее 1/39 части, то в сумме его доля составит не менее 39/40 * 1/39 = 1/40. Что и требовалось получить.
Вот. Всем дочитавшим до конца - спасибо за любознательность :)