Пиратская доля

Прежде всего, уточним, что хотя вкусы у пиратов и разные, но здравого смысла они не лишены и ни один из них не оценит заведомо меньшую долю выше, чем заведомо большую (например, если из какой-то части сокровищ что-то отложили, то все пираты понимают, что эта часть стала меньше).

Двоим пиратам разделить добычу между собой легко: сначала один разделит ее пополам (в соответствии со своими предпочтениями), а затем второй выберет из двух половин ту, которая ему больше нравится. Это решение простое, но может быть не очень понятно, как его перенести на случай трех и более пиратов.

Для этого сформулируем ту же идею по-другому. Первый пират разделит сокровище пополам, а затем выберет одну из половин и спросит у второго, не возражает ли тот против такого выбора. Если тот не против, то первый заберет свою половину и оба будут довольны, а если второй против, то первый предложит второму отсыпать лишнее и забрать оставшееся.

С завистливыми пиратами, если их больше двух, все сложнее (когда их двое, то работает решение из подсказки 1). Но начинать с чего-то надо, поэтому одному из них придется поделить добычу на три части. Другие двое будут уверены, что его деление, конечно же, несправедливое. Понять, как действовать дальше, поможет частный случай, когда второй пират считает, что две из трех частей равны друг другу.

Сначала закончим решение задачи для независтливых пиратов, развивая идею из первой подсказки. Пусть их будет трое или больше (то есть n > 2). Действовать им нужно так. Сначала один из них — будем называть его П₁ — отмеряет себе 1/n от добычи (по своим понятиям). Затем он должен по очереди спросить всех остальных, согласны ли они с тем, что отмерено не больше 1/n. Если никто не возразит, то П₁ забирает свою долю. Он доволен, а всем остальным тоже нет повода для расстройства: каждый из них считает, что П₁ отмерил себе меньше 1/n, поэтому им при справедливом дележе остатка достанется даже больше этой доли. Если же кто-то (назовем его П₂) возразит, то П₁ попросит этого несогласного отсыпать лишнее и отдаст ему долю. После этого уже П₂ будет продолжать опрос. Всех, кто уже был опрошен, заново спрашивать не нужно — доля только уменьшилась, и они на нее претендовать не будут. Если появится еще один несогласный (П₃), то он отсыпет лишнее у П₂ и заберет оставшееся сокровище себе. Этот процесс рано или поздно закончится, потому что пиратов конечное число, а число неопрошенных всё время уменьшается. Последний, кто отсыпал лишнее, должен будет забрать долю себе и больше не будет участвовать в дележе. Таким образом, гарантированно получается один довольный пират, а все остальные уверены, что получат не меньше 1/n от всего сокровища.

Оставшиеся n − 1 пиратов повторяют описанную в предыдущем абзаце процедуру, пока всё сокровище не будет поделено между ними.

Теперь разберемся с тремя завистливыми пиратами. Нетрудно понять, почему в этом случае не работает описанный выше способ: после того как первый пират получит свою «треть» сокровища, двое других как-то разделят остаток между собой, но вот первого результат этого раздела может и не устроить.

Допустим, первый пират разделил сокровище на, как он считает, три равноценные части: А, Б и В. Предложим второму расположить эти части по убыванию ценности. Можно считать, что порядок такой: А — самая ценная часть, В — самая дешевая, а Б имеет промежуточную ценность. «Неравенства» здесь нестрогие — части могут иметь одинаковую ценность. Если по мнению второго пирата А = Б, то дальше всё просто: третий выбирает свою долю, у второго в любом случае остается возможность забрать одну из двух более ценных частей, а первый и так считал, что они все три равноценные, поэтому оставшаяся часть его устроит.

А как быть, если по мнению второго А > Б? Тогда попросим его отложить «лишнее» А₁ из части А, чтобы остаток А₂ уравнялся с частью Б. Три части — А₂, Б и В — пираты смогут распределить между собой, чтобы все были довольны. Это делается аналогично случаю А = Б с одним уточнением: если третий забрал часть В, то второго попросим не брать часть Б (ему-то неважно, что брать — часть Б или «похудевшую» часть А), чтобы первый пират не расстроился. Остается поделить излишек А₁. Заметим, что первый точно не будет завидовать тому, кто взял себе А₂, потому что туда не получится добавить больше, чем А₁, то есть больше части А по мнению первого точно не получится. Пусть, для определенности, часть А₂ досталась второму пирату. Тогда попросим третьего поделить излишек А₁ на три равные части, а второго — выбрать из них ту, которая ему больше понравится. Затем первый выберет одну из двух оставшихся частей, а последняя достанется третьему. В итоге все три пирата будут довольны и не будут никому завидовать.

Скорее всего, подобную задачу о честном дележе впервые сформулировал Гуго Штейнгауз (Hugo Steinhaus) еще во время Второй мировой войны. В дальнейшем возникло большое множество задач о справедливом дележе (см. Fair division), в которых варьируются разные параметры: тип «сокровищ» (допускает ли оно непрерывное деление на сколь угодно малые части или его можно разделить лишь на конечное количество частей), количество «пиратов» и их предпочтения, наличие и отсутствие зависти и другие. С точки зрения математики эти задачи относятся к теории меры, теории игр, теории алгоритмов. Некоторые из них являются хорошими моделями для реальных ситуаций, поэтому важны, например, и для экономики. Рассмотренные нами две задачи в англоязычной литературе обычно называют задачами о делении пирога (см. Fair cake-cutting). Решение второй задачи с произвольным числом пиратов можно найти в статье С. Брамса и А. Тейлора An Envy-Free Cake Division Protocol.

Приведу еще одно рассуждение, которое помогает решить нашу первую задачу (на самом деле, оно очень близко к разобранному решению, но гораздо короче). Удобно считать, что пираты делят мешок золотого песка. Один из них начинает отсыпать кучку и сыпет до тех пор, пока кто-нибудь не крикнет «Стоп!» (считая, что отсыпалась как раз доля 1/n). Тот, кто крикнул, забирает кучку себе и выбывает из процесса, а остальные продолжают дальше.

А в завершение расскажу об удивительном (хотя и длинном) решении, основанном на одном комбинаторном факте, который, казалось бы, вообще никак не связан с обсуждаемыми вопросами. Этот факт называется леммой Шпернера и формулируется так:

Дан треугольник, вершины которого покрашены в три цвета. Рассмотрим произвольную триангуляцию этого треугольника. Вершины этой триангуляции покрасим в те же три цвета с единственным условием: вершины триангуляции, которые попали на сторону исходного треугольника, можно красить только в цвет одного из концов этой стороны. Тогда в триангуляции обязательно найдется треугольник с вершинами всех трех цветов.

Чтобы применить эту лемму к задаче о дележе, нужно немного подготовиться. Исключительно для наглядности предположим, что сокровище, которое делят трое пиратов, — это длинная золотая цепь с мелкими звеньями. Примем длину этой цепи за 1 и будем считать, что цепь вытянута в горизонтальный отрезок. Любое разделение этой цепи можно описать парой чисел x и y, обозначающих места, в которых нужно разрезать цепь, чтобы она распалась на три части: x — место первого разреза, y — место второго (считаем, что разрезы могут совпадать — тогда кому-то достается «пустой» кусок цепи, то есть не достается ничего). Тогда выполняются неравенства 0 ≤ x ≤ y ≤ 1. На декартовой плоскости эти неравенства задают треугольник, ограниченный прямыми x = 0, y = 1, y = x. Обратите внимание, что у нас уже появился треугольник! Обозначим его Т. Каждая точка в этом треугольнике задает разделение цепи. Например, точка с координатами (1/3, 2/3) соответствует делению на три равных куска, а точка с координатами (1/2, 1/2) — такому делению: половина, «пустой» кусок, еще половина. Вершины исходного треугольника Т имеют координаты (0, 0), (0, 1), (1, 1) и дают «вырожденные» разрезания, в которых получается только один непустой кусок. Например, вершине (0, 0) соответствует такое разделение: первые два куска пустые, а третий кусок — это вся цепь.

Триангулируем треугольник Т и введем раскраску вершин триангуляции следующим образом. Сначала рядом c этими вершинами напишем имена пиратов так, чтобы рядом с вершинами каждого треугольничка стояли все три имени (поскольку мы вольны в выборе триангуляции, то выберем такую, чтобы это было возможно; а вы придумайте триангуляцию, вершины которой так подписать не получится). Можно сказать, что у каждой вершины триангуляции есть владелец — пират, чье имя написано рядом с вершиной. Пройдем по всем вершинам и спросим их владельцев, какой (по порядку) из кусков соответствующих разделений цепи они бы выбрали себе: левый, средний или правый. В качестве цвета используем характеристики «выбор левого куска», «выбор среднего куска», «выбор правого куска», их как раз три. Убедитесь, что такая «раскраска», несмотря на всю странность, удовлетворяет условиям леммы Шпернера (а именно, что вершины триангуляции, попавшие на стороны исходного треугольника, будут покрашены в цвет одного из концов своей стороны). Тогда, по лемме, обязательно найдется треугольничек, вершины которого будут покрашены в разные цвета. Этот треугольничек можно снова триангулировать, причем так же, как и исходный треугольник. Вершины триангуляции можно покрасить в те же самые три «цвета» и получить еще один, уже совсем маленький, треугольничек с вершинами всех трех цветов. Продолжая этот процесс, получим последовательность вложенных треугольников, которая сходится к одной точке (это двумерный аналог принципа вложенных отрезков). Эта точка и дает нужное разделение, потому что каждый из пиратов выберет свой кусок цепи. Более того, это разделение подойдет и завистливым пиратам.

При подготовке этой задачи были использованы материалы 11-й Летней конференции Турнира городов (см. статью И. Иванова-Погодаева, А. Канель-Белова, С. Кублановского и А. Малистова «Задача о разбойниках» в книге Н. Константинова и Б. Френкина «Летние конференции Турнира городов. Избранные материалы. Выпуск 1»).