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

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

Сразу предупреждаю - задача без подвохов, тут нет никаких уловок. Тут красивое логическое решение.

Итак, задача:
Вы - пират. Со своими друзьями вы награбили 1000$ и теперь вы все сидите за круглым столом и делите добычу. Всего пиратов пятеро (включая вас). Процесс делёжки проходит следующим образом: первый пират (а это как раз вы) предлагает свой способ разделения денег. Далее все пираты (включая делящего) голосуют. Способ разделения принимается в том случае, если он набрал как минимум 50% голосов (3 из 5, 2 из 4, 2 из 3 или 1 из 2). Если же способ не принят - делившего убивают и делит следующий пират (по часовой стрелке). Делёжка начинается с вас. Как надо разделить деньги так, чтобы вас не убили и чтобы вы получили наибольшее возможное количество денег? Учтите, что все пираты великолепно разбираются в логике!

Для пущей ясности - вот так вы сидите за столом. Вы - номер 1. После вас (если вас убьют) делит номер 2 и так далее.


Это сообщение отредактировал(а) Kefir - 1.5.2008, 16:51

а если мой способ других устраивает а одного не устраивает? Его убивают? Если да то у меня есть решение 

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

Добавлено через 2 минуты и 39 секунд
я  максимально могу забрать себе 499$ ?

krwlr, если за твой способ проголосуют три пирата (50%+ от всех голосов), тогда уже наплевать на остальных двух пиратов.

v2v, в задаче всё описано. каждый пират, естесственно, хочет получить как можно больше денег. делить общуу сумму можно на целые числа (к примеру, нельзя предлагать 0.5 доллара) - предлагать можно суммы от 0 до 1000 долларов.

например, можно предложить такой раздел: себе 200, а остальным 1, 199, 250 и 350. решение однозначное, никаких "а может быть?".


во-первых, почему?
во-вторый, нет В)

Kefir, правильно или нет: Себе 415, Второму 251, Третьему 334, Четвёртому 0, Пятому 0?
---
Тысячи чертей!!! Я Убью тебя!!!          

Это сообщение отредактировал(а) Joil - 1.5.2008, 18:14

Когда-то решал.. 
Правильное решение помню смутно  


Вроде нет

себе все бабки =))

от обратного.
всех убили остался только 3 и 4. 3й делит и берёт всё себе - голосует 1 - За. 1 - Против. Поделено.
Значит 4й согласится на любую сумму больше 0: 
даём ему 1$.
и ещё 1$ дадим второму. потому что если меня убъьют и делить будет 1й , то он возмёт 999 себе и даст 1$ 4му.
2й тоже получит ноль.
Значит 998 $ берёт себе ? 

Добавлено @ 03:00
я тут перепутал номера : 5й  - это Я.

Это сообщение отредактировал(а) v2v - 1.5.2008, 20:18

Не.. скорее наоборот.
Себе 1$ (так как первый в очереди на умервшление)
5ому тоже 1$
4ому 998$ - так как он будет последний из выживших  при худшем раскладе.

Это сообщение отредактировал(а) saewelo - 1.5.2008, 20:07

блин я там номера поперепутывал!!!!(((

Добавлено через 24 секунды
в том моём расчёте 5й - ЭТО Я

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

Можно я испорчу всем гадания? Можно?   

так а чё гадать. я ведь правильно решил, так ли. 

v2v,

этот вывод не обоснован почти никак, значит, дальнейшие выводы тоже необоснованы  

Добавлено через 1 минуту и 38 секунд
saewelo, таких решений я ещё, пожалуй, не слышал В)
maxim1000, 
Str!pe, 
подождите, пипл отпишется - тогда, а то так ведь неинтересно В)

чуваки... давай те до вторника подождем... а то праздники+выходные... думать не очень настроен..

 а в понедельник или вторник подумать мона!

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

Добавлено через 7 минут
можно писать? никто не обидется?

Если смотреть с конца и кто где будет трупом...
То себе (как первому) - 998, третьему - 1, пятому - 1.  (Если третий и пятый не соглашаются то при следующей дележке - они трупы.)

Если не так, тогда бум считать что меня жадность сгубила   



Это сообщение отредактировал(а) saewelo - 1.5.2008, 23:22

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

Тоже попробовал распутывать с конца...

Если остались два пирата: четвертый берет все себе, пятый в пролете.

Следовательно, если остались трое, третьему (чтобы выжить) достаточно задобрить пятого, который согласен на любую сумму (если он не согласится, очередь дойдет до четвертого, который оставит его с ничем). Поэтому третий может претендовать на 999 $.

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

Теперь смотрим, что может получить каждый из пиратов в исходном раскладе, в зависимости от того, как он будет голосовать. Видно, что самые реальные шансы получить хороший куш - у второго, поэтому он нам явно не союзник, на него сразу забиваем. Третьему важно, чтобы очередь не дошла до второго - он будет за нас даже за один бакс. Остаются 999 $, и нужно купить еще один голос, притом верняк. И четвертый, и пятый могут надеяться на что-то, если очередь дойдет до второго, так что любой из них может проголосовать против. У пятого шансов больше - он получит гарантированный бакс даже в том случае, если проголосует и против второго (позволив делить третьему). Четвертый, если проголосует против нас, теоретически может остаться с ничем. Поэтому второй бакс - ему, остальное себе. Вроде совпало с решением v2v...

saewelo,  за такое решение вам бы больше одного балла из 10ти на олимпиаде не поставили (собоснованием - угадал ответ).

SelenIT, наконец то, человек, который ясно излагается В) Есть небольшой ньюанс - у тебя немного неверные рассуждения в последнем абзаце, а также нет чёткого вывода в предпоследнем абзаце. Из этого опять же из-за этого выплывают ошибки. Ты пишешь:

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

Это сообщение отредактировал(а) Kefir - 2.5.2008, 08:14

Мы не на олимпиаде, и не разжеван ответ только потому что бы остальным все еще было интересно отгадывать, так ведь договаривались? 

4 и 5 --> 4 делит себе 1000$, имеет своих 50% голосов (свой голос из 2), 5 соотвественно или труп или без денег;
3, 4 и 5 --> 3 делит себе 999$, 5 дает 1$ (согласен так как следующая дележка оставляет его как минимум ни с чем), 4 остается в пролете;
2, 3, 4 и 5 --> 2 делит себе 999$, еще один голос забирает у 4 дав при этом ему 1$, остаются с носом или без жизни 3 и 5ж
1, 2, 3 , 4 и 5 --> 1 делит, себе забирает 998$, по 1$ дает 3 и 5, 2 и 4 смело оставляет за бортом.

Логика в том что надо задабривать тех кто при следующей дележке остается или без денег, или трупом - это проще просчитать с конца. 

saewelo, ну вот. прекрасно! это первое правильное до конца обоснованное решение.


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

малёк не понял, что помешает в случае:  3 и 5 пирату не согласиться и зарубить вас? я был бы недоволен 1$

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

bars80080, тщательнее читай решение В) там всё написано.

читаю: 
пять пиратов, первый делит. себе забирает 998, третьему и пятому даёт по 1, остальным ничего. пираты не согласны и первого (то есть меня) убивают, 
конец. я унёс 0$

???

те кто получат по 1у.е. согласятся, так что тебя не зарубят ;)

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

Потом представил бабулек и яблоки, и что для них важнее жизнь или яблоки 

saewelo, и? таки не догоняю, коли тебя убили, задача капут... т.е. falsh, решение не правильное


 почему?
причём если согласятся, ведь делёж сразу прекращается

тоже не догнал... Им легче меня убить, и разделить как надо. 1$ ничто из 1000$.
Кстати, если несогласного пирата убивают, продолжает делить тот кто за ним? Т.е по часовой стрелке?

Изначально есть жесткое условие абстрактной задачи, без всяких вариантов а если второй договорится с третим или  если они разом не будут придерживатся правил.
Все пираты оч логические люди и знают что будет при следующем делении - кроме тебя конечно  



Это эгоцентризм батенька =)))
После тебя нету конца света и все остальные не умирают вместе с тобой  ;)
Продолжается следующая дележка но уже на четверых  и при этом 3 и 5 находятся в самых не выгодных условиях (см. ход следующего деления). 2 делит, дает деньби 4 а он притендент на смерть в следующем делении. У 3 и 5 есть два выбора или согласится с делением 2 и остаться вообще на бобах, или не согласится и умереть. Поэтому логичнее им согласится при первом делении (твоем)  при котором они получают деньгу и остаются живы.

Добавлено через 1 минуту и 26 секунд
krwlr, а какой твой вариант был?

saewelo, у меня "крысий вариант" 
Но, вопрос: Если один пират не согласен, его убивают(или что там с ним делают), начинает делить тот кто за ним?

Ага, в условии этот помент прописан


Делись красивым и коварным вариантом ;)

Добавлено через 1 минуту и 13 секунд
Тоесть если вариант делившего не подешел - о убивают только его, если вариант подошел то убивают тех кто оказался не согласен.

так ведь в условиях же чётко написано: 
так что эгоцентризм не причём, а предельно к задаче.
дальнейшая делёжка после собственной смерти суть нонсенс, там уже непофигу ли...

следовательно делёжка должна пройти в один раунд

saewelo, после того как убиваем тех кто не согласен, начинает заново делить тот кто за ним? по часовой стрелке?

P.S. это последний вопрос, ответь и напишу своё крысинное ршение =))

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

Тоесть если ты делишь:
1. твой вариант принимают большинством - то меньшинтсво убивают, деньги делят так как ты предложил  - все, игар окончена.
2. твой вариант поддержало меньшинство, то  труп только ты, деньги делят дальше по часовой стрелке.


bars80080


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

saewelo, нелогично, что делать с баблятами того(тех) несогласного(ых), которого(ых) убили?

может Кефир даст ссылку на первоисточник?

в общем тема бабок не раскрыта...

Хых ... Задачка из серии, если я такой умный, хочу быть богатым   
Тяжела пиратская жизнь... И почему они на олимпиадах задачки не решали в детстве...? Оставались бы иногда с 1$
  

Эх, что за новые веяния - убивать несогласных? В задаче, по-моему, такого не было - там убивали только делившего...


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


Истинно так.


Ох и да. Один недавний пример с Поносовым чего стоит... ;)

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