Страницы: 1 2 3 4 5 ... 15 След.
RSS
Как разделить пирог?, Старая задача с новым решением?
Давно уже читал такую задачу у Мартина Гарднера:
Цитата
Как разделить пирог?
Существует простой способ, при котором двое могут разделить пирог так, чтобы каждому досталась по крайней мере половина: один разрезает пирог, а другой выбирает себе кусок. Придумайте общий метод, который позволил бы N персонам разделить пирог на N частей так, чтобы каждому досталось не меньше, чем по 1/N пирога.
В той же книге, Математические головоломки и развлечения М.Мир.1971, указано и решение. И, кстати, редакторская ссылка на решение в ещё более ранней книге от 1960г.
Надо заметить, что в книжке Гарднера (или её переводе?) говорится о равном делении пирога, хотя правильнее говорить о справедливом делении.
.
Несмотря на известное решение уже в 2009 г. появилось сообщение Математики придумали алгоритм честного деления пирога на троих  .
.
Но оказалось, что это решение всё еще не решение. Недавно появилось сообщение  Специалисты по информатике разработали алгоритм справедливого раздела пирога для любого количества людей
Что характерно, со временем задача становится всё сложнее. В книге М. Гарднера указывается, что разделить пирог можно несколькими способами и приводится один из алгоритмов на пол-странички.
А вот, что говорится про решение представленное 10 октября на 57-м ежегодном симпозиуме IEEE по основам информатики: Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать столько шагов, что даже для небольшого количества участников это число превышает количество атомов во Вселенной.
Специалисты, исследующие теорию справедливого деления, считают это «однозначно лучшим результатом за десятилетия».
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
Надо заметить, что в книжке Гарднера (или её переводе?) говорится о равном делении пирога, хотя правильнее говорить о справедливом делении.
Здесь видимо имеется в виду, что "равенство" кусков является критерием "справедливости". Когда таких критериев много, причём у каждого свой набор критериев, задача резко усложняется.
Изменено: Техник - 03.11.2016 11:01:53
Ясность - одна из форм полного тумана
Цитата
Техник пишет:
Здесь видимо имеется в виду, что "равенство" кусков является критерием "справедливости". Когда таких критериев много, причём у каждого свой набор критериев, задача резко усложняется.
Да, конечно.
В конце концов, равенство определяется чисто технически и объективно, по весу или объёму.
Но суть задачи, как раз, в субъективной оценке каждого потребителя, что означает не объективное равенство, а субъективную справедливость. Один может оценивать по весу, другой по объёму, третий по наличию вишенки. А вообще, все оценивают по разным параметрам, причём, с разными приоритетами.
Объективное расчленение тортика возможно, только если кто-то свыше укажет, какие параметры главные и если пирог можно разделить по этим параметрам.
Здесь ситуация другая. Каждый потребитель должен быть уверен, что ему достался кусок не хуже чем у других, по его субъективному мнению. Субъективное мнение каждого, это критерий справедливого раздела.
Если пирог делится на двоих, то это очень просто: один режет, другой выбирает. Больше народу - больше сложностей.
По-моему, задача, даже, не совсем математическая или логическая, а скорее философская, поскольку необходимо придумать новое понятие.
Было старое понятие "разделить пирог". Интуитивно это действие понятно и детализации не требует. А для математически справедливой делёжки на двоих необходимо это понятие разложить на две разные составляющие: разрезать и выбрать.
Для более сложной делёжки, на троих и далее, надо ещё что-то изобрести.
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
Каждый потребитель должен быть уверен, что ему достался кусок не хуже чем у других, по его субъективному мнению.
В хорошем коллективе не принципиально. Я резала пиццу и торт на 20 частей, и на 17 частей. Никто не обиделся.
Внимание! Данное сообщение содержит исключительно личное мнение автора. Есть основания полагать, что оно может не отвечать критериям научности.
Цитата
Olginoz пишет:
В хорошем коллективе не принципиально.
Это так.
Во многих комментариях встречал, что как ни странно пол-литра делится на троих всегда исключительно справедливо.
Это всё случаи, когда ради хорошей компании чувство справедливости задвигается на задний план.
В споре не рождается истина, но убивается время.
Цитата
Olginoz пишет:
В хорошем коллективе не принципиально.
Так в том и дело, что в задаче предполагается, что коллектив не очень хороший, т.е. каждый хочет ухватить себе кусок получше, а соседу подсунуть похуже
:)
Изменено: Техник - 03.11.2016 18:41:47
Ясность - одна из форм полного тумана
Цитата
eLectric пишет:
разрезать и выбрать.

...надо ещё что-то изобрести.

незаметно уйти :)
Ясность - одна из форм полного тумана
Цитата
Техник пишет:
незаметно уйти
По английски.

Мне вот что интересно.
Сейчас (и уже в который раз) с торжеством объявляют об очередном достижении математики и нахождении такого, ну очень сложного алгоритма.
А в уже довольно старой книге М. Гарднера с решением для N участников есть ссылка на книгу Р. Д. Льюса и Г. Райффа «Игры и решения» (ИЛ, I960).
Я нашёл эту книжку в интернетах. В ней есть ссылка на более раннюю статью Штейнхауза от 1948 г. А в статье указывается, что задача решена ещё ранее Кнастером  и Банахом.

Получается, что до 80-х годов прошлого века знали, что задача давно решена, а после того и к нашему времени задача оказывается ну очень сложной и есть некоторые перспективы, что в будущем удастся найти хоть как-то приемлемое решение.
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
[уйти] По английски.
Не. С одной стороны, незаметно сбежать с тортом зависть окружающих всё равно не позволит, а с другой, хорошо бы уменьшать количество страждущих в процессе делёжки, дабы завершить процесс за конечное время.
Но насколько я понял, достижение как раз в том, что найден такой алгоритм делёжки без выбывания участников.
Цитата
eLectric пишет:
Получается, что до 80-х годов прошлого века знали, что задача давно решена, а после того и к нашему времени задача оказывается ну очень сложной и есть некоторые перспективы, что в будущем удастся найти хоть как-то приемлемое решение.
Надо смотреть на конкретную формулировку задачи. В той формулировке, что вы привели в начале (по-честному значит поровну) - ну да, задача давно решена.
А сейчас, видимо, решают другую задачу - и пирог неоднородный, и предпочтения разные.
Как-то так.
Изменено: Техник - 04.11.2016 21:49:19
Ясность - одна из форм полного тумана
Цитата
Техник пишет:
Надо смотреть на конкретную формулировку задачи. В той формулировке, что вы привели в начале (по-честному значит поровну) - ну да, задача давно решена.
А сейчас, видимо, решают другую задачу - и пирог неоднородный, и предпочтения разные.
Пирог неоднородный, например с вишенкой, это было с самого начала.
Поровну, это как? По массе или по объёму или по сумме вкусовых характеристик?
Я думаю, что "поровну" требует какого-то технического решения, но никак не математического. В книжке Р. Д. Льюса и Г. Райффа «Игры и решения» рассматриваются разные варианты задач. Книжка про теорию игр. В том числе, про справедливое деление неделимых предметов. Но в нашем случае пирог бесконечно-делимый.
Мне кажется, есть разница в рассуждениях участников. В простом решении от Банаха приводится и самое простое рассуждение (в изложении М. Гарднера):
Цитата
Разделить пирог между n персонами так, чтобы каждой из них досталось по крайней мере 1/n пирога, можно несколькими способами. Предлагаемый нами способ обладает тем преимуществом, что после раздела не остается лишних кусков пирога.
Предположим, что имеется пять желающих получить по куску пирога: А, В, С, D и Е.
А отрезает кусок, который, по его мнению, составляет 1/5 пирога, и намеревается оставить его себе. Если В считает, что А отрезал слишком большой кусок, то он (В) имеет право уменьшить этот кусок до размеров, которые он считает соответствующими 1/5 пирога. Разумеется, если В считает, что отрезанный А кусок меньше 1/5, то он к нему вообще не прикасается. Аналогичными  правами пользуются по очереди С, D и Е. Кусок достается тому из пятерых, кто дотрагивался до него последним. Всякий, кто считает, что получившему кусок пирога досталось меньше 1/5, естественно, доволен: ведь, по его мнению осталось больше 4/5 пирога. Оставшаяся часть пирога (сюда входят и кусочки, отрезанные при доведении отрезанного куска до «кондиции»)  делится затем точно таким же образом между четырьмя, тремя и т.д. любителями пирога. При последнем разделе один из участников режет пирог, а другой выбирает. Ясно, что этот метод применим  при  любом  числе  заинтересованных лиц.
Возможно, это слишком простое рассуждение, которое не принимают современные математики. Где-то здесь и кроется философия. Но как-то я не встречал принцип современных рассуждений для этой задачи.

Одна мысль вдогонку.
В рассуждениях Банаха предполагается, что отрезание кусочка приводит к снижению ценности куска. Но в общем случае может быть и наоборот. Возможно, что современные решения учитывают это обобщение.
Изменено: eLectric - 05.11.2016 12:17:43
В споре не рождается истина, но убивается время.
Страницы: 1 2 3 4 5 ... 15 След.

Как разделить пирог?


Портал журнала «Наука и жизнь» использует файлы cookie и рекомендательные технологии. Продолжая пользоваться порталом, вы соглашаетесь с хранением и использованием порталом и партнёрскими сайтами файлов cookie и рекомендательных технологий на вашем устройстве. Подробнее