Пираты делят добычу.

[Профессор Снэйп]

Пираты в количестве $n$ человек делят добычу, которая состоит из $m$ одинаковых золотых монет. Можно считать, что $m$ намного больше, чем $n$.

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

При голосовании каждый пират руководствуется следующими приоритетами.

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

2) Кровожадность. Если оба варианта голоса дают пирату, по его расчётам, одинаковое количество добычи, то он обязательно проголосует против, желая, чтобы кого-нибудь убили.

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

Вопрос: как пираты разделят добычу?

[TOTAL]

В живых останутся двое самых молодых, все деньги у старшего из них. Все предыдущие "самые старые" будут убиты, т.к. захотят все деньги взять себе.

[Профессор Снэйп]

TOTAL в сообщении #227033 писал(а):

В живых останутся двое самых молодых, все деньги у старшего из них. Все предыдущие "самые старые" будут убиты, т.к. захотят все деньги взять себе.

Ответ неправильный!

Напомню, что если пирата убивают, то ему не достаётся ничего

[TOTAL]

Профессор Снэйп в сообщении #227034 писал(а):

Ответ неправильный!

Напомню, что если пирата убивают, то ему не достаётся ничего

А если я тоже пират! По условию я должен быть кровожадным и при прочих равных условиях поубивать как можно больше пиратов, что я и сделал (ведь денег мне все равно не достанется).

[Профессор Снэйп]

Хорошо. Считайте, что самый старый пират выделил одну монетку лично Вам, чтобы Вы подумали и не спешили всех убивать

[TOTAL]

Профессор Снэйп в сообщении #227045 писал(а):

Хорошо. Считайте, что самый старый пират выделил одну монетку лично Вам, чтобы Вы подумали и не спешили всех убивать

Ну уж нет, одной монеты мне мало! Самый старший пират -- это я и есть, мне $n$ лет. Поэтому пиратам $n-2, n-4, \cdots $ я дам по одной монете, а остальные заберу себе.

[ИСН]

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

[meduza]

Если $n=2$, то самый старший предлагает все монеты забрать себе. Он же поддерживает свое предложение (в условии сказано, что он имеет право голоса) и, следовательно, забирает все себе (в условии сказано, что половины голосов достаточно). Младший остается ни с чем.

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

Если $n=4$, то самому старшему нужно, чтобы его предлажение принял хотя бы 1 пират, иначе его убьют. Если он предложит монету следущему по старшинству, то тот не согласится, т. к. ему лучше прикончить его и прийти к $n=3$. Если самый старший предложит монету самому младшему, то тому уже все равно -- соглашаться или нет (в первом случае он получит 1 монету и во втором тоже, т. к. приходим к $n=3$). Но самый старший не хочет рисковать и поэтому предлагает монету среднему из оставшихся, тот соглашается (он не хочет прийти к $n=3$, когда он остается ни с чем). Предложение принимают: самому старшему $m-1$ монету, следущему по старшинству ничего, следущему 1, самому младшему ничего.

Аналогично, просматривая все варианты, задача решается для б́ольших $n$.

[TOTAL]

ИСН в сообщении #227063 писал(а):

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

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

[meduza]

TOTAL
Действительно, очень нереальная задача. Даже если нет банка по близости, можно отколоть от монеты мааааленькие кусочки золота, отдать их кому нужно, а всё оставшееся взять себе.

[Alexiii]

Допускается,как видно,что возраст каждого пирата разный,чтобы по-двое и т д не выходили!Приставим старому пирату имя 1,второму 2,...,предпоследнему - Н-1,последнему пирату(молодушке-пиратушке) - Н. Пусть также пират может до окончания дележки умереть только указанным в задаче способом(это важно на самом деле ). Также кровожадность и жадность равноценны для пирата!
Априори никто не погибает в дележке - чую!
Выходит 1 пират!!!
Явно он голосует за себя!
Он должен такое предложить,чтобы за него проголосовало минимально необходимое количество пиратов!

Дальше потом додумаю!

-- Чт июл 09, 2009 21:12:42 --

meduza в сообщении #227067 писал(а):

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

Неверно,так как пиратами водит кровожадность,жадность и ум в равной степени.Так что,чтобы сманить младшего на свою сторону,самый старший должен дать ровно $(m+2)/4$ денег (сдачу(которая из-за предположения того,что количество монет больше самих пиратов,будет меньше,чем достанется старшему),если останется, кинет среднему(все же жадность возьмет дать вдобавок младшему)).
Поясню,почему четверть - потому,что монетка - одна грань, половина - другая грань,нужно же среднее

[Vanuan]

Цитата:

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

Как я понимаю, условие задачи предполагает неделимость монет.

Предлагаю своё решение, которое является формализацией того, что предложила meduza: для нечётных n самый старший пират должен делиться с $(n/2)$ пиратами, для чётных - $(n/2-1)$ пиратами. Деление здесь и далее целочисленное.

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

Подведём итог:

• для чётного количества пиратов пираты с чётными номерами получат по одной монете (кроме самого старшего, который получает $m-(n/2-1)$), пираты с нечётными номерами не получат ни одной монеты.
• для нечётного количества пиратов наоборот: пираты с нечётными номерами получат по одной монете (самый старший получит $m-n/2$ монет), пираты с чётными номерами не получат ничего.

Доказывать, что это решение верно, я не буду, ибо лень.

И напоследок, табличка для n<=6:
$\begin{tabular}{|c|c|c|c|c|c|c|} \hline 1 & m & & & & &\\ 2 & 0 & m & & & &\\ 3 & 1 & 0 & m-1 & & & \\ 4 & 0 & 1 & 0 & m-1 & & \\ 5 & 1 & 0 & 1 & 0 & m-2 &\\ 6 & 0 & 1 & 0 & 1 & 0 & m-2\\ \hline \end{tabular}

[ewert]

Vanuan в сообщении #227678 писал(а):

Доказывать, что это решение верно, я не буду, ибо лень.

Это очевидно по индукции. Предположим, что для $(n-1)$ пирата решение верно, т.е. самый старший, раздав по монетке каждому нечётному (начиная от себя), выигрывает. Тогда это же утверждение верно и для $(n)$ пиратов: те, кто сидят на нечётных позициях, знают, что, завалив старшого, они окажутся чётными и тогда им ничего не обломится.