Comments 62
>Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать до n^(n^(n^(n^(n^n)))) шагов, с примерно таким же количеством разрезов. Даже для небольшого количества участников это число превышает количество атомов во Вселенной.
Это еще слабо сказано. Если предположить что в каждом планковском объеме пространства содержаться своя вселенная, размером с нашу, и в той вселенной в свою очередь то же самое, и так 500 раз, то верхнее ограничение возможного количество переборов будет больше чем количество «планковских объемов» во всех вселенных вплоть до самого глубокого уровня вложенности. (Да, мне нечего делать)
Это еще слабо сказано. Если предположить что в каждом планковском объеме пространства содержаться своя вселенная, размером с нашу, и в той вселенной в свою очередь то же самое, и так 500 раз, то верхнее ограничение возможного количество переборов будет больше чем количество «планковских объемов» во всех вселенных вплоть до самого глубокого уровня вложенности. (Да, мне нечего делать)
>>Чарли получает третий кусок.
Чарли, получается, в самом невыгодном положении — разрезать торт на 3 части можно, но обычно получится криво, однако по условию он получит кусок последним — значит неточность его резки выйдет боком
Чарли, получается, в самом невыгодном положении — разрезать торт на 3 части можно, но обычно получится криво, однако по условию он получит кусок последним — значит неточность его резки выйдет боком
Ну, в случае варианта с двумя людьми, такая ситуация же считается справедливой). Первый режет, второй выбирает. Но никто не заставляет его разрезать с первого раза, если Чарли видит, что отрезал криво — пусть поделит заново. Главное, чтобы на выходе Чарли выдал ситуацию когда он согласен выбрать любой кусок и не факт, что куски должны быть одинаковыми даже по мнению самого Чарли — вдруг на одном куске вишенка)
Задача математическая, и к непосредственно торту относится довольно абстрактно.Такой алгоритм можно применять к разделу земли, бюджетов, доходов, расходов, времени презентаций и вообще чего угодно. Очень трудная задача — уравнять разности приоритетов, к примеру насколько важнее получить 35 минут на свой доклад, чем получить 30 минут в периоде до 11:00 утра?
Хоть бы формализовали задачу. Вроде надо разделить так, чтобы с точки зрения каждого их кусок был не хуже любого другого. Или каждый из N человек должен получить не менее 1/N по их мнению? И да, способность разрезать на равные части (по своему мнению) сильно преувеличена:)
В задаче нет никаких размеров торта.
Из данных есть только ответы на вопрос «доволен ли участник текущим разбиением, или нет?», которые можно задавать в любой момент времени любому из участников.
Придти нужно к такому состоянию, когда все участники отвечают положительно на этот вопрос.
Из данных есть только ответы на вопрос «доволен ли участник текущим разбиением, или нет?», которые можно задавать в любой момент времени любому из участников.
Придти нужно к такому состоянию, когда все участники отвечают положительно на этот вопрос.
Ну тогда я могу быть недоволен, если не получил весь торт и мы его не поделим.
Ок, формализм тут
Почему бы Бобу не присоединить отрезанный кусок к любому из оставшихся(сделав эти два куска равными по своему мнению) и позволить Алисе выбирать из них.
Чарли получает третий и остается доволен, так как сам нарезал равные по его мнению куски и, следовательно, согласен получить любой из них.
Чарли получает третий и остается доволен, так как сам нарезал равные по его мнению куски и, следовательно, согласен получить любой из них.
Даже для двух человек будет несправедливо. Они изначально неравноправны — кто из них должен делить и почему?
Возьмем Авраама и Лота из Ветхого завета. Допустим, делит Авраам. Если он делит землю так, что он считает участки равноценными, то он будет доволен, какой бы ему ни достался. Если Лот считает, что Авраам поделил несправдливо, Лот имеет право забрать себе тот участок, который приглянулся ему больше. Точно так же работает, если делит Лот, а выбирает Авраам.
Речь не о равноправии тех, кто выбирает, режет и делит — речь о том, чтобы никто из них не думал, что ему достался кусок хуже, чем другому.
Речь не о равноправии тех, кто выбирает, режет и делит — речь о том, чтобы никто из них не думал, что ему достался кусок хуже, чем другому.
Полагаю, тот, кто берет второй кусок, всегда будет считать, что его кусок хуже. Поэтому никто не согласится резать
Это противоречит тому, что тот, кто режет, режет их так, что с его точки зрения куски равноценны.
Имеется в виду, что после деления могут закрасться сомнения в равноценности кусков, как бы ты ровно не нарезал.
Как бы он не резал, у него выбора не будет. Как бы сделать так, чтобы оба резали и оба выбирали? Резать на 4 части?
Тот, кто режет, может и старается их сделать равноценными для себя. Но они, скорее всего, окажутся неравноценными для второго, который выберет лучший кусок (опять же, для себя). Получается, что первому достанется один из одинаковых (грубо говоря, 50% профита), а второму достанется лучший из двух не одинаковых (грубо говоря, 60% профита). Поэтому быть первым не выгодно, если первый должен делить честно.
Конечно, можно сказать, что первый может поделить с учётом интересов второго (если знает о них). Но здесь уже начинаются сложности с многоступенчатой рефлексией. Попытаюсь объяснить. Предположим, два человека (молодой и старый) делят землю, на которой есть колодец. Старому очень важно, чтобы на земле был колодец, потому что уже тяжело ходить за водой в соседнюю деревню. Пусть первый знает об этом и специально делит так, чтобы один кусок составлял 1% всей площади и содержал колодец. С точки зрения старика куски почти равноценны, но кусок с колодцем чуть-чуть выгоднее. Казалось бы, старый должен выбрать кусок с колодцем (для него это, условно, 51% выгоды), молодому достанется 99% площади — и все довольны. Но почему-то мне кажется, что старик взбунтуется против такой наглости и захочет поделить «по-честному».
В общем, в условиях математического алгоритма всё просто и понятно, а в жизни всё сложнее. Стороны не всегда знают, что для кого выгодно. Порой стороны даже могут не знать, что берется за 100%, а могут лишь сравнивать куски, да и то на глаз (т.е. практически наобум). При честной дележке стороны прикидывают выгоды каждой из сторон и приходят к компромиссу. А при нечестной дележке, где стороны перетягивают одеяло, дележка может не закончиться никогда, либо же закончиться в результате конфликта, по итогам которого одна из сторон может захапать весь торт или бОльшую его часть.
Конечно, можно сказать, что первый может поделить с учётом интересов второго (если знает о них). Но здесь уже начинаются сложности с многоступенчатой рефлексией. Попытаюсь объяснить. Предположим, два человека (молодой и старый) делят землю, на которой есть колодец. Старому очень важно, чтобы на земле был колодец, потому что уже тяжело ходить за водой в соседнюю деревню. Пусть первый знает об этом и специально делит так, чтобы один кусок составлял 1% всей площади и содержал колодец. С точки зрения старика куски почти равноценны, но кусок с колодцем чуть-чуть выгоднее. Казалось бы, старый должен выбрать кусок с колодцем (для него это, условно, 51% выгоды), молодому достанется 99% площади — и все довольны. Но почему-то мне кажется, что старик взбунтуется против такой наглости и захочет поделить «по-честному».
В общем, в условиях математического алгоритма всё просто и понятно, а в жизни всё сложнее. Стороны не всегда знают, что для кого выгодно. Порой стороны даже могут не знать, что берется за 100%, а могут лишь сравнивать куски, да и то на глаз (т.е. практически наобум). При честной дележке стороны прикидывают выгоды каждой из сторон и приходят к компромиссу. А при нечестной дележке, где стороны перетягивают одеяло, дележка может не закончиться никогда, либо же закончиться в результате конфликта, по итогам которого одна из сторон может захапать весь торт или бОльшую его часть.
Насчет того, что в жизни все не так просто, я, конечно, с вами полностью согласен.
Но тут все-таки конкретная математическая задача, которая не принимает во внимание какие-то социальные, исторические и культурологические факторы. Можно продолжить вашу линию о старике и юноше; если старик знает о не вполне чистых помыслах юноши, он вправе забрать себе 99% площади без колодца, чтобы потом выгодно продать и вырыть 5 колодцев. Но это не имеет особого смысла в контексте задачи каждый обладает некоторым собственным мерилом ценности куска, которое во времени не изменяется; это некоторая функция cmp(a, b), если хотите, у каждого своя. Кто-то любит площадь надела, кто-то любит колодцы; и эти приоритеты постоянны.
Ваш вариант задачи, несомненно, имеет право на жизнь, только это уже несколько другая задача. За формализованной формулировкой рассматриваемой в статье задачи можно обратиться к уже опубликованным работам, в статье есть ссылки.
А почему не будет работать такой алгоритм:
1) 1-й участник отрезает себе часть, которую считает равной 1/n.
2) Любой из следующих участников имеет право уменьшить ее и забрать себе
3) После того, как все участники согласны, что данная часть не больше, чем 1/n, а забирающий ее себе считает ее не меньшей, чем 1/n, задача свелась с задаче с n-1 участником
Общее количество шагов — О(n^2)
1) 1-й участник отрезает себе часть, которую считает равной 1/n.
2) Любой из следующих участников имеет право уменьшить ее и забрать себе
3) После того, как все участники согласны, что данная часть не больше, чем 1/n, а забирающий ее себе считает ее не меньшей, чем 1/n, задача свелась с задаче с n-1 участником
Общее количество шагов — О(n^2)
Первые 2 участника в сговоре. Один отрезает весь торт, второй его уменьшает и забирает себе.
Если же после уменьшения надо вернуться к пункту 1, то от первого куска можно по атому откусывать очень долго.
Если же после уменьшения надо вернуться к пункту 1, то от первого куска можно по атому откусывать очень долго.
Возможно, я сформулировал не совсем точно. У каждого из участников будет возможность поучаствовать в шаге 2, но только один раз. Логика простая — если от куска, который ты заявил как 1/n, уже отрезали кусочек, то с твоей точки зрения кусок теперь меньше, чем 1/n. А если ты попытался схитрить — то это уже твои проблемы.
Нет ограничения на размер отрезания, поэтому и число шагов неограниченно — первый отрезает себе 99.9999%, второй уменьшает на 1/10^10, третий уменьшает на 1/10^100…
Там проблема в том, что каждый хочет быть уверен, что его кусок не меньше любого другого. Если хотя бы один выпал из делёжки (даже с самым лучшим на тот момент куском), то после без его участия торт могут поделить настолько криво, что его кусок будет меньше с его точки зрения.
Скажем, если для него всё дело в вишенках, и изначально поделили так, что в каждом куске есть вишенка, то он готов взял себе любой кусок. Но после без него две вишенки могут попасть к одному человеку, так как оставшимся может быть решительно всё равно до вишенок. И эта несправедливость его огорчит.
Скажем, если для него всё дело в вишенках, и изначально поделили так, что в каждом куске есть вишенка, то он готов взял себе любой кусок. Но после без него две вишенки могут попасть к одному человеку, так как оставшимся может быть решительно всё равно до вишенок. И эта несправедливость его огорчит.
Да, в таком случае мое решение не работает. Я правильно вам понял, что если, с точки зрения Алисы, она получит кусок в 40%, Боб в 10%, и Чарли — 50%, то ее такой вариант не будет устраивать?
Попробовал применить идею с вишенками, не получается.
Иду по схеме задачи:
Результат: У А две вишенки, у С — одна, у В — ни одной.
Разделение не справедливо с точки зрения С: он по ходу деления понял, что В вишенки всё равно не нужны, поэтому А и С имеют право рассчитывать на одинаковые порции по полторы вишенки. Ну и с точки зрения А — тоже, но А получил больше, чем должен был, и теперь рад.
Иду по схеме задачи:
- С разделил торт на три куска с вишенками — вишенки для него главное в торте.
- В отрезал от одного куска кусочек с вишенкой (ему плевать на вишенки, он делит просто по размеру)
- А взял кусок с вишенкой (он тоже любит только вишенки), В взял урезанный кусок без вишенки, С взял кусок c вишенкой
- B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
- А выбрал маленький кусочек с вишенкой.
- С выбрал маленький кусочек без вишенки (а что ему ещё остаётся?)
- В взял последний маленький кусочек.
Результат: У А две вишенки, у С — одна, у В — ни одной.
Разделение не справедливо с точки зрения С: он по ходу деления понял, что В вишенки всё равно не нужны, поэтому А и С имеют право рассчитывать на одинаковые порции по полторы вишенки. Ну и с точки зрения А — тоже, но А получил больше, чем должен был, и теперь рад.
> А взял кусок с вишенкой (он тоже любит только вишенки), В взял урезанный кусок без вишенки, С взял кусок c вишенкой
>B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
>А выбрал маленький кусочек с вишенкой.
Неправильно. Если B берёт урезанный кусок, то режет не он, а А (они «меняются местами»).
Правильно будет:
A разделил бонусный кусочек с вишенкой на три — по 1/3 вишенки.
B выбрал маленький кусочек, после чего выбирает C и в последнюю очередь — A.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первым, чтобы C не возмущался, а тот, кто получил «целый» — получает право разреза, но выбирает последним.
>B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
>А выбрал маленький кусочек с вишенкой.
Неправильно. Если B берёт урезанный кусок, то режет не он, а А (они «меняются местами»).
Правильно будет:
A разделил бонусный кусочек с вишенкой на три — по 1/3 вишенки.
B выбрал маленький кусочек, после чего выбирает C и в последнюю очередь — A.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первым, чтобы C не возмущался, а тот, кто получил «целый» — получает право разреза, но выбирает последним.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первымА, точно, за этим моментом я не уследил — разбирался по схеме и думал, что оба раза режет один человек.
Тогда лучше, но всё равно получается, что 1/3 вишенки теряется на В, которому она не нужна.
К тому же, а что, если А на вишенки тоже плевать, и при первом резе он кусок с вишенкой взял по каким-то другим причинам. А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
> Тогда лучше, но всё равно получается, что 1/3 вишенки теряется на В, которому она не нужна.
Если A информирован о предпочтениях B, то он может сделать два маленьких куска с 1/2 вишенки, и один большой без неё.
> А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
ответить
Он ничего не выбирает — ему остаётся остаток после B и C.
Если A информирован о предпочтениях B, то он может сделать два маленьких куска с 1/2 вишенки, и один большой без неё.
> А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
ответить
Он ничего не выбирает — ему остаётся остаток после B и C.
Не понятно, зачем отрезанный кусок делить на три части, а не на две. Чарли уже может идти есть свой кусок, и ему все равно, даже если Алиса и Боб поубивают друг друга — завидовать нечему. Поэтому Чарли вычеркиваем и его кусок тоже. Для Боба имеются два равнозначных куска и приятный бонус, который он ранее откромсал, поэтому у Боба остается вопрос, кому же он достанется. Вот тут и приходится его (обрезок) делить, но только между Алисой и Бобом (читай на две части, а это мы уже легко умеем), и Чарли тут уже ни при чем, он доволен с самого начала.
Алисе тоже приятно, ведь она во второй итерации выбрала кусок пожирнее по ее мнению, что с половинкой от обрезка выглядит лучше, чем у Боба. А Боб ССЗБ, тоже доволен, ибо все поровну с математически выверенной точностью.
Алисе тоже приятно, ведь она во второй итерации выбрала кусок пожирнее по ее мнению, что с половинкой от обрезка выглядит лучше, чем у Боба. А Боб ССЗБ, тоже доволен, ибо все поровну с математически выверенной точностью.
Чем плох старый добрый алгоритм дележа из задачки про пиратов? Алиса режет торт на две равные с её точки зрений части, Боб выбирает лучшую. Затем каждый из них режет свой кусок на три равные части и предлагает Чарли, Чарли выбирает себе лучшие куски из каждой тройки. При условии, что каждый доверяет своему дележу, ни один участник не будет обделен в смысле своей трети.
Вся соль в жадности. Каждый хочет быть уверен, что его кусок не меньше любого другого.
Представим себе, что Боб очень любит вишенки. Алиса разрезала торт на куски по 3 вишенки в каждом. Для Боба они оба одинаковы, поэтому он берёт какой-то. Далее Боб делит свой кусок на три куска по вишенке. А Алисе до вишенок дела нет, поэтому она делит на часть с 3 вишенками, и двумя частями без вишенок.
Что бы не сделал после этого Чарли, Боб будет чувствовать себя обманутым.
Представим себе, что Боб очень любит вишенки. Алиса разрезала торт на куски по 3 вишенки в каждом. Для Боба они оба одинаковы, поэтому он берёт какой-то. Далее Боб делит свой кусок на три куска по вишенке. А Алисе до вишенок дела нет, поэтому она делит на часть с 3 вишенками, и двумя частями без вишенок.
Что бы не сделал после этого Чарли, Боб будет чувствовать себя обманутым.
UFO just landed and posted this here
UFO just landed and posted this here
Дак на первом же куске мы придем к той же задаче — как «справедливо» поделить кусок на 7 частей) А если мы можем его так поделить, то почему так не делить сразу весь торт, а не делать из одной задачи семь)
UFO just landed and posted this here
Ну в итоге-то после деления торта мы получаем уже 7 кусков, которые… надо как-то опять делить. Из предложения «первый человек делит первый кусок на 7 частей, все куски разбираются и съедаются» непонятно по какому такому принципу они разбираются, что по окончании дележки последнего 7-го куска окажется, что у всех суммарно количество торта оказалось поровну? Не раскрыт механизм за счет чего это произойдет?
И получается, что если к нашему торту добавить еще 6, получив в итоге 7 различных тортов (маленьких, средних, больших), то их можно сразу «резать на куски, которые разбираются и съедаются» ведь эти торты можно рассматривать как 7 кусков одного мега-торта, так?)
Ну и, наконец, представим ситуацию: Изначально торт разделен идеально на 7 кусков, первые шесть человек, так же идеально делят свои куски и все довольны. Седьмой делит свой кусок на один большой и остальные маленькие кусочки. Тот, чья очередь брать кусок первым, берет этот большой кусок и что остается делать остальным? Ну кроме того что выкрикнуть: «Э-э, чё за дела! Так не чесно!» )
И получается, что если к нашему торту добавить еще 6, получив в итоге 7 различных тортов (маленьких, средних, больших), то их можно сразу «резать на куски, которые разбираются и съедаются» ведь эти торты можно рассматривать как 7 кусков одного мега-торта, так?)
Ну и, наконец, представим ситуацию: Изначально торт разделен идеально на 7 кусков, первые шесть человек, так же идеально делят свои куски и все довольны. Седьмой делит свой кусок на один большой и остальные маленькие кусочки. Тот, чья очередь брать кусок первым, берет этот большой кусок и что остается делать остальным? Ну кроме того что выкрикнуть: «Э-э, чё за дела! Так не чесно!» )
надо думать надо порядком выбора. В теории человек может выбирать первым из кусков, которые ему не нравятся, и последним из кусков, которые ему нравятся. Думаю он будет не доволен таким результатом.
промахнулся уровнем…
Формальной постановки задачи здесь не хватает. По ссылке на исходную статью не ходил, но догадываюсь, что все операции должны быть, скажем так, «дискретными»: сначала одно действие, за ним другое. Потому что есть простой классический «непрерывный» алгоритм. Один участник медленно ведёт нож над тортом, увеличивая размер потенциального куска. Как только любому, включая режущего, кажется, что достигнута граница 1/N, то он произносит «стоп» и уходит довольный со своим куском. Так повторяется, пока все не уйдут довольными.
Нельзя уходить — а вдруг дальше начнут резать и оценивать криво и какой-то из кусков будет больше?
Можно. Цели хапнуть побольше, чтоб другим было хуже, не ставится. Цель справедливого раздела — чтобы каждый был уверен, что ему досталось не меньше, чем 1/N от всего пирога. Данный алгоритм гарантирует, что никто не будет считать, что ему осталось меньше положенной доли.
Цель — чтобы тебе досталось не хуже, чем кому-либо другому.
Если тебе досталась «справедливая» тысяча, но кому-то другому достался миллион, то ты не будешь таким дележом доволен. Ты тоже хочешь миллион, а не тысячу!
Если тебе досталась «справедливая» тысяча, но кому-то другому достался миллион, то ты не будешь таким дележом доволен. Ты тоже хочешь миллион, а не тысячу!
Вот я и начал с того, что формальной постановки задачи здесь не хватает. Ваша версия трактовки «справедливого раздела» и моя версия — это разные задачи. Поэтому хотелось видеть в статье строгую формулировку того, что ожидают участники раздела. В жизни они могут хотеть что угодно, но математическую задачу так формулировать нельзя.
Самое логичное и простое решение:
1. Берём большой мощный блендер
2. Кладём торт в блендер
3. ВЖ-Ж-Ж-Ж-Ж!
4. Разливаем торт по тарелкам
5. Все довольны, а вы восхитительны!
Побочное достоинство решения: жевать торт больше не нужно.
В случае с землёй понадобится большой бульдозер.
Зато потом на этой земле можно строить что душе угодно!
1. Берём большой мощный блендер
2. Кладём торт в блендер
3. ВЖ-Ж-Ж-Ж-Ж!
4. Разливаем торт по тарелкам
5. Все довольны, а вы восхитительны!
Побочное достоинство решения: жевать торт больше не нужно.
В случае с землёй понадобится большой бульдозер.
Зато потом на этой земле можно строить что душе угодно!
Чарли режет торт на три больших куска,
далее Боб режет каждый кусок на два маленьких,
Алиса выбирает два маленьких куска, но чтобы они не были частями одного большого куска,
Чарли выбирает два любых куска,
Боб забирает что осталось.
Для 4 участников:
первый режет торт пополам,
второй каждую половину ещё пополам,
третий каждый кусок ещё пополам,
четвётый выбирает 2 кусочка,
потом первый 2 кусочка и далее по кругу.
по моему так будет справедливо, если кто-то ошибся получит меньшее.
далее Боб режет каждый кусок на два маленьких,
Алиса выбирает два маленьких куска, но чтобы они не были частями одного большого куска,
Чарли выбирает два любых куска,
Боб забирает что осталось.
Для 4 участников:
первый режет торт пополам,
второй каждую половину ещё пополам,
третий каждый кусок ещё пополам,
четвётый выбирает 2 кусочка,
потом первый 2 кусочка и далее по кругу.
по моему так будет справедливо, если кто-то ошибся получит меньшее.
Кусок в центре получается не такой вкусный, как остальные, так как крема и прочих плюшек меньше, чем у кусков с краю. :)
Одним из участников над тортом заносится нож, и постепенно движется над ним до тех пор пока один из N участников не скажет «стоп», отрезается кусок. Тот участник который остановил получает этот кусок. И так до конца
Sign up to leave a comment.
Как справедливо порезать торт