?

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)
Как проголосуют :)
(no subject) - de_va - Jun. 13th, 2009 07:49 pm (UTC) - Expand
(no subject) - scholar_vit - Jun. 13th, 2009 07:51 pm (UTC) - Expand
(no subject) - de_va - Jun. 13th, 2009 07:50 pm (UTC) - Expand
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)
Идея верна, но в вычислениях ошибка.
(no subject) - rioman - Jun. 13th, 2009 07:43 pm (UTC) - Expand
(no subject) - bazar_wokzal - Jun. 13th, 2009 07:48 pm (UTC) - Expand
(no subject) - rioman - Jun. 13th, 2009 07:48 pm (UTC) - Expand
(no subject) - rioman - Jun. 13th, 2009 07:50 pm (UTC) - Expand
(no subject) - rioman - Jun. 13th, 2009 07:57 pm (UTC) - Expand
(no subject) - rioman - Jun. 13th, 2009 08:06 pm (UTC) - Expand
(no subject) - rioman - Jun. 13th, 2009 08:10 pm (UTC) - Expand
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)
Я потом дам ответ
(no subject) - magpie73 - Jun. 13th, 2009 09:07 pm (UTC) - Expand
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, описка.
(no subject) - fortinbras - Jun. 13th, 2009 09:32 pm (UTC) - Expand
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

November 2017
S M T W T F S
   1234
567891011
12131415161718
19202122232425
2627282930  

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek