Comments 62
Это еще слабо сказано. Если предположить что в каждом планковском объеме пространства содержаться своя вселенная, размером с нашу, и в той вселенной в свою очередь то же самое, и так 500 раз, то верхнее ограничение возможного количество переборов будет больше чем количество «планковских объемов» во всех вселенных вплоть до самого глубокого уровня вложенности. (Да, мне нечего делать)
Чарли, получается, в самом невыгодном положении — разрезать торт на 3 части можно, но обычно получится криво, однако по условию он получит кусок последним — значит неточность его резки выйдет боком
Из данных есть только ответы на вопрос «доволен ли участник текущим разбиением, или нет?», которые можно задавать в любой момент времени любому из участников.
Придти нужно к такому состоянию, когда все участники отвечают положительно на этот вопрос.
Чарли получает третий и остается доволен, так как сам нарезал равные по его мнению куски и, следовательно, согласен получить любой из них.
Даже для двух человек будет несправедливо. Они изначально неравноправны — кто из них должен делить и почему?
Речь не о равноправии тех, кто выбирает, режет и делит — речь о том, чтобы никто из них не думал, что ему достался кусок хуже, чем другому.
Полагаю, тот, кто берет второй кусок, всегда будет считать, что его кусок хуже. Поэтому никто не согласится резать
Как бы он не резал, у него выбора не будет. Как бы сделать так, чтобы оба резали и оба выбирали? Резать на 4 части?
Конечно, можно сказать, что первый может поделить с учётом интересов второго (если знает о них). Но здесь уже начинаются сложности с многоступенчатой рефлексией. Попытаюсь объяснить. Предположим, два человека (молодой и старый) делят землю, на которой есть колодец. Старому очень важно, чтобы на земле был колодец, потому что уже тяжело ходить за водой в соседнюю деревню. Пусть первый знает об этом и специально делит так, чтобы один кусок составлял 1% всей площади и содержал колодец. С точки зрения старика куски почти равноценны, но кусок с колодцем чуть-чуть выгоднее. Казалось бы, старый должен выбрать кусок с колодцем (для него это, условно, 51% выгоды), молодому достанется 99% площади — и все довольны. Но почему-то мне кажется, что старик взбунтуется против такой наглости и захочет поделить «по-честному».
В общем, в условиях математического алгоритма всё просто и понятно, а в жизни всё сложнее. Стороны не всегда знают, что для кого выгодно. Порой стороны даже могут не знать, что берется за 100%, а могут лишь сравнивать куски, да и то на глаз (т.е. практически наобум). При честной дележке стороны прикидывают выгоды каждой из сторон и приходят к компромиссу. А при нечестной дележке, где стороны перетягивают одеяло, дележка может не закончиться никогда, либо же закончиться в результате конфликта, по итогам которого одна из сторон может захапать весь торт или бОльшую его часть.
Насчет того, что в жизни все не так просто, я, конечно, с вами полностью согласен.
Но тут все-таки конкретная математическая задача, которая не принимает во внимание какие-то социальные, исторические и культурологические факторы. Можно продолжить вашу линию о старике и юноше; если старик знает о не вполне чистых помыслах юноши, он вправе забрать себе 99% площади без колодца, чтобы потом выгодно продать и вырыть 5 колодцев. Но это не имеет особого смысла в контексте задачи каждый обладает некоторым собственным мерилом ценности куска, которое во времени не изменяется; это некоторая функция cmp(a, b)
, если хотите, у каждого своя. Кто-то любит площадь надела, кто-то любит колодцы; и эти приоритеты постоянны.
Ваш вариант задачи, несомненно, имеет право на жизнь, только это уже несколько другая задача. За формализованной формулировкой рассматриваемой в статье задачи можно обратиться к уже опубликованным работам, в статье есть ссылки.
1) 1-й участник отрезает себе часть, которую считает равной 1/n.
2) Любой из следующих участников имеет право уменьшить ее и забрать себе
3) После того, как все участники согласны, что данная часть не больше, чем 1/n, а забирающий ее себе считает ее не меньшей, чем 1/n, задача свелась с задаче с n-1 участником
Общее количество шагов — О(n^2)
Если же после уменьшения надо вернуться к пункту 1, то от первого куска можно по атому откусывать очень долго.
Скажем, если для него всё дело в вишенках, и изначально поделили так, что в каждом куске есть вишенка, то он готов взял себе любой кусок. Но после без него две вишенки могут попасть к одному человеку, так как оставшимся может быть решительно всё равно до вишенок. И эта несправедливость его огорчит.
Иду по схеме задачи:
- С разделил торт на три куска с вишенками — вишенки для него главное в торте.
- В отрезал от одного куска кусочек с вишенкой (ему плевать на вишенки, он делит просто по размеру)
- А взял кусок с вишенкой (он тоже любит только вишенки), В взял урезанный кусок без вишенки, С взял кусок c вишенкой
- B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
- А выбрал маленький кусочек с вишенкой.
- С выбрал маленький кусочек без вишенки (а что ему ещё остаётся?)
- В взял последний маленький кусочек.
Результат: У А две вишенки, у С — одна, у В — ни одной.
Разделение не справедливо с точки зрения С: он по ходу деления понял, что В вишенки всё равно не нужны, поэтому А и С имеют право рассчитывать на одинаковые порции по полторы вишенки. Ну и с точки зрения А — тоже, но А получил больше, чем должен был, и теперь рад.
>B разделил бонусный кусочек с вишенкой на три — вишенка только на одном из них.
>А выбрал маленький кусочек с вишенкой.
Неправильно. Если B берёт урезанный кусок, то режет не он, а А (они «меняются местами»).
Правильно будет:
A разделил бонусный кусочек с вишенкой на три — по 1/3 вишенки.
B выбрал маленький кусочек, после чего выбирает C и в последнюю очередь — A.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первым, чтобы C не возмущался, а тот, кто получил «целый» — получает право разреза, но выбирает последним.
В алгоритме тот, кто получил «урезаный» кусок выбирает добавок первымА, точно, за этим моментом я не уследил — разбирался по схеме и думал, что оба раза режет один человек.
Тогда лучше, но всё равно получается, что 1/3 вишенки теряется на В, которому она не нужна.
К тому же, а что, если А на вишенки тоже плевать, и при первом резе он кусок с вишенкой взял по каким-то другим причинам. А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
Если A информирован о предпочтениях B, то он может сделать два маленьких куска с 1/2 вишенки, и один большой без неё.
> А второй рез он делает без учёта вишенки, как и В — а потом, снова по каким-то другим причинам, опять выбирает кусок с вишенкой?
ответить
Он ничего не выбирает — ему остаётся остаток после B и C.
Алисе тоже приятно, ведь она во второй итерации выбрала кусок пожирнее по ее мнению, что с половинкой от обрезка выглядит лучше, чем у Боба. А Боб ССЗБ, тоже доволен, ибо все поровну с математически выверенной точностью.
Представим себе, что Боб очень любит вишенки. Алиса разрезала торт на куски по 3 вишенки в каждом. Для Боба они оба одинаковы, поэтому он берёт какой-то. Далее Боб делит свой кусок на три куска по вишенке. А Алисе до вишенок дела нет, поэтому она делит на часть с 3 вишенками, и двумя частями без вишенок.
Что бы не сделал после этого Чарли, Боб будет чувствовать себя обманутым.
И получается, что если к нашему торту добавить еще 6, получив в итоге 7 различных тортов (маленьких, средних, больших), то их можно сразу «резать на куски, которые разбираются и съедаются» ведь эти торты можно рассматривать как 7 кусков одного мега-торта, так?)
Ну и, наконец, представим ситуацию: Изначально торт разделен идеально на 7 кусков, первые шесть человек, так же идеально делят свои куски и все довольны. Седьмой делит свой кусок на один большой и остальные маленькие кусочки. Тот, чья очередь брать кусок первым, берет этот большой кусок и что остается делать остальным? Ну кроме того что выкрикнуть: «Э-э, чё за дела! Так не чесно!» )
Если тебе досталась «справедливая» тысяча, но кому-то другому достался миллион, то ты не будешь таким дележом доволен. Ты тоже хочешь миллион, а не тысячу!
1. Берём большой мощный блендер
2. Кладём торт в блендер
3. ВЖ-Ж-Ж-Ж-Ж!
4. Разливаем торт по тарелкам
5. Все довольны, а вы восхитительны!
Побочное достоинство решения: жевать торт больше не нужно.
В случае с землёй понадобится большой бульдозер.
Зато потом на этой земле можно строить что душе угодно!
далее Боб режет каждый кусок на два маленьких,
Алиса выбирает два маленьких куска, но чтобы они не были частями одного большого куска,
Чарли выбирает два любых куска,
Боб забирает что осталось.
Для 4 участников:
первый режет торт пополам,
второй каждую половину ещё пополам,
третий каждый кусок ещё пополам,
четвётый выбирает 2 кусочка,
потом первый 2 кусочка и далее по кругу.
по моему так будет справедливо, если кто-то ошибся получит меньшее.
Как справедливо порезать торт