| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Флейм > Очень интересная задачка |
| Автор: Kefir 1.5.2008, 16:49 | ||
| Привет, мне довольно давно задавали очень интересную задачу. Очень долго ломал голову как она решается. Могу сказать - если вы любите головоломки, то решение этой вам должно понравиться. Да, кстати, господа, если вы уже знаете решение этой задачи (слышали или читали где) - не постите решение, дайте людям подумать без спойлеров. Просто напишите "а я знаю!" и похохатывайте В) Сразу предупреждаю - задача без подвохов, тут нет никаких уловок. Тут красивое логическое решение. Итак, задача: Вы - пират. Со своими друзьями вы награбили 1000$ и теперь вы все сидите за круглым столом и делите добычу. Всего пиратов пятеро (включая вас). Процесс делёжки проходит следующим образом: первый пират (а это как раз вы) предлагает свой способ разделения денег. Далее все пираты (включая делящего) голосуют. Способ разделения принимается в том случае, если он набрал как минимум 50% голосов (3 из 5, 2 из 4, 2 из 3 или 1 из 2). Если же способ не принят - делившего убивают и делит следующий пират (по часовой стрелке). Делёжка начинается с вас. Как надо разделить деньги так, чтобы вас не убили и чтобы вы получили наибольшее возможное количество денег? Учтите, что все пираты великолепно разбираются в логике! Для пущей ясности - вот так вы сидите за столом. Вы - номер 1. После вас (если вас убьют) делит номер 2 и так далее.
|
| Автор: krwlr 1.5.2008, 16:59 |
| а если мой способ других устраивает а одного не устраивает? Его убивают? Если да то у меня есть решение |
| Автор: v2v 1.5.2008, 17:37 |
| не понятно как принимают решения пираты? сколько какому пирату хватит , а сколько будет мало? и какую минимальную сумму должен получить каждый пират? Добавлено через 2 минуты и 39 секунд я максимально могу забрать себе 499$ ? |
| Автор: Kefir 1.5.2008, 17:58 | ||
| krwlr, если за твой способ проголосуют три пирата (50%+ от всех голосов), тогда уже наплевать на остальных двух пиратов. v2v, в задаче всё описано. каждый пират, естесственно, хочет получить как можно больше денег. делить общуу сумму можно на целые числа (к примеру, нельзя предлагать 0.5 доллара) - предлагать можно суммы от 0 до 1000 долларов. например, можно предложить такой раздел: себе 200, а остальным 1, 199, 250 и 350. решение однозначное, никаких "а может быть?".
во-первых, почему? во-вторый, нет В) |
| Автор: Joil 1.5.2008, 18:08 |
| Kefir, правильно или нет: Себе 415, Второму 251, Третьему 334, Четвёртому 0, Пятому 0? --- Тысячи чертей!!! Я Убью тебя!!!  |
| Автор: Kangaroo 1.5.2008, 18:17 | ||
| Когда-то решал.. Правильное решение помню смутно 
Вроде нет |
| Автор: krwlr 1.5.2008, 18:33 |
| себе все бабки =)) |
| Автор: v2v 1.5.2008, 18:50 | ||
от обратного. всех убили остался только 3 и 4. 3й делит и берёт всё себе - голосует 1 - За. 1 - Против. Поделено. Значит 4й согласится на любую сумму больше 0: даём ему 1$. и ещё 1$ дадим второму. потому что если меня убъьют и делить будет 1й , то он возмёт 999 себе и даст 1$ 4му. 2й тоже получит ноль. Значит 998 $ берёт себе ? Добавлено @ 03:00 я тут перепутал номера : 5й - это Я. |
| Автор: saewelo 1.5.2008, 20:05 | ||
Не.. скорее наоборот. Себе 1$ (так как первый в очереди на умервшление) 5ому тоже 1$ 4ому 998$ - так как он будет последний из выживших при худшем раскладе. |
| Автор: v2v 1.5.2008, 20:16 |
| блин я там номера поперепутывал!!!!((( Добавлено через 24 секунды в том моём расчёте 5й - ЭТО Я |
| Автор: maxim1000 1.5.2008, 20:46 |
мне эту задачку задали на собеседовании судя по тому, что взяли, решение понравилось |
| Автор: Str!pe 1.5.2008, 21:45 |
| Можно я испорчу всем гадания? Можно? |
| Автор: v2v 1.5.2008, 21:55 | ||
так а чё гадать. я ведь правильно решил, так ли. |
| Автор: Kefir 1.5.2008, 22:33 | ||
v2v,
этот вывод не обоснован почти никак, значит, дальнейшие выводы тоже необоснованы  Добавлено через 1 минуту и 38 секунд saewelo, таких решений я ещё, пожалуй, не слышал В) maxim1000, Str!pe, подождите, пипл отпишется - тогда, а то так ведь неинтересно В) |
| Автор: Rodman 1.5.2008, 22:43 |
| чуваки... давай те до вторника подождем... а то праздники+выходные... думать не очень настроен.. а в понедельник или вторник подумать мона! |
| Автор: krwlr 1.5.2008, 22:58 |
| я кажется знаю как все бабки себе забрать(у меня крысья натура - ничего удивительного ), хотя не знаю если правильно... Добавлено через 7 минут можно писать? никто не обидется? |
| Автор: saewelo 1.5.2008, 23:21 |
| Если смотреть с конца и кто где будет трупом... То себе (как первому) - 998, третьему - 1, пятому - 1. (Если третий и пятый не соглашаются то при следующей дележке - они трупы.) Если не так, тогда бум считать что меня жадность сгубила |
| Автор: krwlr 1.5.2008, 23:33 |
| saewelo, какая жадность? какая сгубила? Вот я жадный, у меня вообще по расчету все баблята себе забираю |
| Автор: SelenIT 1.5.2008, 23:38 |
| Тоже попробовал распутывать с конца... Если остались два пирата: четвертый берет все себе, пятый в пролете. Следовательно, если остались трое, третьему (чтобы выжить) достаточно задобрить пятого, который согласен на любую сумму (если он не согласится, очередь дойдет до четвертого, который оставит его с ничем). Поэтому третий может претендовать на 999 $. Если остались четверо, уже интереснее. На первый взгляд кажется, что второму достаточно задобрить тем же одним баксом того же пятого, прокатив жадных третьего и четвертого. Но с другой стороны, он может задобрить и четвертого (которому важно, чтобы очередь не дошла до третьего, который оставит его с ничем). По той же логике, четвертый тоже должен быть доволен одним баксом - если он откажется, третий не даст ему и этого . Получается, что если делит второй - так или иначе в пролете третий. Давать что бы то ни было третьему второму не выгодно - тот в любом случае проголосует против, чтобы получить свой ход и свои 999 $.Теперь смотрим, что может получить каждый из пиратов в исходном раскладе, в зависимости от того, как он будет голосовать. Видно, что самые реальные шансы получить хороший куш - у второго, поэтому он нам явно не союзник, на него сразу забиваем. Третьему важно, чтобы очередь не дошла до второго - он будет за нас даже за один бакс. Остаются 999 $, и нужно купить еще один голос, притом верняк. И четвертый, и пятый могут надеяться на что-то, если очередь дойдет до второго, так что любой из них может проголосовать против. У пятого шансов больше - он получит гарантированный бакс даже в том случае, если проголосует и против второго (позволив делить третьему). Четвертый, если проголосует против нас, теоретически может остаться с ничем. Поэтому второй бакс - ему, остальное себе. Вроде совпало с решением v2v... |
| Автор: Kefir 2.5.2008, 08:14 | ||
| saewelo, за такое решение вам бы больше одного балла из 10ти на олимпиаде не поставили (собоснованием - угадал ответ). SelenIT, наконец то, человек, который ясно излагается В) Есть небольшой ньюанс - у тебя немного неверные рассуждения в последнем абзаце, а также нет чёткого вывода в предпоследнем абзаце. Из этого опять же из-за этого выплывают ошибки. Ты пишешь:
достаточно ли? скажем так, можно ли надеятся на пятого? ведь обязательно надо действовать наверняка. одна промашка и второй - труп. |
| Автор: saewelo 2.5.2008, 11:07 | ||
Мы не на олимпиаде, и не разжеван ответ только потому что бы остальным все еще было интересно отгадывать, так ведь договаривались? 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 смело оставляет за бортом. Логика в том что надо задабривать тех кто при следующей дележке остается или без денег, или трупом - это проще просчитать с конца. |
| Автор: Kefir 2.5.2008, 11:21 | ||
saewelo, ну вот. прекрасно! это первое правильное до конца обоснованное решение.
ну, я имел в виду тех, кто эту задачу ранее не встречал. просто чтобы сразу правилное решение они не выкладывали. а от тех, кто видит задачу в первый раз решение-то и надо В) |
| Автор: bars80080 4.5.2008, 11:46 | ||
малёк не понял, что помешает в случае:
мало того, как я понимаю, если делёжка проходит, то она прекращается. а раз начинаем с себя, то нам надо решить делёж с одного раза, чтобы уйти живым. |
| Автор: Kefir 4.5.2008, 11:47 |
| bars80080, тщательнее читай решение В) там всё написано. |
| Автор: bars80080 4.5.2008, 12:27 | ||
читаю:
пять пиратов, первый делит. себе забирает 998, третьему и пятому даёт по 1, остальным ничего. пираты не согласны и первого (то есть меня) убивают, конец. я унёс 0$ ??? |
| Автор: v2v 4.5.2008, 12:41 |
| те кто получат по 1у.е. согласятся, так что тебя не зарубят ;) |
| Автор: saewelo 4.5.2008, 12:48 | ||
Тоже вначале так рассуждая сразу видел, что ну не реально между пиратами так просто поделить - ну скверно-взбалмащный народ.) Потом представил бабулек и яблоки, и что для них важнее жизнь или яблоки |
| Автор: bars80080 4.5.2008, 13:05 | ||
saewelo, и? таки не догоняю, коли тебя убили, задача капут... т.е. falsh, решение не правильное
причём если согласятся, ведь делёж сразу прекращается |
| Автор: krwlr 4.5.2008, 13:34 |
| тоже не догнал... Им легче меня убить, и разделить как надо. 1$ ничто из 1000$. Кстати, если несогласного пирата убивают, продолжает делить тот кто за ним? Т.е по часовой стрелке? |
| Автор: saewelo 4.5.2008, 13:35 | ||
| Изначально есть жесткое условие абстрактной задачи, без всяких вариантов а если второй договорится с третим или если они разом не будут придерживатся правил. Все пираты оч логические люди и знают что будет при следующем делении - кроме тебя конечно
Это эгоцентризм батенька =))) После тебя нету конца света и все остальные не умирают вместе с тобой ;) Продолжается следующая дележка но уже на четверых и при этом 3 и 5 находятся в самых не выгодных условиях (см. ход следующего деления). 2 делит, дает деньби 4 а он притендент на смерть в следующем делении. У 3 и 5 есть два выбора или согласится с делением 2 и остаться вообще на бобах, или не согласится и умереть. Поэтому логичнее им согласится при первом делении (твоем) при котором они получают деньгу и остаются живы. Добавлено через 1 минуту и 26 секунд krwlr, а какой твой вариант был? |
| Автор: krwlr 4.5.2008, 13:43 |
| saewelo, у меня "крысий вариант" Но, вопрос: Если один пират не согласен, его убивают(или что там с ним делают), начинает делить тот кто за ним? |
| Автор: saewelo 4.5.2008, 13:47 | ||
Ага, в условии этот помент прописан
Делись красивым и коварным вариантом ;) Добавлено через 1 минуту и 13 секунд Тоесть если вариант делившего не подешел - о убивают только его, если вариант подошел то убивают тех кто оказался не согласен. |
| Автор: bars80080 4.5.2008, 13:58 | ||
так ведь в условиях же чётко написано:
так что эгоцентризм не причём, а предельно к задаче. дальнейшая делёжка после собственной смерти суть нонсенс, там уже непофигу ли... следовательно делёжка должна пройти в один раунд |
| Автор: krwlr 4.5.2008, 14:02 |
| saewelo, после того как убиваем тех кто не согласен, начинает заново делить тот кто за ним? по часовой стрелке? P.S. это последний вопрос, ответь и напишу своё крысинное ршение =)) |
| Автор: saewelo 4.5.2008, 14:18 | ||
| krwlr, если я правильно уловил сутть твоего вопроса - то нет. Когда убивают тех которые не осгласены, то это подрозумевает под собой что деньги уже поделили. Тоесть дележ продолжается только после смерти того кто делил. Тоесть если ты делишь: 1. твой вариант принимают большинством - то меньшинтсво убивают, деньги делят так как ты предложил - все, игар окончена. 2. твой вариант поддержало меньшинство, то труп только ты, деньги делят дальше по часовой стрелке. bars80080
Да, согласен. Но для это тебе нужно учесть кому и сколько давать. То есть просчитать худший вариант -- тебя убили и что будет дальше, кто будет в невыгодном положении , поддержкой тех пиратов и надо заручится. |
| Автор: krwlr 4.5.2008, 14:23 |
| saewelo, нелогично, что делать с баблятами того(тех) несогласного(ых), которого(ых) убили? |
| Автор: bars80080 4.5.2008, 14:28 |
| может Кефир даст ссылку на первоисточник? |
| Автор: krwlr 4.5.2008, 14:36 |
| в общем тема бабок не раскрыта... |
| Автор: ksnk 4.5.2008, 14:55 |
| Хых ... Задачка из серии, если я такой умный, хочу быть богатым Тяжела пиратская жизнь... И почему они на олимпиадах задачки не решали в детстве...? Оставались бы иногда с 1$ |
| Автор: SelenIT 5.5.2008, 00:10 | ||||||||
Эх, что за новые веяния - убивать несогласных? В задаче, по-моему, такого не было - там убивали только делившего...
До окончания дележки все баблята в общаке. После окончания дележки все невезучие уже жмурики и в баблятах не нуждаются (хоронить пиратов дешево, акулы денег за погребение не берут;)
Истинно так.
Ох и да. Один недавний пример с Поносовым чего стоит... ;) А что касается пиратов в задаче - представляю, как они дрались за право делить первым по таким условиям... |
