Пять пиратов на острове должны разделить между собой сотню золотых монет.
Они делят свою добычу следующим образом.
Старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала.
Самый старший пират (из тех, кто выжил) предлагает новый план, за него голосуют по тем же правилам, а потом или делят добычу, или убивают старшего пирата. Процесс продолжается до тех пор, пока какой-то план не будет принят.
Допустим, вы — старший пират. Как вы предложите разделить добычу?
Примечание: все пираты жадные, мыслят очень логично, и все они хотят жить.
Посмотреть решениеЧтобы найти решение, нужно понять, что ситуацию с n пиратов можно анализировать на основе ситуации с n — 1 пиратов и т.д., пока вы не доберетесь до «базовой ситуации», решение в которой будет абсолютно ясным.
Базовая ситуация — это один выживший пират. Очевидно, что единственный пират предложит отдать ему все монеты.
А что если пиратов двое? Старшему из них придется предложить, как делить добычу. В условии головоломки говорится, что предложение принимается, если «по крайней мере половина пиратов» за него проголосует. Это значит, что достаточно одного голоса старшего пирата, чтобы предложение было принято. Следовательно, если пиратов всего двое, то старшему из них бояться нечего, и он может не беспокоиться о том, что думает его товарищ. Будучи жадным негодяем, старший пират предложит отдать все сто монет ему. Результаты голосования будут такими: один голос «за» и один «против» — это значит, что предложение будет принято.
Может показаться, что старший пират всегда получит то, чего он хочет. Не совсем так. Представьте, что он решил воспользоваться тем же трюком, если пиратов трое. Давайте пронумеруем пиратов, начиная с самого младшего: №1, №2, №3.
План раздела добычи должен предложить номер 3. Если он предложит план «Все достается мне, а вы, ребята, ничего не получите», то следующий пират в этой последовательности (№2) точно проголосует против подобного предложения. Пират №2 знает, что он сам получит все, если останутся только два пирата после того, как №3 будет убит. Решающим оказывается голос пирата №1. Он ничего не получает, если проголосует за план пирата №3 , но также ничего не получит, если проголосует против, если останутся только два пирата. У него нет никаких причин, чтобы предпочесть один вариант другому.
Итак, если №3 умен, как это предполагается по условию, он попытается получить поддержку пирата №1. Нужно также учесть, что пират №3 жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны пирата №3 будет дать №1 одну золотую монету, №2 — ничего, а себе самому — оставшиеся девяносто девять монет!
Поскольку №1 также рассуждает логично, но поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если пират №3 будет убит. Пират №1 проголосует за план раздела добычи (как и №3, конечно), и это предложение будет принято двумя голосами против одного несмотря на все проклятия накачавшегося с горя ромом пирата №2.
Теперь рассмотрим ситуацию с четырьмя пиратами. Четыре — это опять четное число. Это значит, что самому старшему пирату достаточно всего одного голоса, кроме его собственного, чтобы его предложение прошло. Ему нужно ответить на вопрос: «Какой из голосов остальных трех пиратов окажется самым дешевым?»
Вернемся к ситуации с тремя пиратами. Пират №2 не получает в ней ничего, поэтому если пират №4 предложит ему хотя бы что-то, для пирата №2 будет логично проголосовать «за».
Получив голос пирата №2, пират №4 может вообще не беспокоиться о том, что думают №1 и №3. План пирата №4 будет таким: ни одной монеты для №1, одна монета для №2, ни одной монеты для №3 и девяносто девять монет для себя самого.
Теперь модель нам ясна. В каждом случае самый старший пират должен «купить» ровно столько голосов, сколько ему необходимо, и как можно дешевле. Все остальные деньги достанутся ему самому.
Теперь применим эту модель к ситуации с пятью пиратами, о которой речь и идет в задаче.
Вы пират №5. Вам нужно три голоса: ваш собственный и еще два. Таким образом, вам нужно что-то дать двум пиратам, которые больше всего проиграют, если пиратов останется только четверо. Это пираты №1 и №3. Оба не получат ничего, если вас убьют и останется всего четыре пирата. Обоих можно убедить проголосовать за ваш план. Ваше предложение: ничего не давать пирату №4, дать одну монету №3, ничего не дать №2 и дать одну монету №1. Оставшиеся девяносто восемь монет вы оставите себе.
