Почему именно торт
Разрезание торта — часть области математики, которая изучает справедливое разделение какого-то блага, например земли, времени или ограниченных ресурсов. В этой задаче торт выступает в качестве метафоры. Торты часто неравномерно покрыты кремом или глазурью и неоднородно украшены какими-то дополнительными ингредиентами, например ягодами, фруктами или сладкими фигурками.
Задача усложняется, если принимать во внимание личные предпочтения участников. Кто-то будет рад куску поменьше, зато с вкусной вишенкой сверху, а кто-то останется недоволен большим куском из середины торта, потому что он не покрыт кремом со всех сторон.
Разрезать торт так, чтобы ни один кусок нельзя было считать лучше другого, — и есть суть задачи. При этом разрезание торта предполагает деление именно прямоугольного изделия. Для круглых есть другая задача — про разрезание пирога.
Поначалу учёные пытались решить задачу, учитывая справедливость и пропорциональность, или соразмерность. В последние десятилетия в расчёт также принимают зависть. При идеально разрезанном торте должны получаться куски, каждый из которых будет нравиться тому, кому он достанется.
Дели-и-выбирай
Проще всего разрезать торт на двоих, используя логичный старый метод. Один разрезает, а второй первым выбирает себе кусок. Допустим, торт делят Миша и Лена. Миша разрезает торт на два равных куска, которые оценивает одинаково. Лена выбирает, какой из кусков нравится ей больше, и берёт его себе. Второй кусок достаётся Мише.
Одиночный делящий
После Второй мировой войны мировое сообщество столкнулось с вопросом справедливого разделения земель. На фоне этой проблемы польский учёный Гуго Штейнгауз ввёл задачу разрезания торта. Его подход был основан на старом методе, когда один разрезает, а второй выбирает. Модификация метода состояла в том, что торт делят трое.
Допустим, торт делят Миша, Лена и Кристина. Миша разрезает торт на три куска, оценивая их одинаково, то есть по ⅓ от общей ценности. После этого Лена выбирает, какие куски ей нравятся. Если она одобрит хотя бы два куска, то Кристина может взять любой кусок, какой хочет, а после неё выбирает Лена. Миша получает оставшийся кусок.
Но если Лена и Кристина не одобряют один и тот же кусок, он достаётся Мише, который оценил все три куска одинаково. Оставшиеся два куска объединяют, оценивают в ⅔, а затем Лена и Кристина делят их по методу «дели-и-выбирай».
Последний уменьшивший
Метод Гуго Штейнгауза подходил только для троих. Поэтому он попросил своих студентов Стефана Банаха и Бронислава Кнастера придумать метод, который подходил бы для большего числа людей. Их метод получил название «последний уменьшивший».
Миша отрезает кусок торта, который считает справедливой долей, и передаёт его Лене и Кристине. Они могут обрезать этот кусок, если оценивают его более чем на ⅓ стоимости, или пасовать, то есть не сделать ничего. Если Лена и Кристина отказываются от отрезанного куска, он достаётся Мише. Лена пасует, а Кристина обрезает кусок, который отрезал Миша. Кусок достаётся тому, кто обрезал его последним, то есть Кристине.
После этого обрезок куска добавляется к торту, и его разрезают по методу «дели-и-выбирай». Миша разрезает торт на два куска, которые считает одинаковыми. Из них Лена выбирает кусок, который нравится ей больше. Миша получает оставшийся кусок. Но Кристина, которая вышла из игры на первом раунде, может в итоге считать свой кусок хуже, чем у Лены или Миши.
Метод «последний уменьшивший» можно считать элегантным решением задачи разрезания торта. Каждый участник процесса будет считать свою долю как минимум такой же ценной, как справедливая. Но метод не учитывает зависть, поэтому не идеален. Как и в методе «одиночный делящий», тот, кто выйдет из процесса раньше, может захотеть кусок, который был отрезан позже. Поэтому методы «одиночный делящий» и «последний уменьшивший» называются свободными от зависти, то есть, по сути, несправедливыми.
У метода «последний уменьшивший» есть ещё одно ограничение. Если участников процесса разделения много, то торт, который останется после предыдущих разделений, может быть разрезан слишком большое количество раз.
Метод Селфриджа — Конвея
Математики Джон Селфридж и Джон Конвей задались целью разработать метод разрезания торта на троих, в котором удастся не только добиться пропорциональности, но и избежать зависти любого из участников.
Миша делит торт на три куска, оценивая их одинаково. После этого Лена может либо передать, либо разрезать один из кусков на два. Обрезки откладываются в сторону. Кристина выбирает себе кусок, который ей нравится больше. Затем выбирает Лена, а Миша получает оставшийся кусок.
После этого делятся обрезки. Поскольку Кристина выбрала необрезанный кусок, она разрезает обрезок на три кусочка, которые считает одинаково ценными. Лена выбирает из них первый кусочек, Миша — второй. Кристине достаётся оставшийся кусочек. Метод не вызывает зависти, потому что Лена выбирает первой, Кристина делит обрезок по своему усмотрению, а Миша получает бонусный кусочек к тому, который он отрезал в первом раунде.
«Движущийся нож»
Метод Селфриджа — Конвея подходил только для разрезания торта на троих, так что Стивен Брамс и Алан Д. Тейлор разработали метод для четверых и более участников. Он основан на методе Селфриджа — Конвея, но имеет ограничения, как и все другие методы. Неизвестно, сколько раз придётся разрезать торт. Например, если участников четверо, разрезов может быть минимум три. А если участников очень много, количество разрезов может доходить до миллионов.
Минимальное и максимальное число разрезов
Поскольку задача разрезания торта в первую очередь математическая, многие пытаются подсчитать, сколько раз придётся разрезать торт в зависимости от количества участников процесса.
Математик Ариэль Прокаччиа стал первым, кто понял, как рассчитать минимальное количество шагов справедливого и соразмерного разделения торта без зависти для любого количества людей. Нижняя граница составляет примерно n2, где n — количество участников.
Верхнюю границу определили учёные-компьютерщики Харис Азис и Саймон МакКензи. Сначала они посчитали максимальное количество шагов разрезания торта на четверых, при котором ни у кого не будет зависти к чужому куску. Их алгоритм дал верхнюю границу в 203 шага — много, но правдоподобно.
Затем они подсчитали максимальное количество шагов при разрезании торта без зависти на n людей и получили n^n^n^n^n^n. Так, для пяти участников процесса максимум шагов составит примерно 2×102180. На практике эти несчастные пятеро будут разрезать торт миллиарды раз в секунду в течение 100 триллионов лет. Возможно, в будущем верхнюю границу определят более точно и она составит меньше шагов.
Задача разрезания торта до сих пор актуальна
Мы привели далеко не все методы, их намного больше. Но зачем математики, айтишники и многие другие продолжают решать задачу разрезания торта? У задачи есть множество практических применений. Например, различные методы можно использовать для разделения обязанностей между несколькими людьми. Можно планировать часы работы учителей или смены медицинских работников. Можно делить наследство или имущество при разводе. Задаче разрезания торта уже почти 80 лет, и она давно стала симпатичной головоломкой. А решающие задачу люди стали чем-то вроде отдельного клуба.
Эта статья — пересказ большого материала из «СайенсНьюс» про то, как разрезание торта стало символом небольшого, но очень развитого направления серьёзной математики, а также информатики, экономики и политических наук. Если знаете английский и хотите больше подробностей, почитайте оригинал:
