Как разделить пирог? Существует простой способ, при котором двое могут разделить пирог так, чтобы каждому досталась по крайней мере половина: один разрезает пирог, а другой выбирает себе кусок. Придумайте общий метод, который позволил бы N персонам разделить пирог на N частей так, чтобы каждому досталось не меньше, чем по 1/N пирога.
В той же книге, Математические головоломки и развлечения М.Мир.1971, указано и решение. И, кстати, редакторская ссылка на решение в ещё более ранней книге от 1960г. Надо заметить, что в книжке Гарднера (или её переводе?) говорится о равном делении пирога, хотя правильнее говорить о справедливом делении. . Несмотря на известное решение уже в 2009 г. появилось сообщение Математики придумали алгоритм честного деления пирога на троих . . Но оказалось, что это решение всё еще не решение. Недавно появилось сообщение Специалисты по информатике разработали алгоритм справедливого раздела пирога для любого количества людей Что характерно, со временем задача становится всё сложнее. В книге М. Гарднера указывается, что разделить пирог можно несколькими способами и приводится один из алгоритмов на пол-странички. А вот, что говорится про решение представленное 10 октября на 57-м ежегодном симпозиуме IEEE по основам информатики: Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать столько шагов, что даже для небольшого количества участников это число превышает количество атомов во Вселенной. Специалисты, исследующие теорию справедливого деления, считают это «однозначно лучшим результатом за десятилетия».
eLectric пишет: Надо заметить, что в книжке Гарднера (или её переводе?) говорится о равном делении пирога, хотя правильнее говорить о справедливом делении.
Здесь видимо имеется в виду, что "равенство" кусков является критерием "справедливости". Когда таких критериев много, причём у каждого свой набор критериев, задача резко усложняется.
Техник пишет: Здесь видимо имеется в виду, что "равенство" кусков является критерием "справедливости". Когда таких критериев много, причём у каждого свой набор критериев, задача резко усложняется.
Да, конечно. В конце концов, равенство определяется чисто технически и объективно, по весу или объёму. Но суть задачи, как раз, в субъективной оценке каждого потребителя, что означает не объективное равенство, а субъективную справедливость. Один может оценивать по весу, другой по объёму, третий по наличию вишенки. А вообще, все оценивают по разным параметрам, причём, с разными приоритетами. Объективное расчленение тортика возможно, только если кто-то свыше укажет, какие параметры главные и если пирог можно разделить по этим параметрам. Здесь ситуация другая. Каждый потребитель должен быть уверен, что ему достался кусок не хуже чем у других, по его субъективному мнению. Субъективное мнение каждого, это критерий справедливого раздела. Если пирог делится на двоих, то это очень просто: один режет, другой выбирает. Больше народу - больше сложностей. По-моему, задача, даже, не совсем математическая или логическая, а скорее философская, поскольку необходимо придумать новое понятие. Было старое понятие "разделить пирог". Интуитивно это действие понятно и детализации не требует. А для математически справедливой делёжки на двоих необходимо это понятие разложить на две разные составляющие: разрезать и выбрать. Для более сложной делёжки, на троих и далее, надо ещё что-то изобрести.
Olginoz пишет: В хорошем коллективе не принципиально.
Это так. Во многих комментариях встречал, что как ни странно пол-литра делится на троих всегда исключительно справедливо. Это всё случаи, когда ради хорошей компании чувство справедливости задвигается на задний план.
Olginoz пишет: В хорошем коллективе не принципиально.
Так в том и дело, что в задаче предполагается, что коллектив не очень хороший, т.е. каждый хочет ухватить себе кусок получше, а соседу подсунуть похуже
Мне вот что интересно. Сейчас (и уже в который раз) с торжеством объявляют об очередном достижении математики и нахождении такого, ну очень сложного алгоритма. А в уже довольно старой книге М. Гарднера с решением для N участников есть ссылка на книгу Р. Д. Льюса и Г. Райффа «Игры и решения» (ИЛ, I960). Я нашёл эту книжку в интернетах. В ней есть ссылка на более раннюю статью Штейнхауза от 1948 г. А в статье указывается, что задача решена ещё ранее Кнастером и Банахом.
Получается, что до 80-х годов прошлого века знали, что задача давно решена, а после того и к нашему времени задача оказывается ну очень сложной и есть некоторые перспективы, что в будущем удастся найти хоть как-то приемлемое решение.
Не. С одной стороны, незаметно сбежать с тортом зависть окружающих всё равно не позволит, а с другой, хорошо бы уменьшать количество страждущих в процессе делёжки, дабы завершить процесс за конечное время. Но насколько я понял, достижение как раз в том, что найден такой алгоритм делёжки без выбывания участников.
Цитата
eLectric пишет: Получается, что до 80-х годов прошлого века знали, что задача давно решена, а после того и к нашему времени задача оказывается ну очень сложной и есть некоторые перспективы, что в будущем удастся найти хоть как-то приемлемое решение.
Надо смотреть на конкретную формулировку задачи. В той формулировке, что вы привели в начале (по-честному значит поровну) - ну да, задача давно решена. А сейчас, видимо, решают другую задачу - и пирог неоднородный, и предпочтения разные. Как-то так.
Техник пишет: Надо смотреть на конкретную формулировку задачи. В той формулировке, что вы привели в начале (по-честному значит поровну) - ну да, задача давно решена. А сейчас, видимо, решают другую задачу - и пирог неоднородный, и предпочтения разные.
Пирог неоднородный, например с вишенкой, это было с самого начала. Поровну, это как? По массе или по объёму или по сумме вкусовых характеристик? Я думаю, что "поровну" требует какого-то технического решения, но никак не математического. В книжке Р. Д. Льюса и Г. Райффа «Игры и решения» рассматриваются разные варианты задач. Книжка про теорию игр. В том числе, про справедливое деление неделимых предметов. Но в нашем случае пирог бесконечно-делимый. Мне кажется, есть разница в рассуждениях участников. В простом решении от Банаха приводится и самое простое рассуждение (в изложении М. Гарднера):
Цитата
Разделить пирог между n персонами так, чтобы каждой из них досталось по крайней мере 1/n пирога, можно несколькими способами. Предлагаемый нами способ обладает тем преимуществом, что после раздела не остается лишних кусков пирога. Предположим, что имеется пять желающих получить по куску пирога: А, В, С, D и Е. А отрезает кусок, который, по его мнению, составляет 1/5 пирога, и намеревается оставить его себе. Если В считает, что А отрезал слишком большой кусок, то он (В) имеет право уменьшить этот кусок до размеров, которые он считает соответствующими 1/5 пирога. Разумеется, если В считает, что отрезанный А кусок меньше 1/5, то он к нему вообще не прикасается. Аналогичными правами пользуются по очереди С, D и Е. Кусок достается тому из пятерых, кто дотрагивался до него последним. Всякий, кто считает, что получившему кусок пирога досталось меньше 1/5, естественно, доволен: ведь, по его мнению осталось больше 4/5 пирога. Оставшаяся часть пирога (сюда входят и кусочки, отрезанные при доведении отрезанного куска до «кондиции») делится затем точно таким же образом между четырьмя, тремя и т.д. любителями пирога. При последнем разделе один из участников режет пирог, а другой выбирает. Ясно, что этот метод применим при любом числе заинтересованных лиц.
Возможно, это слишком простое рассуждение, которое не принимают современные математики. Где-то здесь и кроется философия. Но как-то я не встречал принцип современных рассуждений для этой задачи.
Одна мысль вдогонку. В рассуждениях Банаха предполагается, что отрезание кусочка приводит к снижению ценности куска. Но в общем случае может быть и наоборот. Возможно, что современные решения учитывают это обобщение.
Портал журнала «Наука и жизнь» использует файлы cookie.
Продолжая пользоваться порталом, вы соглашаетесь с хранением и использованием
порталом и партнёрскими сайтами файлов cookie на вашем устройстве.
Подробнее