Заключенные и переключатель
Задача
В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:
«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».
После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.
Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?
Подсказка
Казалось бы, как заключенный, которого привели в комнату, может воспользоваться тем, что видит переключатель в положении ON? И если он переключит его на OFF — как следующему заключенному воспользоваться этим?
Тем не менее стратегия, гарантированно приводящая узников к спасению, существует. Например, узники могут разбить дни на декады (10-дневные промежутки) и договориться, что дожидаются такого вот события: первого из них заведут в комнату в первый день декады, второго — во второй день и т. д., десятого — в последний день. Поскольку вероятность такого события отлична от нуля, то рано или поздно оно произойдет! Догадайтесь, как они могут действовать, чтобы 10-й смог понять,что такое событие в данной декаде на самом деле произошло.
Решение
1. Самый простой, но и самый долгий вариант — действовать так, как было сказано в подсказке. Чтобы просигнализировать последнему, каждый из заключенных, которого завели в комнату НЕ В СВОЙ день, должен поставить переключатель в положение ON. Если же 10-й заключенный действительно оказался в комнате на 10-й день декады и видит переключатель в положении OFF, он немедленно говорит начальнику тюрьмы, что в комнате побывали все заключенные. Если в 10-й день в комнате оказался кто-то другой или же 10-й видит переключатель в положении ON, то всё начинается заново...
Это решение, несмотря на всю свою простоту, плохо в главном — бедным узникам придется слишком долго ждать. Действительно, из всех возможных 1010 вариантов посещения ими комнаты в течение декады их устраивает только один — таким образом, вероятность p их выхода на волю в течение одной декады равна 1/1010. Сравнительно несложными вычислениями можно доказать, что среднее время, которое потребуется им на освобождение, равно 1/p = 1010 декад, или 1011 дней, или более 270 миллионов лет. В общем, столько люди не живут.
2. Однако это же решение подсказывает, как они могут ускорить свой выход на свободу. Для этого они должны дожидаться следующего события: в течение декады каждый из 10 человек побывал в комнате ровно один раз. Как такое событие «сигнализируется»? Да почти так же: если кого-нибудь заводят второй раз в одной декаде, он ставит переключатель на ON. Таким образом, если на 10-й день декады узник, которого туда отвели, оказался там впервые (за декаду) и видит переключатель в положении OFF, он сообщает начальнику тюрьмы, что всех можно освобождать.
Этот способ работает уже существенно быстрее, потому что количество благоприятных исходов теперь не 1, а 10! = 3628800. Это означает, что вероятность p' выхода на свободу за первую же декаду не так уж и мала — она равна 0,00036288. Следовательно, ожидаемое число декад до выхода равно 1/p' ≈ 2755, то есть освободятся они примерно через 75 лет. Так что кто-нибудь, может быть, и доживет до освобождения, хотя особо надеяться на это не стоит.
Неужели всё так печально?
3. К счастью, у заключенных существует принципиально другой способ действий.
Например,они могут договориться о том, что тот, кого заведут в комнату в первую ночь, выставляет переключатель на OFF и становится СЧЕТЧИКОМ. Остальные заключенные остаются ОБЫЧНЫМИ. Каждый обычный заключенный должен передать счетчику ровно один сигнал о своем попадании в комнату с переключателем. Это делается так: попав туда, обычный заключенный смотрит на положение переключателя. Если оно OFF, то заключенный ставит его на ON и считает сигнал переданным. Если же выключатель уже находится в положении ON, то заключенный ничего не делает — иначе говоря, ждет следующего подходящего случая.
Счетчик, попадая в камеру и видя переключатель в положении ON, понимает, что ему передали сигнал (запоминает это), а чтобы сделать возможной передачу следующего сигнала — ставит переключатель в OFF. Если же он видит переключатель в OFF, то ничего не делает и тоже ждет следующего раза.
Как только счетчик примет 9-й сигнал, он сразу же сообщает об этом начальнику тюрьмы.
Как долго продлится их отсидка при такой стратегии? Сосчитать это уже не столь просто, как раньше, потому что вероятность того, что заключенному в очередной день удастся передать сигнал, постепенно уменьшается от 9/10 для первого сигнала до 1/10 для последнего сигнала. В то же время вероятность попадания в комнату Счетчика в любой момент равна 1/10. Тем не менее механизм подсчета в целом аналогичен: до момента передачи первого сигнала в среднем пройдет 10/9 дня, а до момента его приема Счетчиком — еще 10 дней. Затем на второй сигнал уйдет 10/8 + 10 дней, на третий — 10/7 + 10, и так далее. Итого 
дней — совсем не так много, как в предыдущих решениях.
Послесловие
А не существует ли еще более быстрой стратегии действий?
Для 10 заключенных, возможно, и нет, а вот для большего количества — есть. Автор этой стратегии Б. Фельгенауэр назвал ее «пирамидальной».
Чтобы ее было проще понять, давайте будем считать,что количество заключенных равно степени двойки, например 64. Как и в предыдущем решении, каждый должен либо отдать сигнал (ровно один), либо собрать все сигналы. Для того чтобы им было сподручнее это делать, все ночи разбиты на участки разной «стоимости»: сначала идут «1-ночи», в течение которых все отдают либо принимают одинарные сигналы, затем идут «2-ночи», в течение которых все отдают либо принимают «двойные» сигналы, то есть каждый сигнал сообщает о двоих заключенных, затем наступают «4-ночи», «8-ночи», и т. д. Если всё происходит успешно, то когда дело доходит до «32-ночей», носителями сигналов остаются ровно двое заключенных, и в течение 32-ночей один из них отдает свой сигнал другому, после чего тот понимает, что собрал коллекцию из всех 64 сигналов, и значит, в комнате побывали все.
Разумеется, такая «успешность» может и не случиться, поэтому после 32-ночей весь цикл 1-, 2-, 4-, 8-, 16-, 32-ночей повторяется сначала.
Как же происходит отдача и прием сигналов в пирамидальной схеме?
А вот как: если во время k-ночи заключенный пришел в комнату и видит переключатель в положении ON, то он принимает k-сигнал и ставит переключатель в OFF. Если к этому моменту у него уже был один k-сигнал, то теперь у него есть два таких сигнала, или один 2k-сигнал (который он попытается либо отдать, либо снова удвоить в период 2k-ночей). Если же он пришел в комнату со своим k-сигналом и видит OFF, то он ставит ON и считает k-сигнал отданным.
Вот, в целом, и всё. Остальное уже является занудными техническими подробностями (какова должна быть продолжительность ночей определенного типа для того, чтобы передача всех нужных сигналов состоялась с достаточной вероятностью, и при этом не было слишком большой задержки перед наступлением следующего типа ночей).
Эта задача имеет самое прямое отношение к теории информации — она демонстрирует, что даже самый узкий (всего 1 бит — ON/OFF) канал позволяет передать достаточно много информации.
Кто именно является автором «тюремной» формулировки, мне неизвестно, но именно эта забавная формулировка буквально покорила мир. Кроме того, несмотря на относительную молодость задачи, она уже успела обрасти кучей самых неожиданных вариаций и усложнений. Например:
Два переключателя. В комнате, куда приводят заключенных, не один, а целых два переключателя (следовательно, выйти на свободу можно быстрее. Вопрос: насколько?)
Две комнаты. Заключенных водят не в одну, а в две разных комнаты, выбирая их также случайным образом. В каждой комнате — свой переключатель.
Разделение передатчика и приемника. Каждую полночь начальник тюрьмы ставит переключатель в положение OFF. В час ночи он приводит туда первого заключенного, потом уводит, а в два часа ночи приводит туда же второго. Таким образом, первый из них должен «сработать» передатчиком информации, а второй — приемником.
Злобный начальник. Начальник тюрьмы знает стратегию узников и каждый день выбирает для посещения комнаты такого заключенного, чтобы максимально затруднить узникам их задачу.
-
Спасибо за интересную задачу.
Она вызвала 10-страничное обсуждение на форуме GotAI
http://gotai.net/forum/Default.aspx?postid=55333#55333
где за три дня разными авторами (я буду указывать их ники)
удалось найти решения, существенно лучше приведенных здесь.-
Во-первых, предложен продвинутый аналог решений 1 и 2 (автор Egg).
Он позволяет снизить время ожидаемого выхода до ~1.5 лет за счет использования каждым заключенным массива отметок.
1. Во время совещания, заключенные нумеруют себя от 0 до 9;
2. Выделяют память для счетчика дней (глобальный индекс, синхронизируется по факту смены дня) и массива "посещений" размером 10 (начальное значение = 0000000000), каждый из заключенных имеет свой индивидуальный массив;
3. Если заключенный приходит в комнату и видит флажок в состоянии 1, то в своем массиве в позиции остатка от деления на 10 индекса предыдущего дня взводит 1;
4. Если заключенный приходит в комнату в день, когда остаток от деления на 10 совпадает с его номером, то он взводит флажок в 1, если не совпадает, то в 0. Если в массиве посещений у заключенного есть 1 в позиции остатка от деления на 10, то он также взводит флаг в позицию 1;
5. Как только у одного из заключенных массив становится равным 1111111111 он идет стучать начальству, что каждый из заключенных побывал в комнате. -
-
Если Счетчиком будет становиться второй посетитель, а не первый,
то в 9 из 10 случаев ему останется принять 8 сигналов, а не 9 (автор Egg).
Но ещё лучше, если счётчиком будет третий (автор Андрей).
При этом договорённость должна быть такая: первый устанавливает выключатель в 1.
Второй (если это другой заключённый, не тот, кто был первым) устанавливает выключатель в 0.
Тогда третий делает вывод: если выключатель в положении 0, значит до него тут были 2-ое,
если в положении 1 - значит 1 заключённый.
Если три (или два) раза был один и тот же - тривиально.
не по одному за ночь, а с каким угодно интервалом (автор Trilobite).
При таком раскладе никто из заключенных не знает порядкового номера своего посещения,
и надо как-то обойти неопределенность исходного положения переключателя.
Решение состоит в том, что Счетчика выбирают на собрании,
а каждый из 9 рядовых заключенных должен переключить 0 --> 1 не один, а два раза.
Счетчик считает теперь уже до 18.
А была ли одна из этих 18-ти единиц выставлена заключенным
или это единица из начального положения переключателя, значения не имеет.
На собрании заключенные договариваются о том, что первые 6 ночей будут ночами выбора счетчика. Заключенный пришедший в 1 ночь переводит переключатель в положение ON, тем самым голосует за себя. В последующие ночи выборов заключенные пришедшие в первый раз, если видят положение ON, то оставляют его в ON, таким образом голосуя за себя. Первый заключенный пришедший в ночь выборов во второй раз и увидевший ON становится счетчиком и подсчитывает всех заключенных побывавших в комнате (ночь прихода во второй раз минус один), а также переводит переключатель в OFF, объявляя выборы состоявшимися. Если после первой ночи выборов, но в течении ночей выборов приходит в комнату не голосовавший заключенный и видит положение OFF, то он ничего не делает и не считает себя проголосовавшим, так как выборы уже состоялись. Если в ночь выборов повторно приходит проголосовавший и видит OFF, то он ничего не делает. Если на 6 ночь в комнату приходит ранее в ней не бывавший заключенный и видит ON, то он считает себя счетчиком, подсчитывает голосовавших участников (их 6 включая его самого) и переводит переключатель в положение OFF. На 7 ночь начинается подсчет не проголосовавших заключенных. Если в ночи подсчета приходит не голосовавший и видит положение OFF, то переводит в ON и считает себя проголосовавшим. Если в ночи подсчета приходит не голосовавший и видит положение ON, то ничего не делает. Голосовавшие (кроме счетчика, разумеется) ничего в комнате не делают при любом положении переключателя. Пришедший в ночи подсчета счетчик подсчитывает положения ON и если положение ON, то переводит в OFF, если же в ночь прихода было OFF, то ничего не делает. После того как счетчик насчитает 10 заключенных, он объявляет начальнику, что все побывали в комнате.
В среднем через 95 ночей все будут на свободе (статистика 1000000 игр без ложного срабатывания и при средней жизни заключенного 100 лет, они ни разу более года не играли).
-
Уже после своего второго сообщения решил погуглить и нашел в англоязычном варианте интересный документик http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBul
b.pdf. Там в принципе описан мой вариант и называется динамический счетчик. Только та стратегия уступает моей на 3 дня. У того алгоритма выборы заканчиваются в день равный количеству заключенных, таким образом теряются драгоценные дни, в погоне за золотым вариантом, когда в последний день выборов приходит единственный еще не приходивший заключенный, стратегия натыкается на маловероятную ситуацию, не приносящую реальной экономии времени. ИМХО -
-
Да, эту дату можно посчитать, тока это нудно и неинтересно. Там надо складывать туеву кучу цифр. И думать какие цифры складывать :) Чисто техника, в которой я не силен. Будет время подумаю, как получить дату окончания выборов, для 10 заключенных подбором можно быстро ее найти, а для 1000 - легче и быстрее формулу написать.
-
-
То есть, если во второй день в комнату заходит тот же, кто был там в первый день, он переводит переключатель в OFF, но не считает себя счетчиком. Если тот, кто приходит на третий день, видит ON, то это означает, что до него там были разные люди и он действует как в вашем описании. Если же он видит OFF, то он знает, что до него там был только 1 человек, в этом случае он считает того человека и себя (1 если все три раза был один и тот же и 2 в остальных случаях), оставляет переключатель в OFF и считает себя счетчиком. С четвертого дня все идет по вашему описанию.
Таким образом, вероятность ситуации, что за первые 6 дней будет посчитан только 1 заключенный, снижается с 10 до 1 процента.
При такой стратегии в среднем потребуется ~93.4 дня.
Если на 6 ночь в комнату приходит ранее в ней не бывавший заключенный и видит OFF, то он считает себя проголосовавшим, и переводит переключатель в положение ON. Таким образом он передает сигнал для первой ночи подсчета.
Итого вместе с предложением о минимальном количестве дней голосования равным 3 и максимальным равным 6 дням получаем примерно 93,389 ночь.
-
Ну да, я в том, что описал выше, это тоже предполагал (мне почему-то казалось, что в вашем алгоритме это уже учтено). Это дает дополнительный выигрыш примерно 0.7 дня.
-
Можно улучшить еще на несколько десятитысячных (точно не считал, но порядок где-то такой), но вряд ли имеет смысл усложнять алгоритм из-за такого мизерного выигрыша.
Если интересно, сделать это можно так: все, кто побывал в комнате и не стал счетчиком становятся "неофициальными счетчиками". Они не меняют положение переключателя, но отмечают изменения. Если переключатель выключен - в комнате побывал счетчик, если потом включился, значит побывал кто-то непосчитанный и т.д.(в первые 6 дней следят согласно правилам для первых дней). Дать выигрыш это может только если кто-то умудрится побывать в комнате всякий раз после счетчика, но до очередного непосчитанного и каждый раз после очередного непосчитанного, но до счетчика. Только тогда он сможет посчитать всех раньше счетчика, причем не на много раньше.-
Первоначально решал задачу о 10 заключенных, но с задумкой о большем количестве и с другими алгоритмами (удвоение сигнала, корзинки и т.д.), поэтому в алгоритмах в последний день не включал выключатель - так меньше путаницы было. Затем вернулся на 10 заключенных и постарался выжать максимум. Поздравляю Вас, думаю, что для 10 заключенных у Вас получилось выжать все соки.
-
И все-таки это еще не все соки ) Для 10и можно улучшить еще на 0.99 дня.
Для этого в предыдущем алгоритме увеличим минимальную продолжительность голосования до четырех ходов. То есть счетчика определим не раньше четвертого шага. Первые два шага остаются такими же, а на третьем, если до этого был только один (о чем должен сообщать переключатель после второго шага) и пришел опять он же, то он ставит on, во всех остальных случаях ставится off, причем, если на третьем шаге пришел тот, кто до этого не бывал и обнаружил по переключателю, что он уже третий, то он себя после выхода из комнаты посчитанным не считает и в дальнейшем ведет себя так же, как те, что приходят впервые. На четвертом шаге после этого воспринимаем on как то, что посчитан только один, а off, как то, что посчитанных двое, и действуем так же, как раньше на третьем шаге - если пришел уже посчитанный, то он считает себя счетчиком с соответствующим кол-вом посчитанных и оставляет off, если пришел непосчитанный, то считает себя посчитанным и оставляет on, тем самым продолжая голосование. Само голосование длится на 1 день дольше, то есть 7 дней, и в самом лучшем случае счетчик начнет счет с 6и. В итоге такой алгоритм позволяет в среднем выйти примерно за 92.39968 дней (аналитически вычислено). Если добавить предложенных ранее неофициальных счетчиков, то можно еще где-то на 0.0002 - 0.0003 улучшить (по данным статистики, т.к. считать тут сложновато).
-
-
-
Кроме того, не учтен вариант "лампа горит с самого начала". Начальное состояние лампы неизвестно.
Видел задачу и раньше, но сейчас увидел снова - на braingames.ru, и решил ее осилить самостоятельно.
1. Числа на шляпах от 1 до 100, шляп тоже 100, заключенных 100, но чтобы освободить ВСЕХ, угадать надо только ОДНОМУ. Поскольку разрешается посовещаться между собой ДО опроса, заключенные договариваются говорить одно и то же число, например, 14. Кто-нибудь один да угадает, если число 14 присутствует.
2. Заключенный не может видеть номера на своей шляпе, но может видеть другие номера. Поскольку некоторые числа повторяются, логично предположить, что некоторые числа либо отсутствуют, либо написаны на шляпе. Именно отсутствующие числа и называет опрашиваемый. Кто нибудь угадает.
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
0111 - 7
1000 - 8
1001 - 9
Каждый заключённый заходя в комнату в первый раз указывает следующее число, второй и дальше ничего не трогает.
Как на счётчике возникает композиция 1001 - заключённый входя в комнату в первый раз утверждает что он последний кто тут не побывал. Все.
