20 грабителей Опции

[Гость_Ёрофеич_*]

20 грабителей взяли банк - 20 лимонов и решили поделить деньги.
Метод дележки такой. Выстроились в ряд и первый предлагает способ дележки. Затем голосуют. если за 50% или больше, то способ принимается, если меньше то первого убивают, и второй предлагает свой способ. И так далее.

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

каким будет распределение денег?
сколько грабителей останется в живых?
как они проголосуют?

[SiMM]

Если забыть о внутренних тёрках - в живых останется 10. При правильной стратегии первого.

[galaxymaster]

Об ответе рассказывает автор загадки -- Константин Кноп:
---
© Константин Кноп, 1997-98. All rights reserved.
Три Закона Гработехники

Не так давно ("Компьютерра" #5(182)) я опубликовал логическую задачу о двадцати грабителях - условие и ответ. Однако этот ответ, видимо, оказался настолько неожиданным, что я до сих пор получаю письма с просьбами прислать полное решение задачи или разобрать его на страницах журнала.

* * *
Итак, напоминаю условие:
Двадцать грабителей взяли банк - 20 миллионов - и решили поделить деньги. Метод дележки такой: они становятся в ряд, и первый предлагает свой способ дележа. Все голосуют. Если "за" высказались 50% или больше, этот способ принимается, если меньше - первого грабителя убивают, а второй предлагает свой способ. И т.д.

При голосовании каждый грабитель исходит только из трех соображений (в порядке убывания приоритета):
А. Надо остаться живым
Б. Надо получить побольше денег
В. Надо сохранить в живых как можно больше грабителей (дело-то не последнее!)

Каким будет распределение денег? Сколько грабителей останутся в живых и как они проголосуют? (Разумеется, как обычно в логических задачах, предполагается, что все они умеют безупречно мыслить логически. Этакие грабители-интеллектуалы...)

* * *
На первый взгляд, кажется, что первому грабителю (N1) надо хорошо подмаслить девятерых "коллег" - лучше всего тех, кто ближе к началу очереди. (Те, кто в конце, рассчитывают на большую долю: у них больше шансов отправить к праотцам предыдущих). Возможно, что удовлетворить их аппетиты не удастся - тогда дело первого грабителя - труба, а возможно, какая-то часть денег и ему достанется...

На самом же деле вся демократия закончится после первого же голосования: грабитель N1 предложит отдать все деньги ему, при голосовании его поддержат грабители N3, N4, ..., N20 и лишь грабитель N2 проголосует против. В результате, естественно, все останутся живы, а 20 миллионов перейдут во владение грабителя N1.

Почему именно так, а не иначе? Давайте посмотрим, что произошло бы в том случае, если бы грабителей было не 20, а меньше.

Ситуация 1. Один грабитель
Ему ничего не остается, как предложить себе отдать все деньги себе, поскольку других вариантов просто нет. После этого он проголосует "за" и хладнокровно заберет все деньги, поскольку именно в этом случае будут максимально удовлетворены все три его заветных желания - А, Б и В.

Ситуация 2. Два грабителя
В этом случае у грабителя N1 есть отличный способ получить максимальную выгоду: он предлагает отдать все деньги ему, поддерживает при голосовании собственное предложение, и выигрывает голосование решающими 50 процентами.

Чувствуете тенденцию? Давайте-ка теперь рассмотрим еще более любопытную ситуацию.

Ситуация 3. Три грабителя
Заткнем уши в тот момент, когда грабитель N1 будет высказывать свое предложение о распределении денег. Заткнули? Теперь поразмышляем.

Грабитель N3 - не дурак, и он соображает, что в случае провала предложения, сделанного грабителем N1, тот будет убит. Их дружная компания попадет в ситуацию 2, финал которой его мало устраивает: N1 убит, N2 при деньгах, а он - N3 - жив, но без денег. Но, может быть, поддержка предложения грабителя N1 обернется для N3 еще худшими последствиями? Нет, в худшем случае он тоже ничего не получит, но зато неплохой парень N1 останется жив. Поэтому, как ни крути, N3 выиграет больше, если предложение грабителя N1 будет принято.

Итак N3 непременно проголосует "за" - вне зависимости от того, что именно предложит N1.

Но N1 не глупее нас с вами, он тоже догадается об этом. А тогда он поймет, что у него есть отличный (и единственный!) способ загрести все деньги - предложить соратникам добровольно отдать их ему и выиграть голосование, заручившись гарантированной поддержкой N3. Так он, разумеется, и поступит.

Конечно, N2 тоже не глуп. Он, как и мы, сообразит, что N1 и N3 проголосуют "за", погрустнеет и, смирившись с потерей денег, мрачно проголосует ничего не значащим голосом "против".

Итак, финал: грабитель N1 предлагает отдать деньги ему, грабитель N3 его поддерживает, а N2 с кислой миной голосует "против".
А теперь - внимание! Барабанная дробь...

Ситуация 20: Двадцать грабителей
Мы воспользуемся одним замечательным изобретением, облегчившим многие тысячи доказательств. Это изобретение - математическая индукция.

Предположим, что мы с вами очень умны - настолько, что сумели разобрать ситуацию n-1. Предположив это, мы должны всего лишь разобрать ситуацию n. А поскольку ситуации 1, 2 и 3 нами уже рассмотрены, мы можем с полным основанием считать, что n>3.

Итак, грабитель N1 - первый из наших n отчаянных парней - высказал свое предложение о разделе денег. И теперь, если его предложение не будет поддержано, бедняга покинет нас, и мы окажемся в ситуации n-1.

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

Немного сомнений...
Если я Вас не совсем убедил - я поздравляю Вас: все действительно не так просто, как я попытался это представить. Давайте-ка рассмотрим ситуацию 4.

Грабитель N1 - первый из четырех - высказал свое предложение о разделе денег. И теперь, если его предложение не будет поддержано, бедняга покинет этот мир, и бандитов останется трое.

Но разве можно сделать однозначный вывод о том, что N3 и N4 поддержат его - проголосуют "за"? Ведь каждый из них может посчитать, что и без его голоса 50% голосов наберется, а значит, можно голосовать непредсказуемо (например, подкинуть монетку). И если оба подкинут монетку, положившись на голос другого, то жизненный путь N1 вполне может завершиться раньше, чем ему того хотелось бы...

Так как же будет на самом деле?
Может ли кто-то из грабителей позволить себе бросать монетку? Может ли N1 ни с кем не поделиться?

По условию, есть Три Закона Гработехники - А, Б и В. Грабители руководствуются ими, и только ими, причем приоритет Первого Закона (А) бесконечно выше, чем приоритет Второго (Б), а приоритет Второго Закона бесконечно выше приоритета Третьего (В). Как обычно в логических задачах, предполагается, что все действующие лица имеют бесконечно большой IQ. Кроме того, ситуация бесконечно рефлексивна: каждый грабитель знает, что остальные грабители руководствуются Тремя Законами и только ими; каждый грабитель знает, что каждый грабитель знает, что остальные грабители руководствуются Тремя Законами и т.д.

Рассмотрим снова ситуацию 3. Как может рассуждать N3?

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

А как рассуждает N1?

"Я должен прежде всего позаботиться о спасении своей жизни. Для этого надо обязательно заручиться голосом N3. Ясно, что он хочет, чтобы я с ним поделился. Если я позволю себе вступить с ним в переговоры о величине этой суммы, то возможно, мы сумеем договориться (например, для этого достаточно отдать ему все деньги). Но само мое вступление в эти переговоры угрожает моей жизни (Первому Закону): я заставляю N3 подчиняться Второму Закону, а не Третьему! Поэтому единственный шанс гарантировать себе жизнь - это дать грабителю N3 твердо понять, что ни при каких условиях он не получит ничего. После этого Второй Закон для N3 оказывается выключенным, а в действие вступает Третий Закон, заставляющий N3 сохранить мне жизнь. Итак, я обязан поставить на голосование предложение, по которому все деньги достаются мне."

Таким образом, предложение N1 "все деньги - мне" продиктовано не Вторым Законом, а Первым. И после того, как это предложение вынесено на голосование (неважно, какие переговоры велись до этого), N3 должен принять решение о том, как ему проголосовать. Его жизни (Первому Закону) ничего не угрожает; Второму - тоже (предложение N1 уже сделано, и при всех возможных исходах N3 не получит ничего). Поэтому для N3 вступает в действие Третий Закон, и он голосует "за".

То же самое будет и в ситуации с двадцатью грабителями (предложение N1 о распределении денег продиктовано не Вторым Законом, как можно было бы предположить, а Первым: только такое предложение гарантирует ему жизнь, ибо отключает Второй Закон и включает Третий для каждого из остальных грабителей).

Следовательно, наше решение было полностью правильным, а предположения о бросании монеток грабителями - противоречащими условиям (если грабители на самом деле придерживаются Трех Законов, то все их поведение при голосованиях детерминировано).

P.S. При подготовке статьи автор использовал некоторые письма, опубликованные в июле 1996 года в конференции relcom.rec.puzzles при обсуждении там этой задачи. Большое спасибо всем участникам той дискуссии и особенно - Александру Гутману (Новосибирск) и Евгению Косенко (Киев).

[Гость_Ёрофеич_*]

лишил людей удовольствия.

[ZooM]

Сидел, читал читал, и никак не пойму как считаются грабители в каком порядке, с какой стороны, ниче не понял. Номер 1 ето первый который дает предложение ?

[Гость_Ёрофеич_*]

теперь это не имеет значения. Т.к. глакси дал распечатку ответа сдернутую с интера.
В результате все лишены радости - пораскинуть мозгами.

Сообщение отредактировал Ёрофеич - Jan 20 2007, 17:32

[DAN19]

Я вот как раз это и хотел сказать

Учимся квотить!

Сообщение отредактировал Kitty - Jan 20 2007, 18:14