"Пиратская" статья в "Кванте"

В первом номере "Кванта" за 2016 год выйдет наша с Сергеем Грибком совместная статья с задачами об оптимальном принятии решений в антагонистических играх с полной информацией для многих игроков. Называется она "Пятнадцать человек на сундук мертвеца". Попросту говоря - это задачи о дележе клада командой пиратов.

С разрешения редакции публикую здесь собственно задачи и упражнения из статьи, без решений.

Пятнадцать человек на сундук мертвеца

Сергей Грибок, Константин Кноп

Все задачи, о которых мы собираемся вам рассказать, связаны общим сюжетом: команда пиратов хочет поделить золотые монеты. Но прежде чем приступить к рассказу, мы должны поближе познакомиться с пиратской логикой и ее законами.

●       Ни при каких обстоятельствах ни один из пиратов не желает очутиться за бортом корабля.

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

●       Ни один из пиратов никогда не вступит в сговор с другим пиратом, чтобы сообща обыграть остальных. «Каждый сам за себя» – правило, которому следует каждый пират.

●       Каждый пират в совершенстве владеет логикой, и все его действия логически обоснованы.

●       Все предпочтения, законы и правила пиратов (включая и это правило) известны и самим пиратам.

Итак…

Задача 1

Пятнадцать пиратов с брига «Арабелла» – капитан, 13 матросов и юнга – нашли клад, – сундук, в котором лежало 100 одинаковых золотых монет. Чтобы поделить деньги, пираты использовали такую процедуру:

1.      Капитан как самый старший предлагает свой план дележа клада.

2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

3.      Если все пираты проголосовали «за», то план принимается и деньги делятся по плану. Если же хотя бы один из пиратов проголосовал против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит свой план, пираты снова голосуют и так далее, пока наконец план одного из пиратов не будет принят.

Еще одна особенность пиратов «Арабеллы» – их природная доброта. Если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират по доброте душевной всегда проголосует «за».

Как будут поделены деньги, если пираты будут использовать данный метод дележа? Чей план будет принят?

Упражнение 1.

Капитан делил добычу между пиратами. Сначала он взял себе 1/16 всех монет и еще одну монету. Второму пирату он дал 1/16 оставшихся монет и еще две и т.д. Пятнадцатому (юнге) он дал 1/16 оставшихся монет и еще 15 монет. Оказалось, что все получили поровну и все монеты розданы. Сколько всего было монет?

Упражнение 2.

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

Теперь расскажем о том, как делила клад другая команда пиратов со шлюпа «Бестия».

Задача 2

Пираты на «Бестии» использовали другой метод дележа:

1.      Самый старший пират рассказывает план остальным.

2.      Все пираты голосуют, следует ли принять план старшего. Каждый из пиратов голосует либо «за», либо «против».

3.      Если не менее половины пиратов проголосовали «за», то план принимается, и деньги делятся по плану. Если же большинство пиратов проголосовало против, то старшего пирата бросают за борт. После этого следующий по старшинству пират излагает свой план, пираты снова голосуют и так далее, пока наконец план одного из пиратов не будет принят.

Пираты «Бестии» – такие же добродушные ребята, как и их коллеги с «Арабеллы». Если решение пирата голосовать «за» или «против» не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то каждый пират всегда голосует «за». Как 15 пиратов со шлюпа «Бестия» поделят 100 монет?

Упражнение 3.

Как изменится дележ монет на «Бестии», если пираты изменят правило 3): план будет считаться принятым, если все пираты, кроме, быть может, одного, проголосовали “за”?

Задача 3.

Пираты с фрегата «Валькирия» отличаются от пиратов «Бестии» отсутствием доброты: если решение пирата голосовать «за» или «против» никак не повлияет на то, будет ли этот пират выброшен за борт и сколько денег он получит, то в пирате просыпается его жестокая бабушка с отцовской стороны, и он голосует «против».

А в качестве алгоритма дележа на  «Валькирии» используются правила, описанные в упражнении 3.

1.      Самый старший пират рассказывает остальным свой план.

2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

3.      Если все пираты, кроме, быть может, одного, проголосовали «за», то план принимается, и деньги делятся по плану. Если же хотя бы двое из пиратов проголосовали против, то старшего пирата бросают за борт. После этого план предлагает следующий по старшинству, пираты снова голосуют и так далее, пока план одного из пиратов не будет принят.

Как 15 пиратов с «Валькирии» поделят 100 монет?

Упражнение 4.

а) Как 15 этих пиратов поделят 20 монет?

б) Как N пиратов с «Валькирии» разделят K монет?

Примечательно, что лишь незначительное различие в характере пиратов (добродушные  пираты «Бестии» в нейтральной ситуации голосуют «за», а упрямые пираты «Валькирии» – против), приводит к кардинально отличающимся результатам дележа. Способность команды “Валькирии” обеспечить себе существенно более выгодные условия дележа иллюстрирует важный общий принцип, доказательство которого выходит далеко за рамки данной работы: социальная активность ведет к росту благосостояния общества.

Задача 4

Один из пиратов, бывший в те славные времена юнгой на «Валькирии», спустя много лет после описываемых событий хвастался, что сумел забрать себе весь клад.

– Тысяча чертей! Этот скряга капитан предложил мне всего 13 монет. Тут я вижу, что шкипер голосует против, и тоже проголосовал против! И пока все на меня выпучились, шкипер уже успел выкинуть капитана за борт. А после этого, как ни в чем не бывало, шкипер предложил мне всего 12! Ну, я еще раз проголосовал против – и наш бывший шкипер тут же улетел за борт к бывшему капитану. И вот тут до следующего стало что-то доходить... Тысяча чертей! Он раз пять подряд начинал что-то говорить, и каждый раз, не доведя предложение до точки, смотрел на меня и сбивался... В конце концов он предложил отдать всё мне. Мне, безусому юнге! А все остальные пираты, постоянно косясь на меня, проголосовали «за». Конечно, после этого я не мог уже ни минуты находиться на нашем фрегате, поэтому отвязал капитанскую шлюпку, погрузил в нее сундук и немедленно отчалил.

Докажите, что этот рассказ юнги немножко не соответствует истине.

Наша серия пиратских баек была бы неполной, если бы мы не рассказали историю пиратов со шхуны «Горгона».

Задача 5

Все пираты на шхуне «Горгона» такие же жестокие, как и на «Валькирии», а для дележа используют тот же метод, что и команда шлюпа «Бестия»:

1.      Самый старший пират излагает свой план дележа.

2.      Все пираты голосуют, следует ли принять этот план. Каждый из пиратов голосует либо «за», либо «против».

3.      Если не менее половины пиратов проголосовало «за», то план принимается и деньги делятся так, как было предложено. Если же большинство пиратов проголосовало против, то старшего пирата бросают за борт. После этого следующий по старшинству пират вносит новый план, оставшиеся пираты снова голосуют и так далее, пока, наконец план одного из пиратов не будет принят.

а) Как 15 пиратов «Горгоны» поделят 100 монет?

б) Чей план будет принят, если 100 пиратам со шхуны «Горгона» нужно разделить 15 монет?

Методы дележа, которые мы рассмотрели в предыдущих задачах, имеют один существенный недостаток: большинство пиратов может очутиться за бортом, а это плохо сказывается на боеготовности экипажа. К счастью, среди пиратских команд встречаются и менее кровожадные.

Задача 6

Пираты с корвета «Даная» были такими же жестокими, как на «Горгоне» и «Валькирии», но придумали новый способ дележа монет, который позволяет пиратам оставаться на борту и претендовать на часть добычи даже после того, как их план не был принят.

1.      Самый старший пират излагает свой план дележа.

2.      Все пираты голосуют «за» либо «против».

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

Как 15 пиратов «Данаи» поделят 100 монет?

Заметим, что доверие пиратов к демократическим механизмам принятия решений тоже не такое абсолютное, как вам могло показаться...

Задача 7

На бригантине «Ехидна» только капитан и шкипер имеют право предлагать планы дележа монет. Все остальные пираты могут лишь голосовать. Таким образом, алгоритм дележа выглядит так:

1.      Шкипер рассказывает всем остальным свой план дележа монет.

2.      Затем капитан рассказывает всем свой план дележа монет.

3.      Все пираты (включая капитана и шкипера) голосуют либо за первый, либо за второй план.

4.      Монеты делятся в соответствии с планом, набравшим больше голосов.

Известно, что если оба плана сулят пирату равное число монет, он проголосует за первый план.

Как 15 пиратов (капитан, шкипер и 13 матросов) с «Ехидны» поделят 63 монеты?

Задача 8

На барке «Жанетта», как и на «Ехидне», матросы не имеют права выдвигать планы. Это могут делать лишь старшие пираты. Алгоритм дележа такой:

1.      Первый пират рассказывает свой план дележа.

2.      Второй пират рассказывает свой план – «альтернативу».

3.      План и альтернатива сравниваются. Если план даёт хотя бы двум пиратам не меньше монет, чем альтернатива, то альтернатива отвергается. Если же альтернатива даёт больше денег всем пиратам, кроме быть может одного, то план отвергается, а альтернатива становится планом. Затем следующий пират озвучивает новую альтернативу, и так далее.

4.      После того как все старшие пираты высказались, монеты делятся по плану.

5 старших пиратов и 10 матросов с «Жанетты» делят 105 монет. Как первый пират сможет получить 14 монет?

Задачи для самостоятельного решения

В среднем эти задачи более сложны, чем разобранные выше.

С1.

Как изменится дележ на «Данае», если пираты поменяют правило 3): план будет считаться принятым, если более половины пиратов проголосовали “за”? Для решения задачи требуется уточнить, как пират решает, какой выдвинуть план, если есть несколько разных планов, каждый из которых принесет этому пирату одно и то же число монет. В этом случае будем считать, что выбор плана происходит случайным образом (например, пират бросает монетку, чтобы сделать выбор между двумя равноценными планами).

С2.

Как изменится решение предыдущей задачи, если в случае выбора между равноценными планами пират «Данаи» всегда предпочтет тот план, который оставляет больше монет более старшим пиратам?

С3.

Как именно будут разделены монеты в задаче 5б (“Горгона” с большой командой и малым запасом золота), если выбор между равноценными планами делается так же, как в предыдущей задаче С2?

С4

Как будут разделены на бригантине «Ехидна» K монет между N пиратами?

С5.**

На яхте «Золушка» команда состоит всего из троих – капитана, шкипера и юнги. В найденном ими кладе оказалось всего 15 монет. Поэтому они договорились, что сначала выслушают все три плана, а уже потом будут выбирать.

Итак, все по очереди, начиная с капитана и заканчивая юнгой, предлагают свои варианты дележа. Потом каждый голосует – выбирает тот из планов, в котором ему достается больше монет. Если таких планов несколько, он проголосует за первый из них. План, получивший больше одного голоса, принимается, и клад делится в соответствии с ним. Однако если такого плана не оказалось, то никто ничего не получает (весь клад выбрасывается за борт).

Как окажутся разделены монеты?