Задача о разумных пиратах

[scholar_vit]

Сын прислал задачку, которую нашел на каком-то сайте. Итак, n пиратов делят m золотых монет, m > n. У каждого пирата есть ранг, причем у всех пиратов они разные. Дележ происходит так. Старший по рангу предлагает вариант, после чего все голосуют. Предложение принимают простым большинством голосов (если голоса разделятся пополам, предложение проходит). Если предложение не проходит, его автора выкидывают за борт (в более мягком варианте - отстраняют от дележа), и следующий по рангу предлагает свой вариант на тех же условиях.

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

Как должен действовать капитан, чтобы получить максимум монет?

Update: Ответ.

Комментарии не скринятся.

Comments

[chva.livejournal.com]

А когда пиратов нечётное число, автоматически выкидывают за борт текущего пирата? Или я неправильно понял что значит «голоса разделятся пополам»?

[scholar-vit.livejournal.com]

Ок, уточнил формулировку.

[de-va.livejournal.com]

Если предложить разделить mонеты между n/2 пиратами - автора выбросят за борт?

[scholar-vit.livejournal.com]

Как проголосуют :)

[de-va.livejournal.com]

Я не учёл вот что - какова иерархия? В смысле - есть уровень, начиная с которого пираты равны?
Или даже среди двух последних один будет старше другого?

[scholar-vit.livejournal.com]

причем у всех пиратов они разные

[de-va.livejournal.com]

сорри. перечитал.

[rioman.livejournal.com]

Предложивиший вариант сам голосует?

[scholar-vit.livejournal.com]

Да

[bazar-wokzal.livejournal.com]

Вроде проще с конца. Если пиратов двое - старший тупо заберет себе все, ибо половина голосов ему обеспечена. Значит, если их трое - капитану достаточно отдать одну монету последнему, чтобы получить его голос. Если четверо - надежнее отдать две - или обе последнему, или по одной последнему и предпоследнему. И т.д.

[scholar-vit.livejournal.com]

Идея верна, но в вычислениях ошибка.

[rioman.livejournal.com]

Если четверо - одну предпоследнему.

[bazar-wokzal.livejournal.com]

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

[rioman.livejournal.com]

Список (начиная с конца, чтобы столбцы не сдвигались):
2 - 0, m
3 - 1, 0, m-1
4 - 0, 1, 0, m-1
5 - 1, 0, 1, 0, m-2

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

[rioman.livejournal.com]

Шаг индукции: если "нечётные" пираты не согласятся на такой вариант, на следующей итерации они станут "чётными" и согласно индукционному предположению они вообще ничего не получат.

[rioman.livejournal.com]

Хм... А вот ещё такой вопрос:
Если, скажем, при 5-и пиратах капитан раздаст монеты так:
0, 1, 0, 0, m-2
3-й и 5-й проголосуют за или против? При том, что на следующей итерации им практически наверняка тоже ничего не достанется.

[rioman.livejournal.com]

Если они проголосуют за (с учётом "вторичного показателя" :), например, чтобы в будущем получить "бонус" от капитана), получается, что капитан может отделаться только одной монетой любому "чётному" пирату, кроме вице-капитана (это который с рангом 2).

[rioman.livejournal.com]

То есть, не так. Монету можно не давать вообще никому: если 3-й, 5-й и капитан проголосуют за, большинство и так будет.

[bazar-wokzal.livejournal.com]

Ой, нет - если четверо, то можно обойтись одной монетой, отданной предпоследнему:).

[magpie73.livejournal.com]

Прекрасный тренинг! Только условия не очень понятные, да и вообще, сейчас голова не варит... но любопытно жутко! А вы не можете в "личке" подсказать, а? И условия уточните, ладно?

[scholar-vit.livejournal.com]

Я потом дам ответ

[magpie73.livejournal.com]

Угу, ладно. Бум ждать

[anna-frid.livejournal.com]

Мы это на теории игр проходили, так что даже писать ответ не буду. :)

[scholar-vit.livejournal.com]

:)

[taki-net.livejournal.com]

"Капитан" - это пират с наибольшим рангом?

[scholar-vit.livejournal.com]

Да

[sceptic-rus.livejournal.com]

Не учтен гринмейл младших по рангу.

[p_govorun.livejournal.com]

Я эту задачу читал немного в другом виде: там было ещё условие, что пираты зазря не убивают (то есть, пират проголосует за убийство только если хоть что-нибудь получит). Там даже по одной монете раздавать не надо: капитан всё забирает себе (первый помощник против, остальные понимают, что им ничего не светит, и голосуют за.)

[ny-quant.livejournal.com]

Стандартная задача, предлагаемая на интервью. Кто не начал говорить что-то разумное в течение первой минуты ищет другую работу.

[http://users.livejournal.com/__rico/]

> действуют рационально и являются прекрасными математиками. Более того, каждый знает, что остальные такие же

Побуду немного занудой, этого недостаточно, нужно еще чтобы каждый знал, что каждый знает, что остальные такие же, ну итп. Т.е. то, что обычно подразумевают под common knowledge

[fortinbras.livejournal.com]

Если ранг пиратов от 1 до n, где n -- ранг капитана. То делить надо так:

Пиратам с рангами от 1 до [n/2] -- по одной монете, остальным по нулю. Т.е. по индукции

n=2: 0; m.
n=3: 1; 0; m-1. ( пират с монетой будет голосовать за, чтобы не перейти к варианту n=1)
n=4: 1; 0; 0; m-1. (тот же мотив)
n=5: 1; 1; 0; 0; m-2 ( пират ранга 2 не захочет варианта n=4)
etc.

[fortinbras.livejournal.com]

В варианте n=3, я имел в виду, что не захочет n=2, описка.

[fortinbras.livejournal.com]

Ещё одна неточность -- [(n-1)/2], конечно, а не [n/2].

[budidich.livejournal.com]

Позвольте предложить свой вариант:
1 ранг: (Капитан) - 1 монета
2 ранг: (Старпом) - 2 монеты
3 ранг: () - 3 монеты
.....
n/2 ранг: - Все оставшиеся монеты
n/2+1 ранг: 0 монет
.....
n ранг: 0 монет.

Позвольте также обратиться к старшему помощнику нашего корабля:
"Уважаемый старший помошник! Нас на корабле 21 человек включая капитана. Только что капитан предложил разделить деньги по его варианту: Нечетным игрокам по 1 монете, а себе все остальное. Я простой лейтенант, мой ранг - 7 и я попал в число тех счастливчиков, которым предложили по 1 монете. Но я проголосовал против, и капитан только что на ваших глазах получил нож под ребро и пошел к акулам. Так что уважаемый Старший помошник! Прежде чем вы предложите СВОЙ вариант, хоршенько подумайте!"

выдвинувший предложение автоматически выбывает

[freedom_of_sea.livejournal.com]

так как это увеличивает долю остальных. Поэтому никто не сделает ни единого предложения.