Посмотрел соседнюю тему про задачку о веревке и вспомнил еще одну интересную задачку. Может кому-нибудь встретится.

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

Задачу эту я прочитал в книге "Как сдвинуть гору Фудзи? Подходы ведущих мировых компаний к поиску талантов" (здесь). Там, кстати, автор постоянно ссылается на Спольски. Вышеописанная задача используется самим Спольски на собеседованиях.

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

K>Посмотрел соседнюю тему про задачку о веревке и вспомнил еще одну интересную задачку. Может кому-нибудь встретится.

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

Гм.Если пиратов пять:
1.Главный) — 34
2) — 33
3) — 33
4) — 1
5) — 1
Таким образом соглашаются 3 пирата, а 4-ый и 5-ый пират(самый низкий ранг) нервно курят в сторонке.
Этот же принципе применяется для систем с 4-мью и N кол-вом пиратов

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

_>Гм.Если пиратов пять:
_>1.Главный) — 34
_>2) — 33
_>3) — 33
_>4) — 1
_>5) — 1
_>Таким образом соглашаются 3 пирата, а 4-ый и 5-ый пират(самый низкий ранг) нервно курят в сторонке.
_>Этот же принципе применяется для систем с 4-мью и N кол-вом пиратов

Не совсем так. Попозже напишу как бы поступил настоящий пират Если, конечно, не напишет кто-нибудь еще.

_>Гм.Если пиратов пять:
_>1.Главный) — 34
_>2) — 33
_>3) — 33
4) — 0
5) — 0

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


_>>Гм.Если пиратов пять:
_>>1.Главный) — 34
_>>2) — 33
_>>3) — 33
S>4) — 0
S>5) — 0

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

В случае этой задачи удобно начать рассматривать простые случаи (с малым количеством пиратов), а потом переходить к более сложным.

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

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


_>>>Гм.Если пиратов пять:
_>>>1.Главный) — 34
_>>>2) — 33
_>>>3) — 33
S>>4) — 0
S>>5) — 0

K>Как ты думаешь, проголосует ли четвертый пират за, если знает, что если пятого убьют, то он сможет предлагать свой способ?
Точнее не четвертый, а второй согласно твоей нумерации

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

K>>Как ты думаешь, проголосует ли четвертый пират за, если знает, что если пятого убьют, то он сможет предлагать свой способ?
K>Точнее не четвертый, а второй согласно твоей нумерации
Я всего лишь математику скорректировал, а то там 100 не получалось, а задачу я не решал

В порядке увеличения рейтинга.
Для 5 пиратов:
1 0 1 0 98

Для 4 пиратов:
0 1 0 99

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

las>В порядке увеличения рейтинга.
las>Для 5 пиратов:
las>1 0 1 0 98

las>Для 4 пиратов:
las>0 1 0 99

Ага.
Остальсь, наверное, написать как прийти к столь несправедливому способу дележа.

Для удобства пронумеруем пиратов от 1 до 5 в порядке возрастания старшинства.
Начнем с простых случаев.

1. Если пират один, то он все оставляет себе.
2. Если пиратов двое, то главный пират предлагает все отдать ему и голосует за это. Поскольку «один из двух за» удовлетворяет условию “хотя бы половина за”, то так и делят.
3. Три пирата. Главному пирату достаточно склонить на свою сторону хотя бы одного другого пирата. Поскольку в случае, когда остается два пирата первый не получает ничего, то третьему пирату достаточно предложить первому хотя бы одну песету чтобы он принял его сторону. Второму можно ничего не давать, поскольку двое из трех уже «за».
4. Четыре пирата. Как мы уже выяснили, в случае трех пиратов второму не достается ничего, поэтому четвертому достаточно предложить второму хотя бы одну песету, чтобы он принял его сторону. Остальным ничего не давать.
5. Пять пиратов. Поскольку в случае четырех пиратов первый и третий не получат ничего, то пятому достаточно предложить им по одной печете чтобы они приняли его сторону. Остальным ничего не давать.

Т.о. главный дает первому и третьему пирату по одной песете, а остальное забирает себе.

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

K>Для удобства пронумеруем пиратов от 1 до 5 в порядке возрастания старшинства.
K>Начнем с простых случаев.

K>1. Если пират один, то он все оставляет себе.
K>2. Если пиратов двое, то главный пират предлагает все отдать ему и голосует за это. Поскольку «один из двух за» удовлетворяет условию “хотя бы половина за”, то так и делят.
K>3. Три пирата. Главному пирату достаточно склонить на свою сторону хотя бы одного другого пирата. Поскольку в случае, когда остается два пирата первый не получает ничего, то третьему пирату достаточно предложить первому хотя бы одну песету чтобы он принял его сторону. Второму можно ничего не давать, поскольку двое из трех уже «за».
K>4. Четыре пирата. Как мы уже выяснили, в случае трех пиратов второму не достается ничего, поэтому четвертому достаточно предложить второму хотя бы одну песету, чтобы он принял его сторону. Остальным ничего не давать.
K>5. Пять пиратов. Поскольку в случае четырех пиратов первый и третий не получат ничего, то пятому достаточно предложить им по одной печете чтобы они приняли его сторону. Остальным ничего не давать.

K>Т.о. главный дает первому и третьему пирату по одной песете, а остальное забирает себе.

Это сработает только если предположить, что пираты не способны заключить и соблюсти между собой договор. Но мы уже имеем обратный прецедент — они ведь смогли договориться о правилах дележа и вроде бы соблюдают его.
А раз договоры возможны, то например 4й может договориться со 2м и 1м проголосовать против, предложив им 1 и 2 песеты соответственно. Остальные тоже не будут щелкать клювом и предложат свои варианты, и попрет торговля...

Здравствуйте, Костя Ещенко, Вы писали:

КЕ>Это сработает только если предположить, что пираты не способны заключить и соблюсти между собой договор. Но мы уже имеем обратный прецедент — они ведь смогли договориться о правилах дележа и вроде бы соблюдают его.
Это значит лишь что пираты соблюдают некие принятые в их среде правила дележа. Непосредственно из постановки задачи следует лишь это. Также сказано что пираты жадные и логичные. О том что пираты могут договориться между собой нет ни слова.

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

КЕ>>Это сработает только если предположить, что пираты не способны заключить и соблюсти между собой договор. Но мы уже имеем обратный прецедент — они ведь смогли договориться о правилах дележа и вроде бы соблюдают его.
K>Это значит лишь что пираты соблюдают некие принятые в их среде правила дележа. Непосредственно из постановки задачи следует лишь это.
Ты писал

Пират имеющий самый высокий ранг (главарь) предлагает как делить сокровища.

Ну остальные видимо согласились. Т.е. они все же договорились. Слово "предлагает" подразумевает что они договориваются для этого конкретного случая, а не то что так делается всегда.

K>Также сказано что пираты жадные и логичные. О том что пираты могут договориться между собой нет ни слова.
Это следует из того, что они смогли договориться о правилах дележа.

Все это конечно буквоедство, просто меня возмутила несправедливость по отношению к 4м неавторитетным пиратам

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

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

las>>В порядке увеличения рейтинга.
las>>Для 5 пиратов:
las>>1 0 1 0 98

las>>Для 4 пиратов:
las>>0 1 0 99

K>Ага.
K>Остальсь, наверное, написать как прийти к столь несправедливому способу дележа.

K>Для удобства пронумеруем пиратов от 1 до 5 в порядке возрастания старшинства.
K>Начнем с простых случаев.

K>1. Если пират один, то он все оставляет себе.
K>2. Если пиратов двое, то главный пират предлагает все отдать ему и голосует за это. Поскольку «один из двух за» удовлетворяет условию “хотя бы половина за”, то так и делят.
K>3. Три пирата. Главному пирату достаточно склонить на свою сторону хотя бы одного другого пирата. Поскольку в случае, когда остается два пирата первый не получает ничего, то третьему пирату достаточно предложить первому хотя бы одну песету чтобы он принял его сторону. Второму можно ничего не давать, поскольку двое из трех уже «за».
K>4. Четыре пирата. Как мы уже выяснили, в случае трех пиратов второму не достается ничего, поэтому четвертому достаточно предложить второму хотя бы одну песету, чтобы он принял его сторону. Остальным ничего не давать.
K>5. Пять пиратов. Поскольку в случае четырех пиратов первый и третий не получат ничего, то пятому достаточно предложить им по одной печете чтобы они приняли его сторону. Остальным ничего не давать.

K>Т.о. главный дает первому и третьему пирату по одной песете, а остальное забирает себе.

Данный вариант(рассматриваю для 5 пиратов) ничем не лучше моего: главный пират забирает все себе и говорит , если кто то будет протим замачу.

ЗЫ: Если бы я был один из пяти(но не главный) и мне дали бы 1 писет, я бы такого делильщика убил бы сразу, тем более в задаче сказано что пираты логичные, а если так то после того как убьют главаря то претендентов становится уже 4 и так далее. Это намного логичнее.

Здравствуйте, Костя Ещенко, Вы писали:

КЕ>Все это конечно буквоедство, просто меня возмутила несправедливость по отношению к 4м неавторитетным пиратам

Им еще хорошо. Они хоть имеют возможность не согласиться и завалить жадного главаря. Суровая реальность не дает и этого

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

K>Посмотрел соседнюю тему про задачку о веревке и вспомнил еще одну интересную задачку. Может кому-нибудь встретится.

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

K>Задачу эту я прочитал в книге "Как сдвинуть гору Фудзи? Подходы ведущих мировых компаний к поиску талантов" (здесь). Там, кстати, автор постоянно ссылается на Спольски. Вышеописанная задача используется самим Спольски на собеседованиях.

блин, трудно нематематиу как же оно решается?

главарь(текущий капитан) должен всё забрать себе.

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

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

может правильнее дать поcледним n/2 по монетке, остальное забрать себе.
исходим из того, что если останется двое последний ничего не получит.
поэтому если дать ему 1 монету он ухватит свой шанс.
предпоследний по рангу может также расчитывать,
что последний, если ему дадут монетку проголосует за делившего,
поэтому если и он получит монетку
и народу будет хотя бы 4 человека, то он проголосует за делившего.

предпредпоследний тоже будет рад монетке если пиратов 5.
таким образом, если дать по монетке любым n/2 пиратам кроме второго,
а остальное забрать себе, то будет главарю счастье.

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

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

Задача древняя и уже была в Этюдах. Найду — кину ссылку.
А пока — решение.

Если пиратов двое (№4 и №5), то
— в случае, когда достаточно 50% "за" — все деньги загребёт №4;
— если достаточно 50% "против" — то №4, если жить хочет, всё отдаст №5 (иначе тот скажет "против" и убьёт №4).

Если пиратов трое, (№ 3, 4, 5)
При любом раскладе, №4 и №5 невыгодно вступать в сговор, так как один из них (см.выше) останется ни с чем.
№3 знает об этом и предлагает жалкую подачку: 99,0,1 или 99,1,0 соответственно. Сам он, естественно, голосует "за" и рассчитывает на голос прикормленного.

Если пиратов четверо (№ 2 — 5)
Пирату №3 выгодно голосовать против, если ему предложат меньше 99.
— Если достаточно 50% "за", то №2 делит так: 99,0,0,1 — жалкая подачка пирату №5 (который в случае убийства №2 всё равно больше чем на 1 не рассчитывает). Ну или, для гарантии, 98,0,0,2 (мало ли, личная неприязнь №5 к №2 может склонить его к мести).
— Если достаточно 50% "против", то нужно задобрить уже обоих №4 и №5 (либо №3 и №4, но это значит остаться без денег). То есть, 98,0,1,1 или 97,0,2,1.

Наконец, если пиратов пятеро.
Надо набрать два голоса товарищей... Очевидно, что мы опять отделаемся подачками.
№2 голосует против (т.к. рассчитывает на 97-99 монет).
— Если играем "за", то 98,0,1,1,0 вызовут благосклонность №3 и №4 (которым иначе достанутся нули).
— Если играем "против", то 98,0,1,0,1 или, для гарантии, 97,0,1,0,2.

К>Задача древняя и уже была в Этюдах. Найду — кину ссылку.

О как! Сам же, оказывается, её и закидывал http://www.rsdn.ru/Forum/?mid=482467

Автор: SiAVoL
Дата: 18.12.03

Почти правильно решили, но по условию задачи приаты кровожадны, поэтому если при двух вариантах они получают одинаковое количество денег, то они сначала убъют главаря, а на следующем шаге получат свои деньги. Поэтому для N пиратов решение такое:
1 — все осатвшееся, 2 — 0, 3 — 1, 4 — 2, 5 — 3 и т.д., пока не будет получен кворум