Вообщем награбили пять (в общем случае N) пиратов сокровищ всяких и начали их делить. Всего у них есть 100 писет которые надо поделить. Пираты имеют разный ранг. Пират имеющий самый высокий ранг (главарь) предлагает как делить сокровища. Если хотя бы половина пиратов (включая предлагающего) согласиться с предлагаемой системой дележки, то деньги делят предложенным способом. Если соглашается менее половины, то главаря убивают и главарем становится пират с наивысшим рангом среди оставшихся, после чего все начинаеться с начала. Все пираты жадные, кровожадные, абсолютно логичные и не хотят умирать сами. Какой способ дележки следует предложить главарю чтобы остаться в живых и при этом получить максимум денег?

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

ну если идти мат. индукцией, то чето нарешать можно.
При двух пиратах все ясно. Главарь забирает все 100-0
При трех, главарю нужно подкупить самого "нерейтингового" 99-0-1. Он согласится — не согласиться ему не выгодно.
При 4: 98-0-0-2 Тот же подкуп, но с надбавкой.
При 5: нужно подкупить еще одного, второго с конца по рейтингу, и надбавить последнему. 96-0-0-1-3.

Здравствуйте, <Аноним>, Вы писали:

Одна из первых задачек в этом форуме.
Возможны варианты, связанные с трактовкой нюансов условий. Например, что важнее — жадность или кровожадность?

Здравствуйте, Аноним, Вы писали:

А>Вообщем награбили пять (в общем случае N) пиратов сокровищ всяких и начали их делить. Всего у них есть 100 писет которые надо поделить. Пираты имеют разный ранг. Пират имеющий самый высокий ранг (главарь) предлагает как делить сокровища. Если хотя бы половина пиратов (включая предлагающего) согласиться с предлагаемой системой дележки, то деньги делят предложенным способом. Если соглашается менее половины, то главаря убивают и главарем становится пират с наивысшим рангом среди оставшихся, после чего все начинаеться с начала. Все пираты жадные, кровожадные, абсолютно логичные и не хотят умирать сами. Какой способ дележки следует предложить главарю чтобы остаться в живых и при этом получить максимум денег?
Вспомните знаменитую книгу "Остров сокровищ" Р. Л. Стивенсона. В ней главарь пиратов Флинт убил всех, чтобы получить все сокровища.
Точнее, чтобы никто не мог сказать где спрятаны сокровища. Вот Вам решение задачи.

Здравствуйте, ausergiy, Вы писали:

A>При 4: 98-0-0-2 Тот же подкуп, но с надбавкой.

Тут можно поделить более выгодно

Здравствуйте, Аноним, Вы писали:

А>Вообщем награбили пять (в общем случае N) пиратов сокровищ всяких и начали их делить. Всего у них есть 100 писет которые надо поделить. Пираты имеют разный ранг. Пират имеющий самый высокий ранг (главарь) предлагает как делить сокровища. Если хотя бы половина пиратов (включая предлагающего) согласиться с предлагаемой системой дележки, то деньги делят предложенным способом. Если соглашается менее половины, то главаря убивают и главарем становится пират с наивысшим рангом среди оставшихся, после чего все начинаеться с начала. Все пираты жадные, кровожадные, абсолютно логичные и не хотят умирать сами. Какой способ дележки следует предложить главарю чтобы остаться в живых и при этом получить максимум денег?

Как-то на собеседовании такую задачку давали Решил минут за 10-15.

Здравствуйте, o.kostya, Вы писали:

OK>Здравствуйте, ausergiy, Вы писали:

A>>При 4: 98-0-0-2 Тот же подкуп, но с надбавкой.

OK>Тут можно поделить более выгодно

ну да. Ошибся. Подкупать дешевле третьего 99-0-1-0
И, соответственно, 98-0-1-0-1

Здравствуйте, Аноним, Вы писали:

А>Вообщем награбили пять (в общем случае N) пиратов сокровищ всяких и начали их делить. Всего у них есть 100 писет которые надо поделить. Пираты имеют разный ранг. Пират имеющий самый высокий ранг (главарь) предлагает как делить сокровища. Если хотя бы половина пиратов (включая предлагающего) согласиться с предлагаемой системой дележки, то деньги делят предложенным способом. Если соглашается менее половины, то главаря убивают и главарем становится пират с наивысшим рангом среди оставшихся, после чего все начинаеться с начала. Все пираты жадные, кровожадные, абсолютно логичные и не хотят умирать сами. Какой способ дележки следует предложить главарю чтобы остаться в живых и при этом получить максимум денег?

Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
Если второй опять жадный козел — значит убивают и его и уже делят на троих.

Здравствуйте, alpha21264, Вы писали:

A>Здравствуйте, Аноним, Вы писали:


A>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

Вы не учитываете указанные в условии жадность и кровожадность пиратов.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, alpha21264, Вы писали:

A>>Здравствуйте, Аноним, Вы писали:


A>>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

B>Вы не учитываете указанные в условии жадность и кровожадность пиратов.

Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.
И с какого хрена они согласятся, если они знают, что получат минимум 33%?
В такой ситуации на подкуп в 1% от суммы согласится только полный лох.

Здравствуйте, alpha21264, Вы писали:

A>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

Если четвертый пират соглашается с первым, то они получают половину голосов и от мнения второго и третьего ничего не зависит.

A>И с какого хрена они согласятся, если они знают, что получат минимум 33%?
A>В такой ситуации на подкуп в 1% от суммы согласится только полный лох.

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

Здравствуйте, alpha21264, Вы писали:

A>Здравствуйте, baily, Вы писали:

B>>Здравствуйте, alpha21264, Вы писали:

A>>>Здравствуйте, Аноним, Вы писали:


A>>>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>>>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

B>>Вы не учитываете указанные в условии жадность и кровожадность пиратов.

A>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

Профессор: — Докажите это утверждение
Студент: — Мамой, клянусь

Здравствуйте, ДимДимыч, Вы писали:

ДД>Здравствуйте, alpha21264, Вы писали:

A>>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

ДД>Если четвертый пират соглашается с первым, то они получают половину голосов и от мнения второго и третьего ничего не зависит.

В условии задачки когда делят на пятерых нужно чтобы ТРОЕ из присутсвующих согласились с главарем.

A>>И с какого хрена они согласятся, если они знают, что получат минимум 33%?
A>>В такой ситуации на подкуп в 1% от суммы согласится только полный лох.

ДД>Четвертому пирату выгодно соглашаться на любую сколь угодно малую сумму, иначе он не получает вообще ничего (когда их останется двое).

Вот такие люди и продали СТРАНУ за джинсы.

Оффтоп включен.
Рассказать тебе как добрым словом (без оружия) просят заткнуться человека вооруженного автоматом?
(Ну да за спиной танк стоит)

Здравствуйте, baily, Вы писали:

B>Здравствуйте, alpha21264, Вы писали:

A>>Здравствуйте, baily, Вы писали:

B>>>Здравствуйте, alpha21264, Вы писали:

A>>>>Здравствуйте, Аноним, Вы писали:


A>>>>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>>>>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

B>>>Вы не учитываете указанные в условии жадность и кровожадность пиратов.

A>>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

B>

B>Профессор: — Докажите это утверждение
B>Студент: — Мамой, клянусь

Че, так трудно понять, что если главаря не поддержат еще двое, у того башка с плеч?

Здравствуйте, alpha21264, Вы писали:

A>Здравствуйте, baily, Вы писали:

B>>Здравствуйте, alpha21264, Вы писали:

A>>>Здравствуйте, baily, Вы писали:

B>>>>Здравствуйте, alpha21264, Вы писали:

A>>>>>Здравствуйте, Аноним, Вы писали:


A>>>>>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>>>>>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

B>>>>Вы не учитываете указанные в условии жадность и кровожадность пиратов.

A>>>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

B>>

B>>Профессор: — Докажите это утверждение
B>>Студент: — Мамой, клянусь

A>Че, так трудно понять, что если главаря не поддержат еще двое, у того башка с плеч?

Но вы то утверждали, что поддержать должны не просто какие-то двое из пиратов, а именно второй и третий пират. Да еще и за 33%

Здравствуйте, baily, Вы писали:

B>Здравствуйте, alpha21264, Вы писали:

A>>Здравствуйте, baily, Вы писали:

B>>>Здравствуйте, alpha21264, Вы писали:

A>>>>Здравствуйте, baily, Вы писали:

B>>>>>Здравствуйте, alpha21264, Вы писали:

A>>>>>>Здравствуйте, Аноним, Вы писали:


A>>>>>>Поровну. В любом другом случае пираты "абсолютно логично" его убивают и делят все поровну на четверых.
A>>>>>>Если второй опять жадный козел — значит убивают и его и уже делят на троих.

B>>>>>Вы не учитываете указанные в условии жадность и кровожадность пиратов.

A>>>>Это Вы не учитываете. Второй и третий пират ДОЛЖНЫ согласиться с первым.

B>>>

B>>>Профессор: — Докажите это утверждение
B>>>Студент: — Мамой, клянусь

A>>Че, так трудно понять, что если главаря не поддержат еще двое, у того башка с плеч?

B>Но вы то утверждали, что поддержать должны не просто какие-то двое из пиратов, а именно второй и третий пират. Да еще и за 33%

Ну насчет именно второго и третьего я погорячился. Хотя такой вариант вроде проходит.

Здравствуйте, alpha21264, Вы писали:


A>>>Че, так трудно понять, что если главаря не поддержат еще двое, у того башка с плеч?

B>>Но вы то утверждали, что поддержать должны не просто какие-то двое из пиратов, а именно второй и третий пират. Да еще и за 33%

A>Ну насчет именно второго и третьего я погорячился. Хотя такой вариант вроде проходит.

Знаете, мне как то лень разжевывать вам решение, так как, несмотря на то, что в данном топике есть явные подсказки, вы продолжаете упорно настаивать на неправильном ответе, даже не пытаясь понять почему он неправилен. Если вам интересно, то на этом форуме данная задача уже решалась, можете найти и посмотреть.

Здравствуйте, alpha21264, Вы писали:

ДД>>Если четвертый пират соглашается с первым, то они получают половину голосов и от мнения второго и третьего ничего не зависит.

A>В условии задачки когда делят на пятерых нужно чтобы ТРОЕ из присутсвующих согласились с главарем.

Я думал, мы рассматриваем случай с N==4. Если не так, тогда извините.

Здравствуйте, baily, Вы писали:

B>Здравствуйте, alpha21264, Вы писали:


A>>>>Че, так трудно понять, что если главаря не поддержат еще двое, у того башка с плеч?

B>>>Но вы то утверждали, что поддержать должны не просто какие-то двое из пиратов, а именно второй и третий пират. Да еще и за 33%

A>>Ну насчет именно второго и третьего я погорячился. Хотя такой вариант вроде проходит.

B>Знаете, мне как то лень разжевывать вам решение, так как, несмотря на то, что в данном топике есть явные подсказки, вы продолжаете упорно настаивать на неправильном ответе, даже не пытаясь понять почему он неправилен. Если вам интересно, то на этом форуме данная задача уже решалась, можете найти и посмотреть.

Ну если Вам лень, то тогда я вам разжую.

Во-первых эта задача имеет очень много вариантов решения.
Например 20+20+20+20+20 или Х-Х-75-15-10.
Когда пираты голосуют они принимают решение "Казнить или принять вариант".
"Казнить" — это если текущий лидер совсем охамел и следующий кандидат имеет
лучший вариант дележа для этого (голосующего) пирата. "Принять" в противном
случае.
1 Шаг рассуждений (в живых остались 4-й и 5-й пираты). Что будет в этом случае?
4й пират заберет все себе и 5й останется ни с чем.
Значит 5й не должен попасть в эту ситуацию.
2 Шаг рассуждений (В живых 3й 4й 5й пираты)
4й — всегда против — он в случае казни третьего получает все.
5й будет за, если ему дать одну монету.
Итого 3й пират предлагает вариант Х-Х-99-0-1
3 Шаг (В живых 2й 3й 4й 5й пираты)
3й против любого варианта, если он меньше чем 99 (эту сумму он получит при казни второго)
4й за если ему достанется больше чем 0
5й за если ему достанется больше чем 1
Итого 2й пират предлагает вариант Х-99-0-1-0
4 Шаг (В живых все пираты)
2й против любого варианта, если он меньше чем 99
3й за если ему достанется больше чем 0
4й за если ему достанется больше чем 1 (это больше чем в любом из трех предыдущих)
5й за если ему достанется больше чем 0 (это больше чем в варианте предыдущего шага)
Итого 1й пират предлагает вариант 98-0-1-0-1 (стратегия называется "дружить через соседа")
Так рассуждал первый пират. Вполне логично. Рекурсивно.

Теперь что произошло на самом деле.
1) 1й пират предлагает вариант 98-0-1-0-1 весьма довольный, так как он при таком раскладе
получает аж 98 монет и все согласны.
Идет процедура голосования (начиная с младших).
5й неожиданно для всех снимает бескозырку, надевает буденновку и голосует "против"
4й голосует против так как ему ничего не досталось,
3й голосует за, так как он кулацкая морда и одна монета лучше чем ничего
2й голосует против "против" так как в случае казни первого в начальство выходит он и делить ему.
1-го пирата берут под белы руки и вешают на фок рее
2) 2й очень обрадовался, но слегка офигевает от поведения 5-го пирата. Однако в его варианте
голос 5-го пирата все равно должен быть "против", и 2й предлагает свой вариант Х-99-0-1-0
5й пират голосует против так как ему ничего не досталось,
4й — расстегивает бушлат, на котором видна медаль "25 лет в РККА" и тоже голосует против.
3й — против так как жаден до безобразия и в начальство хочется.
2-го пирата берут под белы руки и вешают на грот рее
3) Над головой 3-го пирата со скрипом раскачиваются риф-тали бизань-рея, на котором он будет
болтаться, если эти двое проголосуют против.
5й пират зачем-то достал револьвер нагана.
4й пират достал именной маузер с надписью "за освобождение Дальнего Востока от Феликса
Эдмундовича Дзержинского". Морды у обоих пиратские, неласковые.
3й пират рассуждает:
Можно предложить Х-Х-50-0-50, но черт знает этих большевиков, странные они.
Конечно 50 монет больше 33-х но уж больно на рее висеть не хочется.
И он предлагает вариант Х-Х-33-33-33.
Вот так Алекс и Юстас абсолютно логично и демократично вместо 2х монет получили целых 66
потому что правильно (логично) голосовали.


Анекдот про мышку и мышеловку я вам уже рассказывал. (где тут смайлик язык высовывающий?)