Загадка про заключенных и выключатель
Обновлено: 16.05.2024
УЗНИКИ И ЛАМПОЧКА.
Есть сто узников, сидят они в отдельных камерах и не могут общаться между собой. Однажды их всех собрал тюремщик и предложил испытание. Есть отдельная комната в которой расположена лампочка с выключателем. Узников будут заводить в комнату в случайном порядке по одному. Они могут в этой комнате либо включить лампочку либоу выключить, либо не трогать. Узников выпустят в том случае, если один из них скажет точно, что до него в комнате побывали все остальные узники. Задача узников разработать стратегию поведения
Ответ дам в личку.
Лучший ответЯ не задавал, честное слово, в тюрьме пока не сидел (хотя, как говорится - от сумы да от тюрьмы. )
А решение, вроде, тоже нашел.
Узники выбирают одного определённого человека (будем называть его “счётчиком”), который будет считать узников по такой системе: если, приходя в комнату, он обнаруживает, что свет включён, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из оставшихся узников действует по такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, “счётчик” говорит, что все узники уже побывали в комнате.
Действительно, каждый узник, кроме “счётчика”, включит свет в комнате не более одного раза. Когда “счётчик” насчитает 99, он может быть уверен, что все остальные узники уже побывали в комнате хотя бы раз, кроме того он сам уже побывал в комнате. Получается, что к этому моменту все узники заведомо побывали в комнате хоть раз.
Решение
1. Самый простой, но и самый долгий вариант — действовать так, как было сказано в подсказке. Чтобы просигнализировать последнему, каждый из заключенных, которого завели в комнату НЕ В СВОЙ день, должен поставить переключатель в положение ON. Если же 10-й заключенный действительно оказался в комнате на 10-й день декады и видит переключатель в положении OFF, он немедленно говорит начальнику тюрьмы, что в комнате побывали все заключенные. Если в 10-й день в комнате оказался кто-то другой или же 10-й видит переключатель в положении ON, то всё начинается заново.
Это решение, несмотря на всю свою простоту, плохо в главном — бедным узникам придется слишком долго ждать. Действительно, из всех возможных 10 10 вариантов посещения ими комнаты в течение декады их устраивает только один — таким образом, вероятность p их выхода на волю в течение одной декады равна 1/10 10 . Сравнительно несложными вычислениями можно доказать, что среднее время, которое потребуется им на освобождение, равно 1/p = 10 10 декад, или 10 11 дней, или более 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 заключенных, возможно, и нет, а вот для большего количества — есть. Автор этой стратегии Б. Фельгенауэр назвал ее «пирамидальной».
Как же происходит отдача и прием сигналов в пирамидальной схеме?
А вот как: если во время k-ночи заключенный пришел в комнату и видит переключатель в положении ON, то он принимает k-сигнал и ставит переключатель в OFF. Если к этому моменту у него уже был один k-сигнал, то теперь у него есть два таких сигнала, или один 2k-сигнал (который он попытается либо отдать, либо снова удвоить в период 2k-ночей). Если же он пришел в комнату со своим k-сигналом и видит OFF, то он ставит ON и считает k-сигнал отданным.
Вот, в целом, и всё. Остальное уже является занудными техническими подробностями (какова должна быть продолжительность ночей определенного типа для того, чтобы передача всех нужных сигналов состоялась с достаточной вероятностью, и при этом не было слишком большой задержки перед наступлением следующего типа ночей).
Эта задача имеет самое прямое отношение к теории информации — она демонстрирует, что даже самый узкий (всего 1 бит — ON/OFF) канал позволяет передать достаточно много информации.
Кто именно является автором «тюремной» формулировки, мне неизвестно, но именно эта забавная формулировка буквально покорила мир. Кроме того, несмотря на относительную молодость задачи, она уже успела обрасти кучей самых неожиданных вариаций и усложнений. Например:
Два переключателя. В комнате, куда приводят заключенных, не один, а целых два переключателя (следовательно, выйти на свободу можно быстрее. Вопрос: насколько?)
Две комнаты. Заключенных водят не в одну, а в две разных комнаты, выбирая их также случайным образом. В каждой комнате — свой переключатель.
Разделение передатчика и приемника. Каждую полночь начальник тюрьмы ставит переключатель в положение OFF. В час ночи он приводит туда первого заключенного, потом уводит, а в два часа ночи приводит туда же второго. Таким образом, первый из них должен «сработать» передатчиком информации, а второй — приемником.
Злобный начальник. Начальник тюрьмы знает стратегию узников и каждый день выбирает для посещения комнаты такого заключенного, чтобы максимально затруднить узникам их задачу.
Следующая загадка
Первое, о чем должны договориться ЗК - это кто первый выйдет на свободу. Назовем его N. Алгоритм действий ЗК такой: тот, кто входит в камеру впервые, переводит переключатель в положение ВКЛ (если переключатель уже ВКЛ, то ЗК его не трогает). Если в камеру заходит N, то он переводит рубильник в положение ВЫКЛ. Таким образом, когда N выключает рубильник 9 раз, то, значит, в камере побывали все ЗК. При этом важно: каждый заключенный (не N) должен переводить рубильник в положение ВКЛ ровно один раз.
Нравится Показать список оценивших
Пример.
Первым в камеру вводят заключенного N. Он делает ВЫКЛ
Следующий, зашедший впервые, делает ВКЛ.
Все остальные вошедшие ничего не делают (переключатель остается ВКЛ).
Когда заходит N, он делает ВЫКЛ в первый раз.
Следующий ЗК, если он еще не трогал рубильник, делает ВКЛ, следующие вошедшие его не трогают. Потом N ВЫКЛючает второй раз.
и т.д.
после девятого выключения рубильника N выходит на свободу.
Для оставшихся ЗК алгоритм тот же
Нравится Показать список оценивших
Нравится Показать список оценивших
Игорь Карнаков ответил Марине
Марина, есть две нестыковки:
1. Если N, зайдя в подвал первый раз, видит "включено", то он не знает, первым его завели в камеру или нет.
2. Если в промежутке между двумя заходами N нескольких заключенных заводят по первому разу, то только первый из них дернет выключать, и остальных N не сосчитает.
Нравится Показать список оценивших
Марина Явтушенко ответила Игорю
Нравится Показать список оценивших
Игорь Карнаков ответил Марине
Марина, по п. 2 согласен. По п. 1: если N видит выключенный выключенный переключатель при 9-м и 10-м заходах, то он не знает 9 раз его включали или только 8. То есть одного заключенного могли не завести ни разу, а могли завести уже всех.
Нравится Показать список оценивших
Марина Явтушенко ответила Игорю
Игорь, да. Поэтому N будет ожидать 9-го переключения (при этом если не считать самого первого). Он может зайти в камеру еще не один десяток раз и увидеть ВЫКЛ, прежде чем решит, что ТО ПЕРВОЕ ВЫКЛючение тоже нужно учесть. При этом предполагается, что тюремщики приводят ВСЕХ заключенных. Все равно получается игра в рулетку, если ЗК не знают одно из двух: 1) кого поведут первым и 2) в каком изначальном положении был переключатель.
Нравится Показать список оценивших
Игорь Карнаков ответил Марине
Марина, ну, то есть с вероятностью 1/2. Если тюремщики не стремятся создать у N ложное впечатление, что провели всех заключенных.
Нравится Показать список оценивших
Марина Явтушенко ответила Игорю
Игорь, по этому решению так. Надо подумать еще.
Нравится Показать список оценивших
Блин можно вообще сделать так ,чтоб каждый подсчитал ,как он не менее одного раза переключил переключатель или просто нет вот и все и сообщить об этом всем.
Нравится Показать список оценивших
Марина Явтушенко ответила Альберту
Нравится Показать список оценивших
Альберт Ямалдинов ответил Марине
Марина, ну по началу я так и думал)
Нравится Показать список оценивших
предыдущие два моих варианта были до конца недоработанными ,сейчас же представлю иной ,другой вариант _во первых подсчет должен вести только один из них, далее он же может нажать один из всех допустим с OFF на ON и только.Все же кроме него должны нажимать с ON на OFF и только один раз ,за все вновь приводы ,т.е. если их приводят во второй и более раз ,то они вообще не должны касаться переключателя..подсчет он должен вести своих серий с OFF на ON.. т.к. они возможны ,когда их переводят в позицию OFF из серий с ON на OFF,т.е. другие.Так же с этим вариантом не имеет значение кто вошел первым он или другие по отношению к позициям ON или OFF.
Нравится Показать список оценивших
Нравится Показать список оценивших
можно даже так поделить поровну,т.е. пятеро кто бы переводил с позиции OFF-ON и пятеро наоборот и каждый только один раз за все приводы ,и каждый подсчитывал противоположные серии переключений в кол-ве пяти?
Нравится Показать список оценивших
Марина Явтушенко ответила Альберту
Альберт, задачка явно не дает Вам покоя. Проблема в том, что тот,кого привели первым - не знает, первый он или нет. Поэтому если ЗК видит ON, он не знает, N его включил или так было. Если после этого зайдет N и увидит OFF он также не знает - так было или уже побывал один заключенный и выключил.
Нравится Показать список оценивших
Марина Явтушенко ответила Альберту
Подсказка
Казалось бы, как заключенный, которого привели в комнату, может воспользоваться тем, что видит переключатель в положении ON? И если он переключит его на OFF — как следующему заключенному воспользоваться этим?
Тем не менее стратегия, гарантированно приводящая узников к спасению, существует. Например, узники могут разбить дни на декады (10-дневные промежутки) и договориться, что дожидаются такого вот события: первого из них заведут в комнату в первый день декады, второго — во второй день и т. д., десятого — в последний день. Поскольку вероятность такого события отлична от нуля, то рано или поздно оно произойдет! Догадайтесь, как они могут действовать, чтобы 10-й смог понять,что такое событие в данной декаде на самом деле произошло.
Следующая загадка
Чужой компьютер
Просмотр темы 40
Help загадка которую даже с ответом я не могу понять.
В тюрьме есть два электрических стула. Один из них не подключен к сети. Заключенный имеет право выбора. Но о том, который подключен, знает только палач. Палачу можно задать один любой простой вопрос. Известно, что палач в один день врет, в другой говорит правду (по очереди). Какой вопрос задать тому, кто хочет жить?
Нравится Показать список оценивших
Что ты мне ответишь завтра, если я спрошу тебя подключен ли 1-ый стул к сети?
Следующая загадка
В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:
«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».
После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.
Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?
Читайте также: