Головоломки
February 17

Разбор задачи о пиратах

Пять пиратов на острове должны разделить между собой сотню золотых монет.

Они делят свою добычу так:

  1. Старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет.
  2. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала.

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

Допустим, вы — старший пират. Как вы предложите разделить добычу?

Разбор

Давайте для простоты разберем базовый случай с 2мя пиратами, далее с 3мя и, таким образом, придем к решению для 5ти пиратов.

2 пирата

Старший пират решает, что все монеты должны достаться ему. Так как половина пиратов в данном случае это 1 пират, то данное решение принимается и все монеты достаются старшему пирату. Тут все просто!

3 пирата

1й старший пират предлагает отдать все монеты ему. 2й пират точно против, т.к. если убьют 1го пирата, то все монеты точно достанутся ему. Решающий голос за 3м пиратом. Но он знает, что оба варианта оставят его без монет, поэтому ему все равно за какое решение голосовать.

В этом случае старшему пирату достаточно подкупить 3го пирата, отдав ему всего лишь 1 монету. Разумеется, 3й пират согласится, т.к. 1 монета лучше чем ничего. Напоминаем, что если останутся 2 пирата, то младший пират точно не получит ничего.

4 пирата

Старшему пирату достаточно получить всего лишь 1 дополнительный голос за свое предложение. Тогда половиной голосов (2) его решение пройдет.
Если посмотреть на ситуацию с 3мя пиратами, то в ней не получает ни одной монеты 2й пират. Поэтому его можно подкупить снова всего лишь 1 монетой. 2й пират точно согласится, 1 монета лучше, чем ничего.

5 пиратов

Теперь старшему пирату нужно 2 дополнительных голоса, чтобы его решение прошло. Снова рассуждаем, кто ничего не получит, если убьют старшего пирата. Смотрим случай для 4х пиратов. 3й и 1й пираты в ней не получают ничего. Таким образом, подкупаем 1й монетой 3го и 1го пирата. Ваше решение проходит.
Старший пират в этом случае получит 98 монет.