?

Log in

No account? Create an account

Previous Entry | Next Entry

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

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

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

Update: Ответ.

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

Comments

( 35 comments — Leave a comment )
chva
Jun. 13th, 2009 07:31 pm (UTC)
А когда пиратов нечётное число, автоматически выкидывают за борт текущего пирата? Или я неправильно понял что значит «голоса разделятся пополам»?
scholar_vit
Jun. 13th, 2009 07:34 pm (UTC)
Ок, уточнил формулировку.
de_va
Jun. 13th, 2009 07:35 pm (UTC)
Если предложить разделить mонеты между n/2 пиратами - автора выбросят за борт?
scholar_vit
Jun. 13th, 2009 07:37 pm (UTC)
Как проголосуют :)
de_va
Jun. 13th, 2009 07:49 pm (UTC)
Я не учёл вот что - какова иерархия? В смысле - есть уровень, начиная с которого пираты равны?
Или даже среди двух последних один будет старше другого?
scholar_vit
Jun. 13th, 2009 07:51 pm (UTC)
причем у всех пиратов они разные
de_va
Jun. 13th, 2009 07:50 pm (UTC)
сорри. перечитал.
rioman
Jun. 13th, 2009 07:38 pm (UTC)
Предложивиший вариант сам голосует?
scholar_vit
Jun. 13th, 2009 07:40 pm (UTC)
Да
bazar_wokzal
Jun. 13th, 2009 07:40 pm (UTC)
Вроде проще с конца. Если пиратов двое - старший тупо заберет себе все, ибо половина голосов ему обеспечена. Значит, если их трое - капитану достаточно отдать одну монету последнему, чтобы получить его голос. Если четверо - надежнее отдать две - или обе последнему, или по одной последнему и предпоследнему. И т.д.
scholar_vit
Jun. 13th, 2009 07:42 pm (UTC)
Идея верна, но в вычислениях ошибка.
rioman
Jun. 13th, 2009 07:43 pm (UTC)
Если четверо - одну предпоследнему.
bazar_wokzal
Jun. 13th, 2009 07:48 pm (UTC)
Да, именно. Если пятеро - придется отдать две, одну последнему и одну через одного от него - тогда их голоса обеспечены, ибо иначе они ничего не получат. И т.д - если шестеро, то достаточно двух монет третьему и пятому - на каждом шагу меняем чет на нечет.
rioman
Jun. 13th, 2009 07:48 pm (UTC)
Список (начиная с конца, чтобы столбцы не сдвигались):
2 - 0, m
3 - 1, 0, m-1
4 - 0, 1, 0, m-1
5 - 1, 0, 1, 0, m-2

По индукции можно доказать, что капитан должен раздать по одной монете тем пиратам, ранг которых в иерархии нечётный (предполагается, что ранг капитана - 1, дальше он возрастает).
rioman
Jun. 13th, 2009 07:50 pm (UTC)
Шаг индукции: если "нечётные" пираты не согласятся на такой вариант, на следующей итерации они станут "чётными" и согласно индукционному предположению они вообще ничего не получат.
rioman
Jun. 13th, 2009 07:57 pm (UTC)
Хм... А вот ещё такой вопрос:
Если, скажем, при 5-и пиратах капитан раздаст монеты так:
0, 1, 0, 0, m-2
3-й и 5-й проголосуют за или против? При том, что на следующей итерации им практически наверняка тоже ничего не достанется.
rioman
Jun. 13th, 2009 08:06 pm (UTC)
Если они проголосуют за (с учётом "вторичного показателя" :), например, чтобы в будущем получить "бонус" от капитана), получается, что капитан может отделаться только одной монетой любому "чётному" пирату, кроме вице-капитана (это который с рангом 2).
rioman
Jun. 13th, 2009 08:10 pm (UTC)
То есть, не так. Монету можно не давать вообще никому: если 3-й, 5-й и капитан проголосуют за, большинство и так будет.
bazar_wokzal
Jun. 13th, 2009 07:43 pm (UTC)
Ой, нет - если четверо, то можно обойтись одной монетой, отданной предпоследнему:).
magpie73
Jun. 13th, 2009 07:44 pm (UTC)
Прекрасный тренинг! Только условия не очень понятные, да и вообще, сейчас голова не варит... но любопытно жутко! А вы не можете в "личке" подсказать, а? И условия уточните, ладно?
scholar_vit
Jun. 13th, 2009 07:49 pm (UTC)
Я потом дам ответ
magpie73
Jun. 13th, 2009 09:07 pm (UTC)
Угу, ладно. Бум ждать
anna_frid
Jun. 13th, 2009 07:48 pm (UTC)
Мы это на теории игр проходили, так что даже писать ответ не буду. :)
scholar_vit
Jun. 13th, 2009 07:50 pm (UTC)
:)
taki_net
Jun. 13th, 2009 07:56 pm (UTC)
"Капитан" - это пират с наибольшим рангом?
scholar_vit
Jun. 13th, 2009 07:58 pm (UTC)
Да
sceptic_rus
Jun. 13th, 2009 08:59 pm (UTC)
Не учтен гринмейл младших по рангу.
p_govorun
Jun. 13th, 2009 09:04 pm (UTC)
Я эту задачу читал немного в другом виде: там было ещё условие, что пираты зазря не убивают (то есть, пират проголосует за убийство только если хоть что-нибудь получит). Там даже по одной монете раздавать не надо: капитан всё забирает себе (первый помощник против, остальные понимают, что им ничего не светит, и голосуют за.)
ny_quant
Jun. 13th, 2009 09:16 pm (UTC)
Стандартная задача, предлагаемая на интервью. Кто не начал говорить что-то разумное в течение первой минуты ищет другую работу.
__rico
Jun. 13th, 2009 09:16 pm (UTC)
> действуют рационально и являются прекрасными математиками. Более того, каждый знает, что остальные такие же

Побуду немного занудой, этого недостаточно, нужно еще чтобы каждый знал, что каждый знает, что остальные такие же, ну итп. Т.е. то, что обычно подразумевают под common knowledge
fortinbras
Jun. 13th, 2009 09:23 pm (UTC)
Если ранг пиратов от 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
Jun. 13th, 2009 09:26 pm (UTC)
В варианте n=3, я имел в виду, что не захочет n=2, описка.
fortinbras
Jun. 13th, 2009 09:32 pm (UTC)
Ещё одна неточность -- [(n-1)/2], конечно, а не [n/2].
budidich
Jun. 15th, 2009 09:18 am (UTC)
Позвольте предложить свой вариант:
1 ранг: (Капитан) - 1 монета
2 ранг: (Старпом) - 2 монеты
3 ранг: () - 3 монеты
.....
n/2 ранг: - Все оставшиеся монеты
n/2+1 ранг: 0 монет
.....
n ранг: 0 монет.

Позвольте также обратиться к старшему помощнику нашего корабля:
"Уважаемый старший помошник! Нас на корабле 21 человек включая капитана. Только что капитан предложил разделить деньги по его варианту: Нечетным игрокам по 1 монете, а себе все остальное. Я простой лейтенант, мой ранг - 7 и я попал в число тех счастливчиков, которым предложили по 1 монете. Но я проголосовал против, и капитан только что на ваших глазах получил нож под ребро и пошел к акулам. Так что уважаемый Старший помошник! Прежде чем вы предложите СВОЙ вариант, хоршенько подумайте!"
freedom_of_sea
Jun. 15th, 2009 10:53 am (UTC)
выдвинувший предложение автоматически выбывает
так как это увеличивает долю остальных. Поэтому никто не сделает ни единого предложения.
( 35 comments — Leave a comment )

Profile

knot
scholar_vit
scholar_vit

Latest Month

September 2017
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek