Классическая математическая игра, в которой пятерым пиратам предлагается разделить между собой клад из 100 монет, имеет менее известную вариацию, в которой пиратов 100, а монет всего пять.
100 пиратов должны разделить между собой 5 золотых монет. Согласно пиратскому кодексу, делёж добычи происходит следующим образом. Все пираты строго упорядочены по старшинству. 100-й (самый старший) пират предлагает способ распределить монеты между присутствующими и выносит его на голосование. При этом сам он участия в голосовании не принимает. Если его способ получает одобрение хотя бы половины остальных участников, то так и происходит, и на этом делёж заканчивается. В противном случае его выкидывают за борт, а право предложить свой способ получает следующий по старшинству (99-й), и так далее.
Принимая решение, пираты руководствуются следующими приоритетами:
1. Каждый пират хочет выжить.
2. Каждый пират хочет забрать себе как можно больше.
3. При прочих равных условиях, каждый пират предпочтёт выкинуть другого за борт.
Чьё предложение будет в итоге принято?
100 пиратов должны разделить между собой 5 золотых монет. Согласно пиратскому кодексу, делёж добычи происходит следующим образом. Все пираты строго упорядочены по старшинству. 100-й (самый старший) пират предлагает способ распределить монеты между присутствующими и выносит его на голосование. При этом сам он участия в голосовании не принимает. Если его способ получает одобрение хотя бы половины остальных участников, то так и происходит, и на этом делёж заканчивается. В противном случае его выкидывают за борт, а право предложить свой способ получает следующий по старшинству (99-й), и так далее.
Принимая решение, пираты руководствуются следующими приоритетами:
1. Каждый пират хочет выжить.
2. Каждый пират хочет забрать себе как можно больше.
3. При прочих равных условиях, каждый пират предпочтёт выкинуть другого за борт.
Чьё предложение будет в итоге принято?
Того, кто говорит 18-м (73 с конца)?
ОтветитьУдалитьВообще, выживает первый говорящий при количестве пиратов 9+2^n (n>=1)
Индукция. Раз выживают 9+2^k последних говорящих, то 4+2^k из них будут точно голосовать против того, чтобы остаться с нулём. Чтобы их компенсировать их голоса надо подкупить выживанием или деньгами 8+2^(k+1) человек.
Если пиратов не меньше 11, на подкуп достаточно одной монетки, (найдутся пятеро, которые иначе остались бы с нулём)
База -- 11-й с конца точно выживет (он может перекупить пятерых, которые при десяти оставшихся не получили бы монету).
Стоп-стоп. Чтоб было легче разбираться. Пусть монет всего две. Ты уверен, что 4-й с конца точно выживет? А если нет, то 5-му его не нужно перекупать, - он куплен уже самой необходимостью выживания. Иными словами, на двух монетах индукция начинается раньше. Почему на пяти монетах она начинается с 11, а не раньше?
УдалитьЯ зачем мне индукцию начинать раньше? Я начал при k=1, кажется вполне достаточным. При малых количествах другие соображения.
УдалитьПри пяти. Мне всё равно, выживет ли 4 с конца. Пусть ты решил задачу для четырёх, все пираты знают это решение. При нём двое конкретных пиратов без монетки, значит они согласятся на выгодное предложение пятого. То есть пятый выживет, а получит ли деньги -- это другой вопрос.
На самом деле задача сформулирована не очень чётко и я не уверен, что могу дать точные ответы при n<=10. Нужно ещё что-то типа "при прочих равных пират предпочтёт дать деньги более старшому". Или "при прочих равных разделит случайным образом". Но моё рассуждение действительно даже в последнем случае, просто вместо "получил 0" надо читать "матожидание прибыли меньше 1".
Вот да, насчет нечеткости формулировки я согласен. В том и фишка, что "Пусть ты решил задачу для четырёх, все пираты знают это решение." предполагает, что решение единственно. А если нет, то там нужно знать матожидания, при этом это знание должно быть общим, иначе непонятно как проголосуют те получатели одной монетки, у кого матожидание при меньшем числе игроков и так близко к 1 (но меньше 1), если это матожидание означает что-то типа "в трех случаях получаю две монетки, в четырех - 0".
УдалитьНо это - при недоформулированности условия - уже психологический вопрос (типа парадокса с двумя ящиками и миллионом долларов в одном из них), а не математический.
Ну вот разбери, пожалуйста, задачу в формулировке "при прочих равных предпочтение отдаётся более старшему". У меня там получается именно тот клинч, который я описал выше для задачи с двумя монетами. Дело в том, что при 8 людях дележ будет таким: трое получат по 1, еще один - 2, остальные четверо - по нулю. Соответственно, для 9 людей (девятому нужно 4 голоса) монеты достаются ровно тем, кто у 8 получал по нулю, а последняя монета уходит себе. Без денег остаются четверо. Но тогда для 10 людей (десятому нужны пять голосов) не хватает денег для получения пятого голоса, и 10-го убивают.
Да ради бога, пусть его убивают. Или не убивают. Какое мне до него дело, у нас же в задаче сто человек.
УдалитьЯ как раз специально не интересуюсь, что там было у первых десяти. Это не важно для моего решения Одиннадцатый точно выживет и баста. Ну оставит себе ещё монетку, если ты прав про десятого. А 12-й, значит, не выживет. И поехали.
Еще раз. Ты пишешь про 11-го "найдутся пятеро, которые иначе остались бы с нулём". Это так, если бы перед этим существовал способ провести предложение от 10-го. А если нет, то этот аргумент уже не может НЕ опираться на предыдущую индукцию. Вот я написал про то, что 9-й выживает, а 10-й нет, и ты на этом довёл решение до конца. А если бы расклад был другим, то просто так про 11-го было бы ничего нельзя сказать.
УдалитьНикакой предыдущей индукции нет.
УдалитьЯ не понимаю, кто из нас чего не понимает :)
Если предложение десятого не проходит, то проходит предложение кого-то другого. Если всё детерминированно (а это так), то в результате у вопроса "кто из десяти в результате погибнет, и кто из оставшихся получит сколько денег, если 11-го убьют?" есть однозначный ответ, который знают все 11 пиратов. Ну, то есть в данном случае ответ видимо "один мёртвый, у четверых ноль, у пятерых монетка",
но мы с тобой не обязаны были его вычислять, достаточно того, что он вычислим. Так вот, каким бы этот ответ ни был, мёртвых и бедных в сумме не меньше пяти. И опять же все точно знают, кто эти люди. Одиннадцатый заплатит бедным, возьмёт остаток себе и выживет.
Это рассуждение работало бы при любом способе задать "четвёртое" условие. Надо только чтобы все пираты соблюдали в своих рассуждениях три базовых условия и всё друг про друга знали, то есть могли бы точно сказать, кто с какой вероятностью какое решение кто примет в каждой спорной ситуации.