Комментарии 72
По идее на три части можно, но кому достанется 34-ая монета — это вопрос :)
НЛО прилетело и опубликовало эту надпись здесь
Нужно делить на троих — между троими самыми старшими — они тоже хотят жить.
По 1 монете самому младшему пирату и самому среднему :) Себе 98 монет и на корабль)
Идиотический топик.
Думаю нужно усложнить задачу следующим образом:
Максимизировать количество полученных монет.
Максимизировать количество полученных монет.
А разве это не подразумевается? :)
В комментах указывают решения с заточкой под 'выжить', следовательно — не очевидно что там подразумевается
Подразумевается. Я даже выделил это жирным, т.е. что все пираты — жадные негодяи), и если у старшего пирата будет возможность оставить все сто монет себе и выжить, он, несомненно, так и поступит.
Не, ну тут как — если пираты не согласны поделить все поровну — нужно составить какую-то пропорцию, при которой количество полученных монет обратно пропорционально возрасту. Потому что чем пират старше — тем менее ему будет хотеться спорить, потому что предыдущий вариант не понравится — решать придется ему. Меньше всего боится самый молодой — логично, что его надо задобрить и дать ему больше всех денег.
НЛО прилетело и опубликовало эту надпись здесь
Ну, я имел в виду, что этот вариант мы отметаем, как самый очевидный :)
НЛО прилетело и опубликовало эту надпись здесь
Ну, так можно строить бесконечное количество предположений :) Например, вдруг окажется, что у третьего умерла бабушка и ему нужно больше денег для похорон. Тогда надо вообще начать с того, что собрать анамнез на всех «товарищей».
НЛО прилетело и опубликовало эту надпись здесь
Вариант «поровну» не покатит хотя бы потому, что в таком случае будет гораздо выгоднее завалить старшего и поделить ту же сумму уже на четверых. Именно поэтому старшему надо не высовываться и взять себе меньше всех, чтобы четверо остальных не возбухали
НЛО прилетело и опубликовало эту надпись здесь
Да, уже врубился, спасибо товарищу MiXei4. Кстати, по идее, это классическая задача на динамическое программирование и она должна решаться для любого числа пиратов (разумеется, если монет хватит).
Да, так и есть. Если пираты занумерованы как 1 2 3… n по старшинству — то надо давать по одной монете 3-му, 5-му, 7-му и т.д., а остаток взять себе. Это в случае — если монет хватает.
А интересное решение получается если монет не хватает.
Если у нас K монет и N пиратов, то количество выживших пиратов будет максимальным числом вида вида A = 2*K+2L при условии что A <= N.
Если у нас K монет и N пиратов, то количество выживших пиратов будет максимальным числом вида вида A = 2*K+2L при условии что A <= N.
Не так.
Когда остается 2 и 3 пирата — да, вы правы.
Когда остается 4 пирата, то монетку надо давать второму (с конца), т.к. в случае убийства четвертого он получит ноль. Первый же в этом случае получит 1 и ему выгодно голосовать против. Третий само собой голосует против, т.к. может получить 99 монет.
Когда живы все 5, то второй голосует против, т.к. в случае расправы над пятым он получит монетку. Поэтому выгоднее всего предлагать монетки первому третьему, т.к. они, в случае расправы няд пятым получат ноль.
Когда остается 2 и 3 пирата — да, вы правы.
Когда остается 4 пирата, то монетку надо давать второму (с конца), т.к. в случае убийства четвертого он получит ноль. Первый же в этом случае получит 1 и ему выгодно голосовать против. Третий само собой голосует против, т.к. может получить 99 монет.
Когда живы все 5, то второй голосует против, т.к. в случае расправы над пятым он получит монетку. Поэтому выгоднее всего предлагать монетки первому третьему, т.к. они, в случае расправы няд пятым получат ноль.
Это очень старая задача, я решил не гуглить, а попробовать решить сам. У меня получилось, что старший пират может взять 98 монет себе и предложить по 2 монеты двум самым младшим пиратам.
Они согласятся, потому что иначе, они получили не более одной монеты. На самом деле им можно было бы предложить и по одной ведь это и есть их гарантированный выигрыш, но тогда их поведение вроде как не определяется правилами (в условиях равного выигрыша могут выбрать любой из двух вариантов).
Сейчас буду гуглить и сверяться.
Они согласятся, потому что иначе, они получили не более одной монеты. На самом деле им можно было бы предложить и по одной ведь это и есть их гарантированный выигрыш, но тогда их поведение вроде как не определяется правилами (в условиях равного выигрыша могут выбрать любой из двух вариантов).
Сейчас буду гуглить и сверяться.
Кстати, это для случая, что голос старшего учитывается. Если нет, то решение неприменимо.
100 — 2*2 = 96 :)
Я облажался, голос среднего действительно дешевле, Адмирал всё правильно решил (непонятно, почему его заминусовали): по 1 монете младшему и среднему.
Себе 98 монет, среднему 1 и младшему 1.
Я не гуглил решение, но у меня чувство, что в силу наглости и логичности проще будет при таком раскладе завалить старшего, надеясь на то, что «новый старший» предложит более честный вариант дележки :)
Я тоже не гуглил, так вышло из рассуждений.
Хотя сейчас смотрю на результат и ищу подвох, потому что выглядит нереально :)
Хотя сейчас смотрю на результат и ищу подвох, потому что выглядит нереально :)
Новый старший предложит такой вариант — Себе 99, четвертому 1.
Не намного честнее :) И четвертый согласится, потому что иначе, при убийстве второго, третий предложит себе 99 и пятому 1 и пятый уж точно согласится.
Не намного честнее :) И четвертый согласится, потому что иначе, при убийстве второго, третий предложит себе 99 и пятому 1 и пятый уж точно согласится.
А зачем соглашаться пятому? Если убьют третьего — останутся только двое, и судьба всех монет будет зависеть только от решения пятого :)
Получается, что никто не умрет в том случае, если третий и пятый пираты получают хоть что-то.
То есть, если ты справедливый старший пират, то можно смело делить поровну или в какой-то пропорции по старшинству.
То есть, если ты справедливый старший пират, то можно смело делить поровну или в какой-то пропорции по старшинству.
Суть в том, что второй и третий не смогут получить больше 1 каждый. А если уберут старшего, то они в лучшем случае останутся живы, т.к. в любом случае двое младших поделят все между собой.
Будет справедливо, продолжать в том же духе до тех пор, по тем же правилам пока не останется кто-нибудь один. Вот и счастливчик :)
Самый старший 15 монет
Второй 34 монеты
Третий 51 монета
Четверый 0 монет
Пятый 0 монет
Второй 34 монеты
Третий 51 монета
Четверый 0 монет
Пятый 0 монет
логика такая:
если останется 2 пирата — то задача не имеет решения, т.к. должно проголосовать большенство… по этому рассматриваем ситуацию с 3 пиратами… они будут делить 50/50/0… значит даем ему 51 монету — так он получит больше… остается 49 монет…
рассмотрим случай с 4 пиратами — надо, чтобы 3 из 4 проголосовали за этот вариант… делить придется 33/33/33/1 — дадим 4му пирату 34 монеты — так он будет жить и получит больше, чем при 33/33/33/1
ну и 15 монет остается самому старшему…
если останется 2 пирата — то задача не имеет решения, т.к. должно проголосовать большенство… по этому рассматриваем ситуацию с 3 пиратами… они будут делить 50/50/0… значит даем ему 51 монету — так он получит больше… остается 49 монет…
рассмотрим случай с 4 пиратами — надо, чтобы 3 из 4 проголосовали за этот вариант… делить придется 33/33/33/1 — дадим 4му пирату 34 монеты — так он будет жить и получит больше, чем при 33/33/33/1
ну и 15 монет остается самому старшему…
Задача имеет решение даже если останется 2 пирата, т.к. в условии головоломки говорится, что предложение принимается, если «по крайней мере половина пиратов» за него проголосует. Т.е. если пиратов осталось всего двое, то старший пират предложит отдать все сто монет ему. Результаты голосования будут такими: один голос «за» и один «против», а это значит, что предложение будет принято.
Пронумеруем пиратов от 1 до 5, где 5 – самый младший. Это поможет вам/нам объяснить решение задачи.
1. Если пиратов останется двое:
5-ый ничего не получит.
4-ый забирает все.
2. Если пиратов останется трое (подкупить надо одного):
4-му выгодна смерть 3-го.
Подкупаем 5-го одной монетой.
3-ий получает 99 монет.
3. Если пиратов останется четверо (достаточно подкупить надо тоже одного):
3-му выгодна смерть 2-го.
5-ый, в случае смерти 2-го, все равно получит монету от 3-го, а вот 4-ый — ничего.
Подкупаем 4-го одной монетой.
2-ой получает 99 монет
4. Когда пиратов пятеро (подкупить надо двоих):
2-му выгодна смерть 1-го.
В случае смерти 1-го, 4-ый получит монету от 2-го, а 3-ий и 5-ый пролетают.
Даем 3-му и 5-му по одной монете.
1-ый получает 98 монет.
Пронумеруем пиратов от 1 до 5, где 5 – самый младший. Это поможет вам/нам объяснить решение задачи.
1. Если пиратов останется двое:
5-ый ничего не получит.
4-ый забирает все.
2. Если пиратов останется трое (подкупить надо одного):
4-му выгодна смерть 3-го.
Подкупаем 5-го одной монетой.
3-ий получает 99 монет.
3. Если пиратов останется четверо (достаточно подкупить надо тоже одного):
3-му выгодна смерть 2-го.
5-ый, в случае смерти 2-го, все равно получит монету от 3-го, а вот 4-ый — ничего.
Подкупаем 4-го одной монетой.
2-ой получает 99 монет
4. Когда пиратов пятеро (подкупить надо двоих):
2-му выгодна смерть 1-го.
В случае смерти 1-го, 4-ый получит монету от 2-го, а 3-ий и 5-ый пролетают.
Даем 3-му и 5-му по одной монете.
1-ый получает 98 монет.
Да… действительно невнимательно прочитал условие… думал, что голосуют большинством, а не половиной…
А представим что у нас 3 пирата под номерами 1,2,3.
И 1-й оставляет все 100 монет себе и не дает ничего 2-му и 3-му. 2-й очевидно голосует против. Как должен проголосовать 3-й? Ему то пофигу по сути дела. Проголосует против — все 100 монет достанется 2-му. Проголосует за — все 100 достанется 3-му.
Ну если предположить, что он с вероятностью 1/2 выберет
голосовать
И 1-й оставляет все 100 монет себе и не дает ничего 2-му и 3-му. 2-й очевидно голосует против. Как должен проголосовать 3-й? Ему то пофигу по сути дела. Проголосует против — все 100 монет достанется 2-му. Проголосует за — все 100 достанется 3-му.
Ну если предположить, что он с вероятностью 1/2 выберет
голосовать
Тьфу блин, по энтеру стукнул случайно. Ну вы поняли…
Да у 3-го нет никаких причин, чтобы предпочесть один вариант другому. И может показаться, что старший пират всегда получит то, чего он хочет. Но это не совсем так.
Так как не дав 3-му ни копейки, он рискует лишиться жизни с большой вероятностью. А все пираты — "жадные, мыслят очень логично, и все они хотят жить".
Итак, если 1-ый умен, как это предполагается в головоломке, он попытается получить поддержку 3-го пирата, чтобы не рисковать своей жизнью. Нужно также учесть, что 1-ый пират также и жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны 1-го пирата будет дать 3-му одну золотую монету, 2-му — ничего, а ему самому — оставшиеся девяносто девять монет! Поскольку 3-ий также рассуждаете логично, то поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если 1-ый пират будет убит. Поэтому 3-ий пират проголосует за план раздела добычи, и это предложение будет принято двумя голосами.
Так как не дав 3-му ни копейки, он рискует лишиться жизни с большой вероятностью. А все пираты — "жадные, мыслят очень логично, и все они хотят жить".
Итак, если 1-ый умен, как это предполагается в головоломке, он попытается получить поддержку 3-го пирата, чтобы не рисковать своей жизнью. Нужно также учесть, что 1-ый пират также и жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны 1-го пирата будет дать 3-му одну золотую монету, 2-му — ничего, а ему самому — оставшиеся девяносто девять монет! Поскольку 3-ий также рассуждаете логично, то поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если 1-ый пират будет убит. Поэтому 3-ий пират проголосует за план раздела добычи, и это предложение будет принято двумя голосами.
Да, не дописав до конца, я все же не смог донести свою мысль. Я согласен с вашим ответом, но есть одно «но». «очень логичны» подразумевает, что мыслят исключительно в терминах мат логики, как компьютеры. Так вот, имея 2 варианта — «получить 99 монет с 100% вероятностью» и «получить 100 монет с вероятностью 50%» у компьютера нет никаких причин предпочесть один вариант другому. Просто потому, что условие задачи не говорит что приоритетней — жадность или желание жить. Это только человек очевидно выберет вариант «99 монет с 100% вероятностью».
Почему варианты 99коп×100% и 100коп×50% будут равнозначны для компьютера?
Т.е., хорошо, у компьютера нет приоритетов между жадность и жить; но у него в предложенном примере одно значение отличается на 1/100, а второе — на 1/2. 99 монет против 100 монет для жадности и 50% против 100% для жизни.
А если взять для примера 99коп×100% и 100коп×99%, то тут и человек рандомом выбрать может.
Т.е., хорошо, у компьютера нет приоритетов между жадность и жить; но у него в предложенном примере одно значение отличается на 1/100, а второе — на 1/2. 99 монет против 100 монет для жадности и 50% против 100% для жизни.
А если взять для примера 99коп×100% и 100коп×99%, то тут и человек рандомом выбрать может.
АРРРРГГХХХХ!!!
Вы все — никудышные пираты, рома мне в глотку! Такими темпами вы не протянете на острове и дня!
Первым ходом — сабля в печень второму по старшинству пирату — это отродье морского огурца метит на мое место!
Затем — выхватываю пистоль и пускаю пулю в лоб 4му пирату. 1к медуз, он никогда мне не нравился, клянусь своим деревянным окороком!
Пятый, самый младший пират, — Джим, — он уже на моей стороне, я подговорил этого сосунка еще перед высадкой на остров, пообещал дать ему порулить галеоном. Джим уже всадил свой нож под ребра 4му пирату.
А дальше уже — по предложенной схеме: я предлагаю 99 монет мне и 1 монету Джиму, один голос «за», один — «против». Половина согласна. Я наклоняюсь за деньгами. Щенок Джим бьет меня ножом в шею. Перед тем, как упасть, я успеваю выстрелить в него из моего секретного пистоля в крюке.
Всё, каррамба! Все мертвы, деньги не пригодились.
Вот это — по-пиратски.
P.S. Простите,… я просто представил себя старшим пиратом, а потом как-то все закрутилось, пошло-поехало… А задачка интересная, спасибо :)
Вы все — никудышные пираты, рома мне в глотку! Такими темпами вы не протянете на острове и дня!
Первым ходом — сабля в печень второму по старшинству пирату — это отродье морского огурца метит на мое место!
Затем — выхватываю пистоль и пускаю пулю в лоб 4му пирату. 1к медуз, он никогда мне не нравился, клянусь своим деревянным окороком!
Пятый, самый младший пират, — Джим, — он уже на моей стороне, я подговорил этого сосунка еще перед высадкой на остров, пообещал дать ему порулить галеоном. Джим уже всадил свой нож под ребра 4му пирату.
А дальше уже — по предложенной схеме: я предлагаю 99 монет мне и 1 монету Джиму, один голос «за», один — «против». Половина согласна. Я наклоняюсь за деньгами. Щенок Джим бьет меня ножом в шею. Перед тем, как упасть, я успеваю выстрелить в него из моего секретного пистоля в крюке.
Всё, каррамба! Все мертвы, деньги не пригодились.
Вот это — по-пиратски.
P.S. Простите,… я просто представил себя старшим пиратом, а потом как-то все закрутилось, пошло-поехало… А задачка интересная, спасибо :)
А пираты-то сомалийские? :)
отличная задачка!
у нас в компании похоже по такому принципу в конце года начальство делят бонусы
у нас в компании похоже по такому принципу в конце года начальство делят бонусы
мм… а можно здесь поподробней?)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пять пиратов