Три Закона Гработехники
АрхивВ "Компьютерре" #5 за этот год я опубликовал логическую задачу о двадцати грабителях - условие и ответ. Однако этот ответ, видимо, оказался настолько неожиданным, что я до сих пор получаю письма с просьбами прислать полное решение задачи или разобрать его на страницах журнала.
Итак, напоминаю условие:
Двадцать грабителей взяли банк - 20 миллионов - и решили поделить деньги. Метод дележки такой: они становятся в ряд, и первый предлагает свой способ дележа. Все голосуют. Если "за" высказались 50 процентов или больше, этот способ принимается, если меньше - первого грабителя убивают, а второй предлагает свой способ. И так далее.
При голосовании каждый грабитель исходит только из трех соображений (в порядке убывания приоритета):
А. Надо остаться живым.
Б. Надо получить как можно больше денег.
В. Надо сохранить в живых как можно больше грабителей (дело-то не последнее!).
Каким будут распределены деньги, сколько грабителей останется в живых и как они проголосуют? (Разумеется, как обычно в таких задачах, предполагается, что все они умеют безупречно мыслить логически. Этакие грабители-интеллектуалы...)
На первый взгляд, кажется, что первому грабителю (#1) надо хорошо "подмаслить" девятерых "коллег" - лучше всего тех, кто ближе к началу очереди. (Те, кто в конце, рассчитывают на большую долю: у них больше шансов отправить к праотцам предыдущих.) Возможно, что удовлетворить их аппетиты не удастся - тогда дело первого грабителя - труба, а возможно, какая-то часть денег и ему достанется...
На самом же деле вся демократия закончится после первого же голосования: грабитель #1 предложит отдать все деньги ему, при голосовании его поддержат грабители #3, #4, ..., #20 и лишь грабитель #2 проголосует против. В результате, естественно, все останутся живы, а 20 миллионов перейдут во владение грабителя #1.
Почему именно так, а не иначе? Давайте посмотрим, что произошло бы в том случае, если бы грабителей было не 20, а меньше.
Ситуация 1. Один грабитель.
Ему ничего не остается, как предложить себе отдать все деньги себе же, поскольку других вариантов просто нет. После этого он проголосует "за" и хладнокровно заберет все деньги, поскольку именно в этом случае будут максимально удовлетворены все три его заветных желания - А, Б и В.
Ситуация 2. Два грабителя.
В этом случае у грабителя #1 есть отличный способ получить максимальную выгоду: он предлагает отдать все деньги ему, поддерживает при голосовании собственное предложение, и выигрывает голосование решающими 50 процентами.
Чувствуете тенденцию? Давайте-ка теперь рассмотрим еще более любопытную ситуацию.
Ситуация 3. Три грабителя.
Заткнем уши в тот момент, когда грабитель #1 будет высказывать свое предложение о распределении денег. Заткнули? Теперь поразмышляем.
Грабитель #3 не дурак, и он соображает, что в случае провала предложения, сделанного грабителем #1, тот будет убит. Их дружная компания попадет в ситуацию 2, финал которой его мало устраивает: #1 убит, #2 при деньгах, а он - #3 - жив, но без денег. Но может быть, поддержка предложения грабителя #1 обернется для #3 еще худшими последствиями? Нет, в худшем случае он тоже ничего не получит, но зато неплохой парень #1 останется жив. Поэтому, как ни крути, #3 выиграет больше, если предложение грабителя #1 будет принято.
Итак, #3 непременно проголосует "за" - независимо от того, что именно предложит #1.
Но #1 не глупее нас с вами, он тоже догадается об этом. А тогда он поймет, что у него есть отличный (и единственный!) способ загрести все деньги: предложить соратникам добровольно отдать их ему и выиграть голосование, заручившись гарантированной поддержкой #3. Так он, разумеется, и поступит.
Конечно, #2 тоже не глуп. Он, как и мы, сообразит, что #1 и #3 проголосуют "за", погрустнеет и, смирившись с потерей денег, мрачно проголосует "против".
Итак, финал: грабитель #1 предлагает отдать деньги ему, грабитель #3 его поддерживает, а #2 с кислой миной голосует "против". А теперь - внимание! Барабанная дробь...
Ситуация 20. Двадцать грабителей.
Мы воспользуемся одним замечательным изобретением, облегчившим многие тысячи доказательств. Это изобретение - математическая индукция.
Предположим, что мы с вами очень умны - настолько, что сумели разобрать ситуацию n-1. Предположив это, мы должны всего лишь разобрать ситуацию n. А поскольку ситуации 1, 2 и 3 нами уже рассмотрены, мы можем с полным основанием считать, что n > 3.
Итак, грабитель N1 - первый из наших n отчаянных парней - высказал свое предложение о разделе денег. И теперь, если его предложение не будет поддержано, бедняга покинет нас, и мы окажемся в ситуации n-1.
Она, как известно нам с вами, а значит и всем умницам-грабителям, максимально выгодна грабителю #2 (который станет тогда новым #1), но для всех остальных ее финал менее привлекателен, чем предложение грабителя #1, ибо денег они не получат все равно, а друга #1 потеряют. Поэтому все остальные (кроме #2) голосуют "за", оставляя #1 в живых и с деньгами.
Немного сомнений...
Если я вас не совсем убедил - я вас поздравляю: все действительно не так просто, как я попытался это представить. Давайте-ка рассмотрим ситуацию 4.
Грабитель #1 первым из четырех высказал свое предложение о разделе денег. И теперь, если его предложение не будет поддержано, бедняга покинет этот мир, и бандитов останется трое.
Но разве можно сделать однозначный вывод о том, что #3 и #4 поддержат его, проголосовав "за"? Ведь каждый из них может посчитать, что и без его голоса 50 процентов голосов наберется, а значит, можно голосовать непредсказуемо (например, подкинуть монетку). И если оба подкинут монетку, положившись на голос другого, то жизненный путь #1 вполне может завершиться раньше, чем ему того хотелось бы...
Так как же будет на самом деле?
Может ли кто-то из грабителей позволить себе бросать монетку? Может ли #1 ни с кем не поделиться?
По условию, есть Три Закона Гработехники - А, Б и В. Грабители руководствуются ими и только ими, причем приоритет первого закона (А) бесконечно выше, чем приоритет второго (Б), а приоритет второго закона бесконечно выше приоритета третьего (В). Причем предполагается, что все действующие лица имеют бесконечно большой IQ. Кроме того, ситуация бесконечно рефлексивна: каждый грабитель знает, что остальные грабители руководствуются тремя законами и только ими; каждый грабитель знает, что каждый грабитель знает, что остальные грабители руководствуются тремя законами, и т. д.
Рассмотрим снова ситуацию 3. Как может рассуждать #3?
- Для меня выполнение первого закона (сохранение жизни) гарантировано, поэтому я должен позаботиться о втором законе - сорвать как можно больший куш. Получить его я смогу единственным образом: шантажируя грабителя #1 тем, что если он не поделится, я его убью (мой голос решающий, его вполне хватит для убийства). Если #1, логически рассуждая, придет к выводу, что для спасения своей шкуры он должен со мной поделиться, то я получу хотя бы что-то. Третий закон здесь пока ни при чем, поскольку ситуация подконтрольна второму закону, а он имеет больший приоритет.
А как рассуждает #1?
- Я должен прежде всего позаботиться о спасении своей жизни. Для этого надо обязательно заручиться голосом #3. Ясно, что он хочет, чтобы я с ним поделился. Если я позволю себе вступить с ним в переговоры о величине этой суммы, то возможно, что мы сумеем договориться (например, для этого достаточно отдать ему все деньги). Но само мое вступление в эти переговоры угрожает моей жизни (первому закону): я заставляю #3 подчиняться второму закону, а не третьему! Поэтому единственный шанс гарантировать себе жизнь - это дать грабителю #3 твердо понять, что ни при каких условиях он не получит ничего. После этого второй закон для #3 оказывается выключенным, а в действие вступает третий закон, заставляющий #3 сохранить мне жизнь. Итак, я обязан поставить на голосование предложение, по которому все деньги достаются мне.
Таким образом, предложение #1: "все деньги - мне" продиктовано не вторым законом, а первым. И после того, как это предложение вынесено на голосование (неважно, какие переговоры велись до этого), #3 должен принять решение о том, как ему проголосовать. Его жизни (первому закону) ничего не угрожает; второму - тоже (предложение #1 уже сделано, и при всех возможных исходах #3 не получит ничего). Поэтому для #3 вступает в действие третий закон, и он голосует "за".
То же самое будет и в ситуации с двадцатью грабителями (предложение #1 о распределении денег продиктовано не вторым законом, как можно было бы предположить, а первым: только такое предложение гарантирует ему жизнь, ибо отключает второй закон и включает третий для каждого из остальных грабителей).
Следовательно, наше решение было полностью правильным, а предположения о бросании монеток грабителями - противоречащими условиям (если грабители на самом деле придерживаются Трех Законов, то все их поведение при голосованиях детерминировано).
P.S. При подготовке статьи автор использовал некоторые письма, опубликованные в июле 1996 года в конференции relcom.rec.puzzles, где обсуждалась эта задача. Большое спасибо всем участникам той дискуссии и особенно Александру Гутману (Новосибирск) и Евгению Косенко (Киев).
