|
И вот как описывают это Бизам и Герцег в книге Многоцветная логика:
70. СПРАВЕДЛИВЫЙ РАЗДЕЛ
Прежде всего заметим, что речь пойдет о разделе на равные части (такой способ раздела справедлив не всегда). Трем золотоискателям с Аляски, остановившимся в придорожной гостинице, требовалось разделить перед расставанием намытый ими золотой песок именно на 3 равные части: каждый из золотоискателей вложил в добычу золота ровно 1/3 общих затрат труда и поэтому не без основания претендовал на 1/3 золотого песка, считая, что такой раздел был бы вполне справедливым.
Но каким образом разделить кучу золотого песка на 3 равные части? Этого золотоискатели не знали. Весы имелись лишь на приемном пункте, но до него было несколько дней пути. (Впрочем, тем, кто добрался бы до приемного пункта, весы вряд ли понадобились бы, поскольку делить надо было бы уже не золотой песок, а доллары.) Делить золото «на глазок» никому не хотелось.
Стали совещаться, что делать.
Если бы золотоискателей было двое, поступить можно было бы довольно просто: один разделил бы золотой песок на 2 части, а другой выбрал бы себе ту из частей, которая ему больше нравится. При таком способе раздела ни у кого из золотоискателей не могло бы возникнуть никаких претензий к своему напарнику.
Но золотоискателей было не двое, а трое, вопрос о справедливом разделе золотого песка оставался неясным, и атмосфера постепенно начала накаляться. Наконец один из золотоискателей попытался найти выход из создавшегося неприятного положения.
— Джентльмены,—обратился он к своим компаньонам,—чем, собственно говоря, так хорош справедливый раздел на двоих, когда один делит, а другой выбирает? Очевидно, тем, что каждому участнику раздела предоставляется возможность взять себе не меньше золотого песка, чем достанется другому. Тот, кто при таком способе раздела все же получит меньше золота, чем его партнер, может винить только самого себя: если он делил, то ему следовало делить на равные части, а если он выбирал, то ему незачем было оставлять себе меньшую часть. Именно так нам и следует поступить с золотым песком.
— Верно говоришь, старина,—одобрил его выступление другой золотоискатель, — только я никак не возьму в толк, как же все-таки нам надо поступить, чтобы каждый мог выбрать себе долю песка, не меньшую, чем у других?
Ответа на такой вопрос по существу не последовало: рецепта справедливого раздела на троих не знал никто.
Спросить совета, как надлежит действовать, чтобы соблюсти основное условие справедливого раздела (выделенное курсивом)—предоставить каждому возможность получить не менее 1/3 золотого песка (разумеется, если сам участник раздела не допустит какой-нибудь досадной оплошности) даже в том случае, если двое партнеров вступят в тайный сговор и будут всячески стремиться урезать долю третьего партнера в свою пользу, — золотоискателям было не у кого.
Разумеется, о применении при разделе золотого песка грубой силы не могло быть и речи. Кольты были отложены в сторону, и каждый из трех золотоискателей давно научился с уважением относиться к кулакам другого. К тому же затевать потасовку было небезопасно, поскольку шериф находился неподалеку: он, как всегда, коротал время за стаканом виски в соседнем питейном заведении. '
Как разделить золотой песок?
(Способ раздела должен гарантировать, что каждому из золотоискателей достанется не менее '/з песка. Если все же кому-нибудь достанется золотого песка больше, то причину несправедливости надлежит искать не,в способе, которым делили песок.)
71. ИХ СТАЛО ЧЕТВЕРО
Как поступить, если (при обстоятельствах, описанных в предыдущей задаче) золотой песок требуется разделить не между тремя, а между четырьмя золотоискателями?
72. ОТ ДВУХ ДО...
Обобщите способ «справедливого раздела», изложенный в двух предыдущих задачах, на случай произвольного числа золотоискателей.
Решение
70. СПРАВЕДЛИВЫЙ РАЗДЕЛ
[Пусть один из золотоискателей делит намытый песок, а двое других выбирают себе долю по вкусу. Необходимо следить лишь за тем, чтобы каждый из них выбирал свою часть песка независимо от другого. Это позволит пресечь все попытки создания «коалиций», когда двое сговариваются и действуют против третьего. Разумеется, решение задачи необходимо найти и в том случае, если двое злоумышленников все же сговорятся между собой.]
Назовем того из трех золотоискателей, кто делит кучу намытого песка на 3 равные части, «раздатчиком», а тех двух, кто. выбирает, какую часть взять себе, «приемщиками». Каждый из двух приемщиков отмечает те из трех кучек, которые, по его мнению, удовлетворяют условиям справедливого раздела, то есть составляют 1/3 всего намытого песка. По крайней мере 1 кучка непременно будет отмечена (поскольку все 3 кучки не могут содержать менее 1/3 песка).
а. Если найдутся 2 различные кучки, одну из которых сочтет приемлемой один, а другую — другой приемщик, то раздел золотого песка можно считать завершенным: каждый приемщик берет себе ту из двух кучек, которая ему приглянулась, а третий золотоискатель, исполнявший обязанности раздатчика и поэтому лишенный права выбора, забирает оставшуюся кучку золотого песка.
б. Предположим теперь, что найти 2 такие различные кучки не удалось. Это означает следующее: каждый из приемщиков счел, что условиям справедливого раздела удовлетворяет лишь 1 из 3 кучек, причем оба приемщика отметили одну и ту же кучку золотого песка.
В этом случае 2 остальные кучки песка с точки зрения обоих приемщиков неприемлемы, то есть каждая кучка содержит менее ,1/3 намытого совместными усилиями песка. Следовательно, любую из этих кучек- можно оставить раздатчику. Поскольку она составляет менее 1/3 всего песка, то в двух остальных кучках содержится более 2/3 всего золотого песка. Разделив их между собой по уже известному рецепту справедливого раздела на двоих, приемщики тем самым завершат справедливый раздел на троих.
[После того как раздатчик получит свою долю золотого песка, один из приемщиков выступит в роли нового раздатчика; он разделит оставшийся золотой песок на две части, а второй приемщик выберет ту из частей, которая ему больше понравится.] Указанный способ раздела позволяет каждому из трех золотоискателей получить не менее 1/3 намытого песка.
Интересы раздатчика не будут ущемлены, если он разделит песок на 3 равные части, каждая из которых содержит 1/3 общего количества намытого золота. (В противном случае ему не остается ничего другого, как обижаться на самого себя.)
Приемщики не должны выбирать ту кучку, которую им не хотелось бы оставлять себе. Если раздатчик разделил песок на неравные кучки, то ему следует отдать ту кучку, от которой откажутся оба приемщика (то есть ту, которая содержит менее 1/3 золотого песка). Разделив между собой оставшуюся часть песка, приемщики получат не менее 1/3 всего намытого золота.
71. ИХ СТАЛО ЧЕТВЕРО
Последовательность действий по существу указана в решении предыдущей задачи. Если после первой же попытки каждый не получит справедливой (то есть удовлетворяющей всех приемщиков) доли, то по крайней мере один золотоискатель заведомо получит «то, что ему причитается» (по единодушному мнению всех приемщиков). Поскольку число золотоискателей, не получивших своей доли, после этого не будет превышать 3, то для справедливого раздела остальной части золотого песка они могут воспользоваться готовым рецептом.
Итак, один из золотоискателей («раздатчик») делит весь золотой песок на 4 равные части, а трое других («приемщики») выбирают ту из кучек, которая им понравится. Каждый из приемщиков отмечает те из 4 кучек, которые, по его мнению, удовлетворяют условиям справедливого раздела (то есть содержат не менее 1/4 намытого золота). По крайней мере 1 из 4 кучек будет отмечена всеми приемщиками.
Далее возможны 3 случая.
1. Какая-то кучка не отмечена одним из приемщиков. Эту кучку приемщики должны оставить раздатчику, а золотой песок из трех остальных кучек разделить заново между собой так, как это сделали трое золотоискателей в решении предыдущей задачи.
II. Ни одна кучка золотого песка не осталась без отметки хотя бы одного из приемщиков, но какая-то кучка отмечена лишь одним приемщиком. Тогда эту кучку нужно отдать тому приемщику, который ее отметил, и задача снова сведется к предыдущей задаче (о справедливом разделе золотого песка между тремя золотоискателями).
III. Все кучки песка отмечены по крайней мере двумя приемщиками. Общее число «отметок» в этом случае не меньше 2 х 4 = 8. Следовательно, заведомо найдется приемщик А, поставивший по крайней мере 3 отметки (в противном случае общее число отметок не превышало бы 3 х 2 = 6), а какой-то из двух остальных приемщиков (назовем его Б) должен был поставить по крайней мере 2 отметки (в противном случае общее число отметок не превосходило бы 4 + 2 х 1 = 6, поскольку А не мог отметить более 4 кучек). Следовательно, если третий приемщик В получит ту кучку, которую он отметил (по крайней мере одна такая кучка непременно найдется), то для приемщика Б останется по крайней мере 1 из отмеченных им 2 кучек, а после того, как Б заберет свою долю, для А останется по крайней мере 1 из отмеченных им кучек. Четвертуй кучку, которая останется после того, как все приемщики возьмут себе по кучке золотого песка, можно с их общего согласия оставить раздатчику. Тем самым справедливый раздел золотого песка на 4 части будет завершен.
Нам осталось еще показать, что при таком способе раздела каждый из 4 золотоискателей может получить не менее 1/4 намытого ими золотого песка. Для этого необходимо лишь слово в слово повторить два последних абзаца из решения предыдущей задачи, заменив 1/3 на 1/4.
72. ОТ ДВУХ ДО...
На первый взгляд кажется, что решения двух предыдущих задач должны допускать обобщение на любое число участников раздела. Однако довольно скоро выясняется, что это не так. Если говорить о способе раздела, использованном в решении задачи 70, то нетрудно видеть, что при увеличении числа участников справедливого раздела сложность его быстро возрастает, поэтому от обобщения его на случай произвольного числа участников раздела разумнее отказаться. Рассуждения, использованные нами в решении задачи 71, оставляют кое-какие надежды на обобщение, но этим надеждам не суждено сбыться, поскольку в III случае эти рассуждения не проходят, даже если число участников раздела достигает 5.
Отсюда напрашивается вывод, что обобщение способов справедливого раздела на случай произвольного числа участников станет возможно лишь при условии, если ранее использованные нами методы удастся подвергнуть коренной «реконструкции», избежав при этом чрезмерного усложнения. Кое-какие возможности открылись бы перед нами, если бы, например, «раздатчик» заботился не о всех «кучках» сразу, а сосредоточил свое внимание на какой-нибудь одной части.
Пусть n — число участников раздела. Тогда каждый из них должен получить 1/n всего песка. Справедливый раздел золотоискатели могут осуществить следующим образом.
Прежде всего каждый золотоискатель получает свой номер от 1 до n (порядок, в котором производится нумерация участников раздела, несуществен). Затем они переносят весь золотой песок в какое-нибудь помещение, насыпают его посредине, а сами собираются на левой или на правой половине помещения (обозначим ту половину, на которой собрались золотоискатели, А). Первый золотоискатель подходит к куче золотого песка, отсыпает из нее часть, составляющую, по его мнению, 1/n общего количества песка, и становится рядом с ней. После этого он опрашивает поочередно в порядке возрастания номеров всех золотоискателей, находящихся на половине А (то есть начинает с золотоискателя с наименьшим номером и кончает золотоискателем с наибольшим номером, не пропуская никакого), согласны ли они, чтобы он взял себе ту часть песка, рядом с которой стоит. Те, кто не возражает против этого, переходят на другую половину помещения, которую обозначим В.
Если все согласны, то золотоискатель, стоящий посреди помещения рядом с отсыпанной им частью песка, получает ее.
Если же имеются возражения, то среди тех золотоискателей, кто не согласен, всегда можно найти человека с наименьшим номером. Он первым заявил простеет. Пусть его номер равен Т1 Возражение Т1-го золотоискателя, очевидно, означает, что, по его мнению, золотоискатель, стоящий посреди помещения, отсыпал себе больше, чем 1/n всего песка: Т1-й золотоискатель, должно быть, хотел бы, чтобы эта кучка досталась ему. Более того, поскольку, по его мнению, она чрезмерно велика, из нее необходимо отсыпать «излишек» песка—то количество, на которое она превышает 1\ n. Отсыпав указанное Т1-м золотоискателем количество золотого песка в оставшуюся кучу (содержащую (n - 1)/n намытого золотоискателями песка), тот, кто стоял посреди помещения, переходит на половину В, а его место рядом с «более справедливой» порцией песка занимает Т1-й золотоискатель.
Он продолжает опрашивать тех, кто еще остался на половине А, и если поступает хотя бы один протест, все повторяется сначала .(то есть он сам переходит на половину В, а его место занимает очередной «несогласный» с наименьшим номером) до тех пор, пока на половине А остается хотя бы 1 человек. Рано или поздно наступит такой момент, когда золотоискатель будет стоять посреди помещения рядом с горкой золотого песка, отсыпанного из общей кучи, а все остальные золотоискатели окажутся на половине В. Тогда золотоискатель, стоящий посреди помещения, получает ту, горку золотого песка, рядом с которой он находится, а золотоискатели, собравшиеся на половине В (их n - 1 человек) повторяют всю, описанную выше процедуру с оставшейся кучей золотого песка. После второго «цикла» останется n - 1 золотоискателей, после следующего (третьего) — n - 3 золотоискателей и так далее. Всю процедуру необходимо повторять до тех пор, пока каждый золотоискатель не получит причитающуюся ему долю золотого песка.
Нам остается еще проверить, правильно ли полученное решение и удовлетворяет ли оно условию справедливого раздела, выделенному в условиях задачи 70 курсивом: может ли каждый участник раздела получить не менее 1/n общего количества золотого песка (или, если он все же получит меньшую долю, быть уверенным в том, что это произошло по его собственной оплошности)?
1. Тот золотоискатель (обозначим его Т), который последним останется посреди помещения рядом с горкой отсыпанного из общей кучи золотого песка и получит ее, в то время как все остальные золотоискатели соберутся на половине В, не имеет оснований быть недовольным разделом, поскольку он сам выберет ту горку песка, которая ему достанется.
2. На половине В соберутся те золотоискатели, которые согласны либо с тем, чтобы Т получил свою горку песка, либо с тем, чтобы кто-нибудь другой получил большую порцию золотого песка. Следовательно, даже. если золотоискатель Т получит слишком много песка (а им самим для последующего раздела останется слишком мало золотого песка), то виноваты в этом будут лишь они сами.
3. Не могут пожаловаться и те, кто отсыпал себе порцию золотого песка, вызвавшую возражения у других золотоискателей: поскольку себе они отсыпали больше песка, чем досталось золотоискателю Т, то его долю они не могут назвать чрезмерной.
Примечание 1. Описанный в решении способ справедливого раздела позволяет осуществить разбиение любого исходного множества на n (в принципе равных частей). Это означает, что оставшаяся после первого разбиения часть множества содержит, не одну, а n - 1 часть. Хотя такое «уменьшение» множества в общем ничего не меняет, тем не менее «отщепление» 1/n исходного множества позволяет легче оценить «на глазок» его величину. Более того, отщепленную часть можно использовать при дальнейшем разбиении множества (внося в случае необходимости соответствующие поправки).
Примечание 2. Предложенный способ справедливого раздела коренным образом отличается от тех, которые были использованы в решениях задач 70 и 71. Он позволяет разделить кучу золотого песка на 3 и на 4 части, но не так, как это было сделано в решениях задач 70 и 71, а совершенно иначе. Следовательно, этот способ позволяет получить новые решения задачи о справедливом разделе для 3 и 4 человек. Что же касается случая, когда раздел требуется произвести между двумя людьми, то здесь оба метода совпадают, поскольку в основу нового метода положен именно тот основной принцип, который был извлечен из известного способа традиционного раздела между двумя людьми (в задаче 70 этот принцип выделен курсивом).
Примечание 3. Разумеется, было бы нетрудно применить новый способ справедливого раздела к решению задач 70 и 71, но это не имело бы особого смысла: известно, что если число лиц, участвующих в разделе, равно 3 или 4, то приведенные нами решения задач 70 и 71 проще. Новый способ справедливого раздела отличается лишь большей принципиальной простотой, но при попытке практического применения оказывается весьма громоздким. Почти единственное его преимущество состоит в том, что он применим при любом числе участников раздела.
Примечание 4. Как показывает накопленный нами опыт не все методы решения (и доказательства) допускают обобщение, поэтому от некоторых «соблазнов», возникающих при решении той или иной задачи, приходится отказаться. Продвижение вперед часто зависит от того, удастся ли вырваться из привычного хода рассуждений. Поэтому рассчитывать на то, что заданную задачу непременно удастся решить, весьма трудно.
|
.