Специалисты по информатике разработали алгоритм справедливого раздела пирога для любого количества людей
Двое молодых учёных, специалистов в области информатики, придумали, как честно поделить торт между любым количеством людей, решив задачу, над которой математики бились десятилетиями. Их работа удивила многих исследователей, считавших такое разделение невозможным в принципе.
Делёж пирога – это метафора для широкого круга реальных задач, включающих деление некоего непрерывного объекта, будь это торт или надел земли, между людьми, по-разному оценивающими его свойства. Одному нравится шоколадное покрытие, другой хочет получить кремовые цветочки. С библейских времён известен алгоритм деления такого объекта между двумя людьми, такой, чтобы никто не завидовал другому: один человек делит торт на две равные для него части, а другой выбирает одну из них. В Книге Бытия Авраам (тогда ещё известный, как Аврам) и Лот использовали этот метод для раздела земли, когда Авраам придумывал разделение, а Лот выбирал между Иорданом и Ханааном.
В 1960-х математики придумали алгоритм для подобного разделения пирога «без зависти» уже для трёх человек. Но до сих пор лучшим решением задачи для количества людей больше трёх была процедура, созданная в 1995 году политологом Стивеном Брамсом [Steven Brams] из Нью-Йоркского университета и математиком Аланом Тейлором [Alan Taylor] из Юнион-колледжа. Она гарантировала «справедливую» делёжку пирога, но с одним условием – процедура была «неограниченной», то есть число шагов, необходимое для делёжки, могло оказаться сколь угодно большим.
Алгоритм Брамса-Тейлора в своё время был назван прорывным, но «его неограниченность, по-моему, была большим недостатком», говорит Ариель Прокаччиа [Ariel Procaccia], специалист по информатике из Университета Карнеги-Меллон, один из создателей Spliddit, бесплатного онлайн-инструмента для справедливого раздела различных задач, от домашних обязанностей до платы за совместную аренду квартиры.
За последние 50 лет многие математики и специалисты по информатике, включая Прокаччиа, убедили себя, что ограниченного справедливого алгоритма по разделу торта на n частей не существует.
«Именно эта задача привела меня в область справедливых разделений»,- говорит Уолтер Стромквист [Walter Stromquist], профессор математики в Колледже Брина Мавра в Пенсильвании, достигший неплохих результатов в задаче делёжки торта в 1980. «Всю жизнь я думал, что я вернусь к этой задаче в свободное время и докажу, что такое расширение результата невозможно в принципе».
Но, в апреле два специалиста по информатике опровергли эти ожидания, опубликовав алгоритм справедливой делёжки торта со временем работы, зависящим от количества участников дележа, а не от их личных предпочтений. Один из учёных, 27-летний Саймон Макензи [Simon Mackenzie], доктор наук из Карнеги-Меллон, представлял свою работу 10 октября на 57-м ежегодном симпозиуме IEEE по основам информатики.
Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать до nnnnnn шагов, с примерно таким же количеством разрезов. Даже для небольшого количества участников это число превышает количество атомов во Вселенной. Но у исследователей уже есть идеи по упрощению и ускорению алгоритма, по словам второго участника команды, Хариса Азиза [Haris Aziz], 35-летнего специалиста по информатике из Университета Нового Южного Уэльса, работающего в австралийской группе исследования данных Data61.
Специалисты, исследующие теорию справедливого деления, по словам Прокаччиа, считают это «однозначно лучшим результатом за десятилетия».
Кусочки торта
Алгоритм Азиза и Макензи основан на элегантной процедуре, независимо придуманной математиками Джоном Селфриджем [John Selfridge] и Джоном Конвейем в 1960-х, позволяющим справедливо разделить торт на троих.
Если Алиса, Боб и Чарли (A, B, C) хотят разделить торт, алгоритм начинается с того, что Чарли делит торт на три куска, которые для него выглядят равноценными. Алиса и Боб выбирают куски, нравящиеся им. Если они выберут разные куски – вуаля, каждый получает то, что хотел.
Если Алиса и Боб выберут один кусок, тогда Боб отрезает небольшую часть от этого куска так, чтобы кусок стал равноценен, с его точки зрения, другому куску торта – тому, который бы Боб выбрал во вторую очередь. Отрезанный остаточек откладывается. Теперь Алиса должна выбрать лучший для себя кусок из оставшихся трёх, а затем выбирает Боб – с условием, что он возьмёт обрезанный им кусок, если Алиса его не выберет. Чарли получает третий кусок.
В результате никто никому не завидует. Алиса выбирала первой. Боб получил один из двух одинаково ценных для него кусков. Чарли получил один из трёх изначальных кусков, которые он резал сам.
Остаётся лишь небольшой отрезанный остаточек. Но его можно разделить, не начиная алгоритм сначала и не попадая в бесконечный цикл обрезаний и выборов, поскольку Чарли в любом случае удовлетворён своим куском – и даже если бы тот, кому достался обрезанный кусок, получил бы в довесок к нему весь остаточек целиком, для Чарли это не выглядело бы нечестным, потому что обрезанный кусок и остаточек в сумме дадут кусок торта, эквивалентный его куску – ведь он изначально сам эти куски и нарезал. Азиз и Макензи описывают такое положение Чарли, как «доминирующее».
Теперь, если, к примеру, Алисе достался обрезанный кусок, то Боб режет обрезки на три части, эквивалентные с его точки зрения, Алиса из этих кусков выбирает один себе, затем выбирает Чарли, затем Боб. Все счастливы: Алиса выбирала первой, Чарли получает кусок лучше, чем у Боба (и ему всё равно, сколько взяла Алиса), а с точки зрения Боба все три куска равноценны.
Брамс и Тейлор использовали свойство «доминирования» (но с другим именем) для разработки своего алгоритма 1995 года, но они не дожали свою идею до появления ограниченного алгоритма. В следующие 20 лет никто не добился лучших результатов. «И не из-за недостатка попыток», как говорит Прокаччиа.
Непрофессиональные делители тортов
Когда Азиз и Макензи (АиМ) решили взяться за эту задачу пару лет назад, они были новичками в задаче дележа торта. «У нас не было столько опыта, как у людей, интенсивно работавших над ней,- говорит Азиз. – Хотя обычно это недостаток, в нашем случае он был преимуществом, поскольку мы думали по-другому».
АиМ начали с изучения задачи дележа на трёх участников с нуля, и в результате анализа пришли к ограниченному справедливому алгоритму для четырёх участников, опубликованному ими в прошлом году.
Им не удалось сразу показать, как расширить свой алгоритм на число участников, большее четырёх, но они с энтузиазмом занялись этой задачей. «После отправки работы, касавшейся четырёх участников, мы очень хотели побыстрее продолжить работу, пока кто-нибудь более опытный и умный не обобщит её самостоятельно до случая с n участниками»,- говорит Азиз. И примерно через год их поиски увенчались успехом.
Как и алгоритм Селфриджа-Конвея, протокол АиМ постоянно предлагает разным участникам разрезать торт на n равных частей, а другим – делать отрезы и выбирать куски торта. Но в алгоритме есть и другие шаги, например периодический обмен кусками тортов специальным образом, с целью увеличения количества доминирующих взаимоотношений между участниками.
Эти отношения позволяют АиМ уменьшить сложность задаче. Если, допустим, три участника доминируют над остальными, их уже можно отправлять есть свои куски торта – они будут довольны вне зависимости от того, кто получит остатки. После этого остаётся меньшее число участников, и после ограниченного количества таких шагов все остаются довольными и весь торт оказывается поделён.
«Оглядываясь назад, на сложность алгоритма, становится неудивительно, что его разработка потребовала столько времени»,- говорит Прокаччиа. Но АиМ уже считают, что могут упростить алгоритм, чтобы он не требовал обмена кусками и проходил всего за nnn шагов. По словам Азиза, они уже работают над этими результатами.
Брамс предупреждает, что и у более простого алгоритма не будет практического применения – ведь куски торта, полученные участниками, будут включать множество мелких крошек с разных частей торта. Такой подход не особенно-то полезен, если вы, например, проводите раздел земли.
Но для специалистов по математике и информатике, изучающих задачу, новый результат «обнуляет всю тему», говорит Стромквист.
Теперь, когда исследователям известно, что торт можно разделить за ограниченное число шагов, следующим шагом, по словам Прокаччиа, будет понимание большого разрыва между верхним ограничением количества шагов по методу АиМ, и нижним ограничением необходимого для этого количества шагов. Прокаччиа уже доказал ранее, что алгоритм справедливого разделения торта не может проходить менее, чем за n2 шагов – но это количество шагов крошечное по сравнению с nnnnnn и даже с nnn.
Азиз говорит, что исследователям теперь предстоит понять, как сократить этот разрыв. «Думаю, что в обоих направлениях может быть достигнут прогресс».
Комментарии (49)
uterr
30.10.2016 19:01+4>>Чарли получает третий кусок.
Чарли, получается, в самом невыгодном положении — разрезать торт на 3 части можно, но обычно получится криво, однако по условию он получит кусок последним — значит неточность его резки выйдет боком
IndigoDSV
30.10.2016 21:24+5Ну, в случае варианта с двумя людьми, такая ситуация же считается справедливой). Первый режет, второй выбирает. Но никто не заставляет его разрезать с первого раза, если Чарли видит, что отрезал криво — пусть поделит заново. Главное, чтобы на выходе Чарли выдал ситуацию когда он согласен выбрать любой кусок и не факт, что куски должны быть одинаковыми даже по мнению самого Чарли — вдруг на одном куске вишенка)
mikhaelkh
30.10.2016 19:04+2Хоть бы формализовали задачу. Вроде надо разделить так, чтобы с точки зрения каждого их кусок был не хуже любого другого. Или каждый из N человек должен получить не менее 1/N по их мнению? И да, способность разрезать на равные части (по своему мнению) сильно преувеличена:)
vinograd19
30.10.2016 19:16+3В задаче нет никаких размеров торта.
Из данных есть только ответы на вопрос «доволен ли участник текущим разбиением, или нет?», которые можно задавать в любой момент времени любому из участников.
Придти нужно к такому состоянию, когда все участники отвечают положительно на этот вопрос.mikhaelkh
30.10.2016 19:19+3Ну тогда я могу быть недоволен, если не получил весь торт и мы его не поделим.
Celtis
30.10.2016 19:35+1Почему бы Бобу не присоединить отрезанный кусок к любому из оставшихся(сделав эти два куска равными по своему мнению) и позволить Алисе выбирать из них.
Чарли получает третий и остается доволен, так как сам нарезал равные по его мнению куски и, следовательно, согласен получить любой из них.mikhaelkh
30.10.2016 19:44Надо разделить так, чтобы с точки зрения каждого их кусок был не хуже чем у любого другого.
VIK52
30.10.2016 20:15+1Даже для двух человек будет несправедливо. Они изначально неравноправны — кто из них должен делить и почему?
trueneu
30.10.2016 21:25+1Возьмем Авраама и Лота из Ветхого завета. Допустим, делит Авраам. Если он делит землю так, что он считает участки равноценными, то он будет доволен, какой бы ему ни достался. Если Лот считает, что Авраам поделил несправдливо, Лот имеет право забрать себе тот участок, который приглянулся ему больше. Точно так же работает, если делит Лот, а выбирает Авраам.
Речь не о равноправии тех, кто выбирает, режет и делит — речь о том, чтобы никто из них не думал, что ему достался кусок хуже, чем другому.VIK52
30.10.2016 21:29+2Полагаю, тот, кто берет второй кусок, всегда будет считать, что его кусок хуже. Поэтому никто не согласится резать
trueneu
30.10.2016 21:49+1Это противоречит тому, что тот, кто режет, режет их так, что с его точки зрения куски равноценны.
rocket
30.10.2016 22:15Имеется в виду, что после деления могут закрасться сомнения в равноценности кусков, как бы ты ровно не нарезал.
VIK52
30.10.2016 22:16Как бы он не резал, у него выбора не будет. Как бы сделать так, чтобы оба резали и оба выбирали? Резать на 4 части?
dollar
31.10.2016 07:43+2Тот, кто режет, может и старается их сделать равноценными для себя. Но они, скорее всего, окажутся неравноценными для второго, который выберет лучший кусок (опять же, для себя). Получается, что первому достанется один из одинаковых (грубо говоря, 50% профита), а второму достанется лучший из двух не одинаковых (грубо говоря, 60% профита). Поэтому быть первым не выгодно, если первый должен делить честно.
Конечно, можно сказать, что первый может поделить с учётом интересов второго (если знает о них). Но здесь уже начинаются сложности с многоступенчатой рефлексией. Попытаюсь объяснить. Предположим, два человека (молодой и старый) делят землю, на которой есть колодец. Старому очень важно, чтобы на земле был колодец, потому что уже тяжело ходить за водой в соседнюю деревню. Пусть первый знает об этом и специально делит так, чтобы один кусок составлял 1% всей площади и содержал колодец. С точки зрения старика куски почти равноценны, но кусок с колодцем чуть-чуть выгоднее. Казалось бы, старый должен выбрать кусок с колодцем (для него это, условно, 51% выгоды), молодому достанется 99% площади — и все довольны. Но почему-то мне кажется, что старик взбунтуется против такой наглости и захочет поделить «по-честному».
В общем, в условиях математического алгоритма всё просто и понятно, а в жизни всё сложнее. Стороны не всегда знают, что для кого выгодно. Порой стороны даже могут не знать, что берется за 100%, а могут лишь сравнивать куски, да и то на глаз (т.е. практически наобум). При честной дележке стороны прикидывают выгоды каждой из сторон и приходят к компромиссу. А при нечестной дележке, где стороны перетягивают одеяло, дележка может не закончиться никогда, либо же закончиться в результате конфликта, по итогам которого одна из сторон может захапать весь торт или бОльшую его часть.trueneu
31.10.2016 11:30Насчет того, что в жизни все не так просто, я, конечно, с вами полностью согласен.
Но тут все-таки конкретная математическая задача, которая не принимает во внимание какие-то социальные, исторические и культурологические факторы. Можно продолжить вашу линию о старике и юноше; если старик знает о не вполне чистых помыслах юноши, он вправе забрать себе 99% площади без колодца, чтобы потом выгодно продать и вырыть 5 колодцев. Но это не имеет особого смысла в контексте задачи каждый обладает некоторым собственным мерилом ценности куска, которое во времени не изменяется; это некоторая функция
cmp(a, b), если хотите, у каждого своя. Кто-то любит площадь надела, кто-то любит колодцы; и эти приоритеты постоянны.
Ваш вариант задачи, несомненно, имеет право на жизнь, только это уже несколько другая задача. За формализованной формулировкой рассматриваемой в статье задачи можно обратиться к уже опубликованным работам, в статье есть ссылки.
DragonRU
30.10.2016 20:40+1А почему не будет работать такой алгоритм:
1) 1-й участник отрезает себе часть, которую считает равной 1/n.
2) Любой из следующих участников имеет право уменьшить ее и забрать себе
3) После того, как все участники согласны, что данная часть не больше, чем 1/n, а забирающий ее себе считает ее не меньшей, чем 1/n, задача свелась с задаче с n-1 участником
Общее количество шагов — О(n^2)senia
30.10.2016 21:12Первые 2 участника в сговоре. Один отрезает весь торт, второй его уменьшает и забирает себе.
Если же после уменьшения надо вернуться к пункту 1, то от первого куска можно по атому откусывать очень долго.DragonRU
30.10.2016 23:47Возможно, я сформулировал не совсем точно. У каждого из участников будет возможность поучаствовать в шаге 2, но только один раз. Логика простая — если от куска, который ты заявил как 1/n, уже отрезали кусочек, то с твоей точки зрения кусок теперь меньше, чем 1/n. А если ты попытался схитрить — то это уже твои проблемы.
SinsI
30.10.2016 21:25Нет ограничения на размер отрезания, поэтому и число шагов неограниченно — первый отрезает себе 99.9999%, второй уменьшает на 1/10^10, третий уменьшает на 1/10^100…
DragonRU
30.10.2016 23:57После чего первые два участника начинают кусать себе локти — поскольку свой шанс поучаствовать в дележе этого куска они уже использовали.
ShashkovS
30.10.2016 22:33+3Там проблема в том, что каждый хочет быть уверен, что его кусок не меньше любого другого. Если хотя бы один выпал из делёжки (даже с самым лучшим на тот момент куском), то после без его участия торт могут поделить настолько криво, что его кусок будет меньше с его точки зрения.
Скажем, если для него всё дело в вишенках, и изначально поделили так, что в каждом куске есть вишенка, то он готов взял себе любой кусок. Но после без него две вишенки могут попасть к одному человеку, так как оставшимся может быть решительно всё равно до вишенок. И эта несправедливость его огорчит.DragonRU
31.10.2016 01:56Да, в таком случае мое решение не работает. Я правильно вам понял, что если, с точки зрения Алисы, она получит кусок в 40%, Боб в 10%, и Чарли — 50%, то ее такой вариант не будет устраивать?
ShashkovS
31.10.2016 20:58Да, именно так. Каждый хочет быть уверен, что никто не получил больше него.
И удивительно здесь как раз то, что этого можно добиться.
APLe
31.10.2016 02:06Попробовал применить идею с вишенками, не получается.
Иду по схеме задачи:
- С разделил торт на три куска с вишенками — вишенки для него главное в торте.
- В отрезал от одного куска кусочек с вишенкой (ему плевать на вишенки, он делит просто по размеру)
- А взял кусок с вишенкой (он тоже любит только вишенки), В взял урезанный кусок без вишенки, С взял кусок c вишенкой
- B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
- А выбрал маленький кусочек с вишенкой.
- С выбрал маленький кусочек без вишенки (а что ему ещё остаётся?)
- В взял последний маленький кусочек.
Результат: У А две вишенки, у С — одна, у В — ни одной.
Разделение не справедливо с точки зрения С: он по ходу деления понял, что В вишенки всё равно не нужны, поэтому А и С имеют право рассчитывать на одинаковые порции по полторы вишенки. Ну и с точки зрения А — тоже, но А получил больше, чем должен был, и теперь рад.SinsI
31.10.2016 06:46+1> А взял кусок с вишенкой (он тоже любит только вишенки), В взял урезанный кусок без вишенки, С взял кусок c вишенкой
>B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
>А выбрал маленький кусочек с вишенкой.
Неправильно. Если B берёт урезанный кусок, то режет не он, а А (они «меняются местами»).
Правильно будет:
A разделил бонусный кусочек с вишенкой на три — по 1/3 вишенки.
B выбрал маленький кусочек, после чего выбирает C и в последнюю очередь — A.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первым, чтобы C не возмущался, а тот, кто получил «целый» — получает право разреза, но выбирает последним.APLe
31.10.2016 11:28В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первым
А, точно, за этим моментом я не уследил — разбирался по схеме и думал, что оба раза режет один человек.
Тогда лучше, но всё равно получается, что 1/3 вишенки теряется на В, которому она не нужна.
К тому же, а что, если А на вишенки тоже плевать, и при первом резе он кусок с вишенкой взял по каким-то другим причинам. А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?SinsI
31.10.2016 22:11> Тогда лучше, но всё равно получается, что 1/3 вишенки теряется на В, которому она не нужна.
Если A информирован о предпочтениях B, то он может сделать два маленьких куска с 1/2 вишенки, и один большой без неё.
> А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
ответить
Он ничего не выбирает — ему остаётся остаток после B и C.APLe
01.11.2016 04:14Если A информирован о предпочтениях B, то он может сделать два маленьких куска с 1/2 вишенки, и один большой без неё.
Идея, вроде, в том, что каждый из них исходит только из своих интересов.
Он ничего не выбирает — ему остаётся остаток после B и C.
А, действительно, опять перепутал. Извиняюсь.
igrig
30.10.2016 21:25+1Не понятно, зачем отрезанный кусок делить на три части, а не на две. Чарли уже может идти есть свой кусок, и ему все равно, даже если Алиса и Боб поубивают друг друга — завидовать нечему. Поэтому Чарли вычеркиваем и его кусок тоже. Для Боба имеются два равнозначных куска и приятный бонус, который он ранее откромсал, поэтому у Боба остается вопрос, кому же он достанется. Вот тут и приходится его (обрезок) делить, но только между Алисой и Бобом (читай на две части, а это мы уже легко умеем), и Чарли тут уже ни при чем, он доволен с самого начала.
Алисе тоже приятно, ведь она во второй итерации выбрала кусок пожирнее по ее мнению, что с половинкой от обрезка выглядит лучше, чем у Боба. А Боб ССЗБ, тоже доволен, ибо все поровну с математически выверенной точностью.
SLY_G
30.10.2016 21:27Если Чарли берёт первый кусок, а Боб отрезал мелкий кусочек от третьего куска — вдруг Алиса выберет второй кусок и заберёт ещё и отрезочек себе целиком? Тогда её кусок будет лучше куска Чарли. Нет, ему надо остаться, и проследить, чтобы никому не достался кусок лучше, чем у него.
celen
30.10.2016 22:29Чем плох старый добрый алгоритм дележа из задачки про пиратов? Алиса режет торт на две равные с её точки зрений части, Боб выбирает лучшую. Затем каждый из них режет свой кусок на три равные части и предлагает Чарли, Чарли выбирает себе лучшие куски из каждой тройки. При условии, что каждый доверяет своему дележу, ни один участник не будет обделен в смысле своей трети.
ShashkovS
30.10.2016 22:38Вся соль в жадности. Каждый хочет быть уверен, что его кусок не меньше любого другого.
Представим себе, что Боб очень любит вишенки. Алиса разрезала торт на куски по 3 вишенки в каждом. Для Боба они оба одинаковы, поэтому он берёт какой-то. Далее Боб делит свой кусок на три куска по вишенке. А Алисе до вишенок дела нет, поэтому она делит на часть с 3 вишенками, и двумя частями без вишенок.
Что бы не сделал после этого Чарли, Боб будет чувствовать себя обманутым.celen
31.10.2016 03:33Ну Боб-то получил свои законные две вишенки. Не его проблема, что эта дура Алиса ничего не понимает в вишне. В прочем, я понял.
sumanai
31.10.2016 05:15Просто засуньте его в миксер и разлейте результат на нужное число чашек. Жидкость делится намного лучше.
andrey_aksamentov
31.10.2016 05:23Что если делить не весь торт сразу а частями?
Допустим требуется разделить торт на 7 человек: делим торт на 7 кусков, затем первый человек делит первый кусок на 7 частей, все куски разбираются и съедаются. Затем второй человек режет второй кусок и т.д.IndigoDSV
31.10.2016 10:48Дак на первом же куске мы придем к той же задаче — как «справедливо» поделить кусок на 7 частей) А если мы можем его так поделить, то почему так не делить сразу весь торт, а не делать из одной задачи семь)
andrey_aksamentov
31.10.2016 11:09Не так важно как поделен торт в первый раз, как то что каждый в итоге «делит торт», и в среднем, в теории, все получат поровну.
IndigoDSV
31.10.2016 12:29Ну в итоге-то после деления торта мы получаем уже 7 кусков, которые… надо как-то опять делить. Из предложения «первый человек делит первый кусок на 7 частей, все куски разбираются и съедаются» непонятно по какому такому принципу они разбираются, что по окончании дележки последнего 7-го куска окажется, что у всех суммарно количество торта оказалось поровну? Не раскрыт механизм за счет чего это произойдет?
И получается, что если к нашему торту добавить еще 6, получив в итоге 7 различных тортов (маленьких, средних, больших), то их можно сразу «резать на куски, которые разбираются и съедаются» ведь эти торты можно рассматривать как 7 кусков одного мега-торта, так?)
Ну и, наконец, представим ситуацию: Изначально торт разделен идеально на 7 кусков, первые шесть человек, так же идеально делят свои куски и все довольны. Седьмой делит свой кусок на один большой и остальные маленькие кусочки. Тот, чья очередь брать кусок первым, берет этот большой кусок и что остается делать остальным? Ну кроме того что выкрикнуть: «Э-э, чё за дела! Так не чесно!» )
Phaker
05.11.2016 19:24-1Формальной постановки задачи здесь не хватает. По ссылке на исходную статью не ходил, но догадываюсь, что все операции должны быть, скажем так, «дискретными»: сначала одно действие, за ним другое. Потому что есть простой классический «непрерывный» алгоритм. Один участник медленно ведёт нож над тортом, увеличивая размер потенциального куска. Как только любому, включая режущего, кажется, что достигнута граница 1/N, то он произносит «стоп» и уходит довольный со своим куском. Так повторяется, пока все не уйдут довольными.
SinsI
05.11.2016 23:28Нельзя уходить — а вдруг дальше начнут резать и оценивать криво и какой-то из кусков будет больше?
Nihonjin
>Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать до n^(n^(n^(n^(n^n)))) шагов, с примерно таким же количеством разрезов. Даже для небольшого количества участников это число превышает количество атомов во Вселенной.
Это еще слабо сказано. Если предположить что в каждом планковском объеме пространства содержаться своя вселенная, размером с нашу, и в той вселенной в свою очередь то же самое, и так 500 раз, то верхнее ограничение возможного количество переборов будет больше чем количество «планковских объемов» во всех вселенных вплоть до самого глубокого уровня вложенности. (Да, мне нечего делать)
APLe
Это для какого n?
Nihonjin
Забыл написать, это всего лишь для 2-х.