как разделить пирог на 5 равных частей
Как разделить пирог на 5 равных частей?
Существует простой способ, при котором двое могут разделить пирог так, чтобы каждому досталась по крайней мере половина: один разрезает пирог, а другой выбирает себе кусок. Придумайте общий метод, который позволил бы n персонам разделить пирог на N частей так, чтобы каждому досталось не меньше, чем по 1/N пирога.
Ответ
Предположим, что имеется 5 желающих получить по куску пирога: А, В, С, D и Е. Первым, отрезает кусок А, который, по его мнению, составляет 1/5 пирога, и намеревается оставить его себе. Если В считает, что А отрезал слишком большой кусок, то он (В) имеет право уменьшить этот кусок до размеров, которые он считает соответствующими 1/5 пирога. Разумеется, если В считает, что отрезанный А кусок меньше 1/5, то он к нему вообще не прикасается. Аналогичными правами пользуются по очереди С, D и Е. Кусок достается тому из пятерых, кто дотрагивается до него последним. Всякий, кто считает, что получившему кусок пирога досталось меньше 1/5, естественно, доволен: ведь, по его мнению, осталось больше 4/5 пирога. Оставшаяся часть пирога (сюда входят и кусочки, отрезанные при доведении уже отрезанного куска до «кондиции») делится затем точно таким же образом между четырьмя, тремя и т. д. любителями пирога. При последнем разделе один из участников режет пирог, а другой выбирает. Ясно, что этот метод применим при любом числе заинтересованных лиц.
Подробный разбор этого решения задачи содержится в книге Р. Д. Льюиса и Г. Райффа «Игры и решения» (1960).
О задаче
Похожие задачи
Список похожих занимательных задач:
Скачать задачу
Вы можете скачать изображение с текстом задачи, поделиться им с друзьями в социальных сетях либо использовать в презентациях. Для скачивания, нажмите на картинке.
Оставить комментарий
Свои вопросы, комментарии, замечания и занимательные задачи присылайте через предложенную ниже форму.
Решите задачу
Сколько квадратов изображено на рисунке?
Занимательные задачи
Ещё больше занимательных задач собрано в следующих разделах:
Как поделить пирог чтобы все остались довольны
Есть задача — разделить некое целое между несколькими претендентами и чтобы при этом каждый остался доволен. Причём разделить в реальных бытовых условиях — пирог, например — с линейкой и циркулем вокруг него не сильно удобно бегать, да и целое бывает неоднородным.
На двоих
Первый делит, второй выбирает. Соответственно, первый старается поделить поровнее, чтобы впоследствии порадоваться любой доставшейся доле.
Философская идея
Почему не остаётся недовольных? Потому что каждый обладает всей полнотой выбора, при этом — о чудо — не притесняя соседей. Почти 200% свободы 🙂 С решением внешнего судьи — выбранного человека или судьбы при жеребьёвке — всегда могут несогласиться (хотя бы внутренне), здесь же каждый участвует в вершении своей судьбы потому что что-то делает, а не только принимает чужой вердикт.
Альтернативные решения и подобные задачи приветствуются.
На троих (уже посложнее)
а) N1 делит пирог на три части как может; и снова покидает сцену.
б) N2 и N3 выбирают себе по куску. Если их выбор разнится, на этом делёж и заканчивается — N1 забирает что осталось.
в) (Если оба претендуют на один и тот же кусок.) Теперь надо избавиться от какого-то куска, чтобы осталось их два — скинуть один номеру первому.
Просто дать первому выбрать свой кусок нельзя, чтобы удержать его от соблазна порезать пирог заведомо неровно и завладеть самой большой, по итогу, долей:
Выбирать что достанётся N1, как и в дележе «на двоих», должны N2 и N3. Каждый из них теперь выбирает кусок для N1. В случае единого мнения, N1 кушает свой кусок; иначе, он выбирает из двух ему предложенных и опять удаляется откушивать свою долю.
г) Итак, осталось два куска и два претендента. Задача сводится к дележу «на двоих» два раза. Один кусок режет N1, выбирает N2. Со вторым куском наоборот:
Как справедливо порезать торт
Специалисты по информатике разработали алгоритм справедливого раздела пирога для любого количества людей
Двое молодых учёных, специалистов в области информатики, придумали, как честно поделить торт между любым количеством людей, решив задачу, над которой математики бились десятилетиями. Их работа удивила многих исследователей, считавших такое разделение невозможным в принципе.
Делёж пирога – это метафора для широкого круга реальных задач, включающих деление некоего непрерывного объекта, будь это торт или надел земли, между людьми, по-разному оценивающими его свойства. Одному нравится шоколадное покрытие, другой хочет получить кремовые цветочки. С библейских времён известен алгоритм деления такого объекта между двумя людьми, такой, чтобы никто не завидовал другому: один человек делит торт на две равные для него части, а другой выбирает одну из них. В Книге Бытия Авраам (тогда ещё известный, как Аврам) и Лот использовали этот метод для раздела земли, когда Авраам придумывал разделение, а Лот выбирал между Иорданом и Ханааном.
В 1960-х математики придумали алгоритм для подобного разделения пирога «без зависти» уже для трёх человек. Но до сих пор лучшим решением задачи для количества людей больше трёх была процедура, созданная в 1995 году политологом Стивеном Брамсом [Steven Brams] из Нью-Йоркского университета и математиком Аланом Тейлором [Alan Taylor] из Юнион-колледжа. Она гарантировала «справедливую» делёжку пирога, но с одним условием – процедура была «неограниченной», то есть число шагов, необходимое для делёжки, могло оказаться сколь угодно большим.
Алгоритм Брамса-Тейлора в своё время был назван прорывным, но «его неограниченность, по-моему, была большим недостатком», говорит Ариель Прокаччиа [Ariel Procaccia], специалист по информатике из Университета Карнеги-Меллон, один из создателей Spliddit, бесплатного онлайн-инструмента для справедливого раздела различных задач, от домашних обязанностей до платы за совместную аренду квартиры.
За последние 50 лет многие математики и специалисты по информатике, включая Прокаччиа, убедили себя, что ограниченного справедливого алгоритма по разделу торта на n частей не существует.
«Именно эта задача привела меня в область справедливых разделений»,- говорит Уолтер Стромквист [Walter Stromquist], профессор математики в Колледже Брина Мавра в Пенсильвании, достигший неплохих результатов в задаче делёжки торта в 1980. «Всю жизнь я думал, что я вернусь к этой задаче в свободное время и докажу, что такое расширение результата невозможно в принципе».
Но, в апреле два специалиста по информатике опровергли эти ожидания, опубликовав алгоритм справедливой делёжки торта со временем работы, зависящим от количества участников дележа, а не от их личных предпочтений. Один из учёных, 27-летний Саймон Макензи [Simon Mackenzie], доктор наук из Карнеги-Меллон, представлял свою работу 10 октября на 57-м ежегодном симпозиуме IEEE по основам информатики.
Алгоритм чрезвычайно сложный. Раздел торта между n участниками может потребовать до n n n n n n шагов, с примерно таким же количеством разрезов. Даже для небольшого количества участников это число превышает количество атомов во Вселенной. Но у исследователей уже есть идеи по упрощению и ускорению алгоритма, по словам второго участника команды, Хариса Азиза [Haris Aziz], 35-летнего специалиста по информатике из Университета Нового Южного Уэльса, работающего в австралийской группе исследования данных Data61.
Специалисты, исследующие теорию справедливого деления, по словам Прокаччиа, считают это «однозначно лучшим результатом за десятилетия».
Кусочки торта
Алгоритм Азиза и Макензи основан на элегантной процедуре, независимо придуманной математиками Джоном Селфриджем [John Selfridge] и Джоном Конвейем в 1960-х, позволяющим справедливо разделить торт на троих.
Если Алиса, Боб и Чарли (A, B, C) хотят разделить торт, алгоритм начинается с того, что Чарли делит торт на три куска, которые для него выглядят равноценными. Алиса и Боб выбирают куски, нравящиеся им. Если они выберут разные куски – вуаля, каждый получает то, что хотел.
Если Алиса и Боб выберут один кусок, тогда Боб отрезает небольшую часть от этого куска так, чтобы кусок стал равноценен, с его точки зрения, другому куску торта – тому, который бы Боб выбрал во вторую очередь. Отрезанный остаточек откладывается. Теперь Алиса должна выбрать лучший для себя кусок из оставшихся трёх, а затем выбирает Боб – с условием, что он возьмёт обрезанный им кусок, если Алиса его не выберет. Чарли получает третий кусок.
В результате никто никому не завидует. Алиса выбирала первой. Боб получил один из двух одинаково ценных для него кусков. Чарли получил один из трёх изначальных кусков, которые он резал сам.
Остаётся лишь небольшой отрезанный остаточек. Но его можно разделить, не начиная алгоритм сначала и не попадая в бесконечный цикл обрезаний и выборов, поскольку Чарли в любом случае удовлетворён своим куском – и даже если бы тот, кому достался обрезанный кусок, получил бы в довесок к нему весь остаточек целиком, для Чарли это не выглядело бы нечестным, потому что обрезанный кусок и остаточек в сумме дадут кусок торта, эквивалентный его куску – ведь он изначально сам эти куски и нарезал. Азиз и Макензи описывают такое положение Чарли, как «доминирующее».
Теперь, если, к примеру, Алисе достался обрезанный кусок, то Боб режет обрезки на три части, эквивалентные с его точки зрения, Алиса из этих кусков выбирает один себе, затем выбирает Чарли, затем Боб. Все счастливы: Алиса выбирала первой, Чарли получает кусок лучше, чем у Боба (и ему всё равно, сколько взяла Алиса), а с точки зрения Боба все три куска равноценны.
Брамс и Тейлор использовали свойство «доминирования» (но с другим именем) для разработки своего алгоритма 1995 года, но они не дожали свою идею до появления ограниченного алгоритма. В следующие 20 лет никто не добился лучших результатов. «И не из-за недостатка попыток», как говорит Прокаччиа.
Непрофессиональные делители тортов
Когда Азиз и Макензи (АиМ) решили взяться за эту задачу пару лет назад, они были новичками в задаче дележа торта. «У нас не было столько опыта, как у людей, интенсивно работавших над ней,- говорит Азиз. – Хотя обычно это недостаток, в нашем случае он был преимуществом, поскольку мы думали по-другому».
АиМ начали с изучения задачи дележа на трёх участников с нуля, и в результате анализа пришли к ограниченному справедливому алгоритму для четырёх участников, опубликованному ими в прошлом году.
Им не удалось сразу показать, как расширить свой алгоритм на число участников, большее четырёх, но они с энтузиазмом занялись этой задачей. «После отправки работы, касавшейся четырёх участников, мы очень хотели побыстрее продолжить работу, пока кто-нибудь более опытный и умный не обобщит её самостоятельно до случая с n участниками»,- говорит Азиз. И примерно через год их поиски увенчались успехом.
Как и алгоритм Селфриджа-Конвея, протокол АиМ постоянно предлагает разным участникам разрезать торт на n равных частей, а другим – делать отрезы и выбирать куски торта. Но в алгоритме есть и другие шаги, например периодический обмен кусками тортов специальным образом, с целью увеличения количества доминирующих взаимоотношений между участниками.
Эти отношения позволяют АиМ уменьшить сложность задаче. Если, допустим, три участника доминируют над остальными, их уже можно отправлять есть свои куски торта – они будут довольны вне зависимости от того, кто получит остатки. После этого остаётся меньшее число участников, и после ограниченного количества таких шагов все остаются довольными и весь торт оказывается поделён.
«Оглядываясь назад, на сложность алгоритма, становится неудивительно, что его разработка потребовала столько времени»,- говорит Прокаччиа. Но АиМ уже считают, что могут упростить алгоритм, чтобы он не требовал обмена кусками и проходил всего за n n n шагов. По словам Азиза, они уже работают над этими результатами.
Брамс предупреждает, что и у более простого алгоритма не будет практического применения – ведь куски торта, полученные участниками, будут включать множество мелких крошек с разных частей торта. Такой подход не особенно-то полезен, если вы, например, проводите раздел земли.
Но для специалистов по математике и информатике, изучающих задачу, новый результат «обнуляет всю тему», говорит Стромквист.
Азиз говорит, что исследователям теперь предстоит понять, как сократить этот разрыв. «Думаю, что в обоих направлениях может быть достигнут прогресс».
НОД по ФЭМП в средней группе «Раздели пирог»
Татьяна Сушко
НОД по ФЭМП в средней группе «Раздели пирог»
Цель:обучать навыку счёта ;помочь освоить понятия преобразования геометрических фигур;развивать мелкую моторику;закреплять пространственное воображение;формируем обобщённое представление о фруктах,ягодах,формируем навыки деления целого на равные части;развиваем логическое мышление,развиваем навыки владения ножницами.
Материал:набор ягод:малина,чёрная смородина,фланелёграф,фигурки (силуэты)садовника,его жены и двух детей. Наборы геометрических фигур (квадраты,рисунки двух пирогов квадратной формы,картинки садовника на фоне сада.
Ход занятия:
Воспитатель:(показывает картинку с изображением сада и садовника)Кто это?Как называют людей,которые выращивают сады,ухаживают за ними?
В:У одного садовника была жена и двое детей. (выставляет на фланелёграф фигурки садовника,его жены и двоих детей).Сколько всего человек в его семье?
В:Жена испекла два пирога. Посмотрим на первый пирог. Какой он формы? (показывает пирог квадратной формы).
Д: Это квадрат. Пирог квадратный.
В:А чем хозяйка украсила пирог? Какие ягоды она использовала?
В:На сколько равных частей нам нужно разделить пирог,чтобы всем досталось поровну?
В:Давайте разделим пирог на четыре части,а почему вы так решили?
Д: Потому что их в семье четыре человека.
В:Предлагает детям взять бумажные квадраты с четырьмя красными точками,расположенными в углах. Дети путём перегибания листа бумаги делят «пирог» на четыре части. Воспитатель проверяет правильность выполнения работы каждым ребёнком и предлагает им отрезать один кусочек и положить его справа.
В:(показывает детям другой пирог такой же формы и такого же размера,но ягоды чёрные и расположены по серединам боковых сторон.
В:Какими ягодами украсила хозяйка этот пирог?
В:Правильно!А какого цвета эта смородина?
В:А какая ещё бывает?Кто знает?
В:А давайте поможем его тоже разделить на четыре части так,чтобы на каждой из них была смородинка. Но сначала подумайте,как будете делить,а потом делите.
(Дети сгибают,допускают ошибки,воспитатель объясняет,в чём ошибка,показывает работу тех кто выполнил правильно. В процессе совместной деятельности приходят к выводу,что пирог следует поделить так. Рис.
Дети отрезают один кусок и кладут рядом с первым. Воспитатель показывает два куска от разных «пирогов«.
В:Посмотрите, какой кусок больше?
Дети рассматривают,спорят,какой кусок больше,а какой меньше. Сравнение способом наложения не даёт результата. Воспитатель снова обращается к форме «пирогов«,к их размерам. Дети убеждаются,что «пироги» были одинаковые и каждый делили на четыре части. Воспитатель предлагает внимательно посмотреть на получившиеся фигуры и подумать,как доказать,что они равны,как из одного куска получить другой.
Дети предлагают разрезать треугольник и из полученных частей сложить квадрат. Или разрезать квадрат по диагонали и из полученных частей сложить треугольник.
Так дети познакомились с преобразованием фигур.
«Сенсорная стена» Для развития мелкой моторики рук мною была изготовлена «Сенсорная стена», из старой детской кроватки. На ней расположены крупные и мелкие.
Игра «Пуговичная мозаика и развивающий коврик». Дети постоянно изучают, постигают окружающий мир. Основной метод накопления информации – прикосновения. Детям необходимо все хватать, трогать,.
Как математики нарезают торт?
Как лучше всего нарезать торт? Если вы не профессиональный свадебный планировщик, то наверняка не часто размышляли над таким вопросом. Вы можете подумать, что ответ довольно прост. Нужно просто посчитать количество гостей, сидящих за столом, и поделить десерт на одинаковые куски. Всевозможные диеты и аллергии на глютен могут усложнить ваши вычисления, но в конечном счете этот процесс вряд ли покажется сложным математическим действием.
Тем не менее, как бы парадоксально это ни звучало, речь идет именно о высшей математике, и вы определенно забыли задать себе несколько важных вопросов.
К примеру, гарантирует ли ваш способ нарезки торта, что никто не покинет вечеринку, почувствовав себя обделенным? Предприняли ли вы какие-то шаги, дабы убедиться в том, что каждый посетитель будет в равной степени удовлетворен своим отдельно взятым ломтиком?
Как видите, сейчас мы говорим не просто о торте. В контексте решения проблемы «справедливого распределения», затрагивающей математику, политологию и экономику, торт представляет собой нечто большее, чем обыкновенный десерт. Торт — это многоэтажный дом с квартирами, которые следует разделить между придирчивыми жильцами. Торт — это бракоразводный процесс с высокими отступными. Торт — это охваченная гражданской войной страна.
Начиная с XVII века, теоретики занимаются разработкой методов, которые бы позволяли делить необходимые нам вещи в соответствии с жестким формализмом математики и нашими субъективными представлениями о справедливости. Все это время торт использовался в качестве мощной метафоры для всего ценного, исчерпаемого и делимого в этом мире.
И теперь, с учетом последних достижений в области теории справедливого распределения (fair division theory) и информатики, все больше исследователей хотят сделать эти методы доступными для неосведомленной общественности. Чтобы всего одним нажатием кнопки вы могли бы порезать торт как настоящий математик.
Принцип справедливого деления
Детям уже давно известен лучший способ разделить объект на две части. Этот метод называется «Я разделяю, ты выбираешь», и вы наверняка использовали этот алгоритм справедливого деления в далеком детстве. Гениальность данного подхода заключается не только в том, что он достаточно прост для применения, но и в том, что при определенных обстоятельствах он дает объективные результаты.
Человек, применяющий его, знает, что другой выберет себе лучший кусок, поэтому старается разрезать торт (бутерброд или что-либо еще) как можно более справедливо. Таким образом, обе стороны гарантированно получают порции, которые, по их мнению, являются примерно одинаковыми.
Экономисты и математики нарекли этот метод «свободным от зависти» и таким определением они попали точно в цель. Если у вас есть ванильный торт, и вам нужно разделить его между двумя людьми, каждый из которых одинаково любит сладкое, то, чтобы никто не начал завидовать, торт нужно разделить пополам. Оба получат равный кусок торта, и никаких математических талантов для такого разделения не нужно.
Метод «Я разделяю, ты выбираешь» работает не только для материальных вещей (торты и арахисовое масло). Как показал популярный писатель Мартин Гарднер в 1978 году, домашние обязанности также можно распределить, если один человек делит каждую задачу на две части, а другой выбирает одну из них.
Этот метод также используется юристами. При заключении контрактов на совместную собственность, адвокаты часто прибегают к денежному аналогу принципа «Я разделяю, ты выбираешь». Когда люди при разводе делят собственность, один партнер называет цену, а другой решает, хочет ли он её выкупить или продать.
Как пишет Джеймс Ф. Ринг, «инициирующая сторона ставит своего противника в положение, когда наиболее разумная стратегия для него заключается в том, чтобы честно оценить собственность и закончить спор».
Ринг убедился в этом на собственном опыте. Являясь соучредителем Fair Outcomes, компании, специализирующейся на оказании помощи людям при разводах, Ринг и Стивен Брамс нашли множество применений метода «Я разделяю, ты выбираешь».
В обзоре способов справедливого разделения, опубликованных на сайте nautil.us, научный писатель Эрика Кларрайх приводит один любопытный пример. В случае спора при расторжении брака или отношений, алгоритм, который Ринг и Брамс называют «Справедливая покупка-продажа», предполагает, что каждый партнер одновременно называет свою цену.
«Если Джон предложит 110 000 долларов, а Джейн предложит 100 000 долларов, тогда Джон, предложивший более высокую цену может выкупить вещь у Джейн за 105 000 долларов», — объясняет Ринг. «Каждый участник в результате получает что-то — деньги или вещь — по цене, которая лучше, чем его предложение».
Этот метод нашел место даже в международном морском праве. В 1970-х годах, когда государства готовились к будущему, в котором подводная добыча ископаемых станет крупной отраслью, развивающиеся страны были обеспокоены тем, что технологически более развитые корпорации приобретут права на разработку наиболее ценных морских участков.
Решение было предложено и ратифицировано в Конвенции по морскому праву. Теперь, если компания хочет добывать ресурсы с морского дна, она должна сначала разделить участок на две части. После чего менее развитая сторона выбирает один из них.
«Свобода от зависти»
Но, как может сказать любой ученик начальной школы, существуют такие конфликты, справиться с которыми не в состоянии даже способ «Я разделяю, ты выбираешь».
Возвращаясь к кулинарной метафоре, представьте себе, что рассматриваемый торт не простой ванильный (допустим, вдоль левого края были размещены несколько кусочков клубники), и что голодные гости за столом имеют разные предпочтения (может быть, один человек предпочитает фрукты, а другой любит выпечку).
Если пирог будет делить любитель клубники, он может разделить его на две половины, оставив равное количество клубники на каждой. Так он получит свою долю фруктов независимо от выбора другого человека. Поскольку любитель выпечки собирается выбросить свою клубнику, для него тоже не имеет значения, какую половину выбрать. В результате никто не будет завидовать.
Но всё же есть кое-что неудовлетворительное в подобном исходе. В частности, экономисты назвали бы этот результат «неэффективным», потому что торт можно было разрезать таким образом, чтобы сделать по крайней мере одного из участников счастливее, не причинив никому вреда. В приведённом примере можно было сделать так: любитель ягоды мог поменять часть своего пирога на клубнику. Всем было бы лучше.
Значит, разделение было неправильным? Ведь лучше, если бы он оставил себе больше клубники?
Предположим другую ситуацию. Любитель клубники просто отсекает меньшую покрытую ягодами половину. Таким образом, он гарантированно получит либо меньший кусок с большим количеством ягоды (что было бы хорошо, потому что он любит клубнику), либо больший кусочек без ягод (что тоже неплохо, потому что, несмотря на отсутствие ягод, он все же получает больше пирога).
На этот раз выбор для его друга очевиден. Он выберет большую часть торта.
Теперь результат можно назвать эффективным, потому что кусочки торта нельзя было бы поменять, не сделав хотя бы одну из сторон неудовлетворенной. Более того, в результате никто никому не завидует. Ни у одной из сторон нет причин хотеть поменять свой кусок. В теории нет причин для зависти.
И тем не менее, сложность людской психологии запутывает математическую выстроенную модель человеческого поведения. Вышеприведенное решение теоретически может иметь последствия, противоречащие нашему чувству справедливости. Поклонник клубники в любом случае не проиграет (он получает кусочек, который, по его мнению, составляет 50% от стоимости торта), в то время как любитель торта получает большую часть торта, то есть выигрывает в сделке.
Как разделить торт между тремя и более людьми
Десятилетиями теоретики тщетно пытались найти справедливое решение проблемы деления. Ведь приглашение к столу дополнительных претендентов на торт вводит еще большую сложность.
В 1940-х годах польский профессор Хьюго Штайнхаус подошел к этому вопросу с математической строгостью. Спросив себя, существует ли вариант метода «Я разделяю, ты выбираешь» для трех или более человек, он в конечном итоге придумал то, что теперь называется «методом одинокого разделителя».
Проиллюстрируем его суть на примере. Представьте себе трех потенциальных покупателей торта. Один из них выбирается наугад. Он становится «одиноким разделителем», и его просят разделить торт на три части. Как и в случае с «Я разделяю, ты выбираешь», он не знает, какой кусочек ему суждено получить, и поэтому пытается разделить торт на три одинаково желаемых ломтика.
Остальным двум участникам, выборщикам, предлагается записать, какие из кусочков они бы хотели. Затем списки сравниваются. Если они хотят разные кусочки, то игра окончена: каждый из них получает то, что хотел, а первый разделитель получает третий кусок.
Если же выборщики хотят один кусок, то разделителю дается одна из двух не востребованных частей, а два оставшихся куска соединяются. Теперь у нас есть один маленький торт, два голодных конкурента и метод «Я разделяю, ты выбираешь», который и решит их проблему.
Метод Штайнхауса привлекательно прост и может быть расширен до более чем трех человек, но он не гарантирует результатов, в которых не было бы зависти. Для этого требуется более сложная математика.
Торт из треугольников
Фрэнсис Су получил докторскую степень по математике в Гарварде в конце 1990-х, когда Брэд Манн, его друг и кандидат в докторанты, пришел к нему со своей проблемой.
Как и большинство студентов в районе Кембриджа, Манн снимал тесный домик с несколькими знакомыми. Естественно, их мнения расходились в том, кто должен получить комнату больших размеров. Манн пришел к Су с вопросом, как выйти из тупика.
В то время как большинство из нас предложило бы бросить жребий, Су, который теперь является профессором в колледже Харви Мадд и Президентом Математической ассоциации Америки, предложил оригинальное решение.
«Когда он рассказал мне о своем затруднительном положении, я сказал:«Это математический вопрос!», — рассказывает Су. В частности, это был вопрос справедливого разделения.
Возможно, решение Су было не очень полезным для Манна, но спустя несколько лет Су опубликовал статью на эту тему, в которой он смог доказать, что в доме, разделенном в соответствии с его методом, комнаты и арендная плата могут быть разделены так, чтобы никого не обидеть.
Статью Су новаторской сделало то, что он использовал сложный математический аргумент 1920-х годов, названный «леммой Спернера». Изначально лемма не имела ничего общего с арендой или тортами. Она относилась к треугольникам.
Представим себе, что у вас есть большой треугольник, как на рисунке выше. Каждую из вершин треугольника обозначим числами (в данном случае 1, 2 и 3). Треугольник затем разделяется на ряд меньших треугольников, и их вершинам также присваиваются числа.
Но здесь есть сложность. Любая вершина вдоль края большего треугольника должна делиться своим числом с одной из двух точек в конце этого края. Например, в нижней части треугольника могут быть только 1 и 2, потому что они расположены между двумя точками большего треугольника, которые обозначены 1 и 2. Аналогично, левая сторона треугольника может иметь только метки 1 и 3, в то время как правая сторона получает только 2 и 3.
Согласно «лемме» (мини-теореме), если все вышеприведенные условия верны, то во всей сетке перекрещивающихся вершин должен быть хотя бы один треугольник, который имеет разные числа в каждой из трех его точек. На рисунке выше таковых три.
Какое это имеет отношение к ренте? В нахождении этой связи и заключалось прозрение Су.
В статье треугольник переосмысливается как все возможные комбинации цен на комнаты, разделенные между тремя комнатами. Например, точка в верхней части треугольника может представлять собой ситуацию, когда один из соседей оплачивает всю аренду в комнате А, а остальные не платят ничего за оставшиеся две комнаты В и С. Аналогично, точка в левом углу большого треугольника будет представлять собой ситуацию, когда житель комнаты B отдает всю арендную плату. Перемещение в центр треугольника соответствует более справедливым распределениям ренты между тремя комнатами.
Су назначил каждого из жителей дома «владельцем» вершины (ценовой комбинации).
Математический алгоритм решения проблемы Су начинается с вершины за пределами треугольника с вопроса: «Если бы ренту нужно было разделить в соответствии с этой ценовой схемой, в какой комнате ты бы жил?» В зависимости от ответа, этому пункту будет дано число (1, 2 или 3). Затем алгоритм может «переместиться» на новую комбинацию «цена и комната», расположенную глубже внутри треугольника, где тот же вопрос будет задан другому жильцу.
Процедура будет продолжаться до тех пор, пока не будет найдена схема ценообразования, в которой каждый житель согласится жить в разных комнатах при определенных ценах. Графически этот пункт будет существовать в треугольнике, в котором вершины были бы помечены разными цифрами. Помните, что согласно лемме Спернера такой треугольник должен существовать.Таким образом, гармония возможна.
Идея Су стала настоящим открытием. В 2014 году New York Times даже сделал калькулятор арендной платы, используя алгоритм Су.
«Алгоритма справедливости» не существует
Алгоритм Фрэнсиса Су не является единственным способом решить рассматриваемые проблемы.
Хотя первая версия данного калькулятора подражала алгоритму Су, разработанному в 2004 году, результаты, которые он производил, хотя и были свободными от зависти в математическом смысле, не всегда удовлетворяли людей на практике.
«Иногда у вас есть решения, которые удовлетворяют некоторой теоретической модели справедливости, но на практике справедливым вы интуитивно считаете другой расклад», — говорит руководитель проекта Ариэль Прокачча.
Он предлагает следующий пример. Представьте себе трехкомнатную квартиру, разделенную между тремя соседями. Арендная плата составляет 3 доллара. Первый житель заинтересован только в том, чтобы жить в первой комнате, второй интересуется только второй, а их сосед — третьей. Каждый человек согласен заплатить 3 доллара за свою комнату.
Одно из возможных решений заключалось бы в том, чтобы поместить каждого человека в комнату по его выбору и назначить всю сумму арендной платы первому жильцу. Второй и третий жильцы тогда заключат гораздо более выгодную сделку, но у первого соседа по дому нет причин возражать. Он платит 3 доллара — ровно столько, сколько он и хотел, ведь у него нет желания жить в другом месте дома.
«Это решение не должно вызвать зависти на уровне теории, но, очевидно, оно несправедливо», — говорит Прокачча. «Справедливо каждому поселиться в комнате, в которой он хочет жить, и платить 1 доллар».
Именно такого результата и пытается достичь алгоритм Spliddit. Во-первых, он пытается максимизировать разницу между тем, сколько житель готов заплатить за комнату, и тем, сколько он в конечном счете платит. Этот «излишек» показывает, насколько выгодна сделка для каждого жильца, и алгоритм гарантирует, что у каждого жильца в желаемой им комнате он будет выше, чем тот излишек, который у него был бы в другой комнате. Это удовлетворяет условию отсутствия зависти.
Но затем, пытаясь найти «интуитивно справедливое» решение, калькулятор находит комбинацию комнат, которые минимизируют разницу в излишках каждого жильца.
Короче говоря, алгоритм гарантирует, что каждый житель заключает выгодную сделку, которая не может быть намного выгоднее по сравнению с соседями.
С появлением Spliddit поменялся способ расчета тарифов на такси, кредитования, методики разделения задач. Одной из причин создания Spliddit было ознакомление широкой общественности с преимуществами математических методов решения проблем, связанных со справедливым разделением. Точно так же, как метод «Я разделяю, ты выбираешь», его алгоритм используется для урегулирования деловых конфликтов.
Создатель Spliddit надеется, что когда-нибудь компьютеры смогут находить решения в гораздо более сложных проблемах.