Загадка про 10 заключенных

Обновлено: 24.12.2024

Деспотичный диктатор держит в заключении на острове 100 человек. Сбежать оттуда невозможно, но есть одно правило. Ночью любой узник может попросить стражников об освобождении. Если у пленника голубые глаза, его отпустят. Если нет — скормят акулам.

На самом деле все 100 заключённых голубоглазые. Но они живут на острове с рождения, и диктатор постарался, чтобы никто не узнал цвет своих глаз. На острове нет зеркал, узники нигде не могут увидеть своё отражение. Все ёмкости для воды непрозрачные.

Островитяне логичны во всех своих действиях, поэтому никто из них не рискнёт просить об освобождении, если не будет абсолютно уверен в успехе.

Однажды диктатор влюбляется в девушку, которая всегда говорит правду. Он поддаётся на уговоры избранницы, разрешает ей посетить остров и поговорить с пленными. Но ставит такие условия: она может сделать только одно заявление и не должна сообщать узникам новую информацию.

Девушка знает о ситуации на острове и хочет помочь заключённым освободиться, но опасается навлечь на себя гнев диктатора. После долгих раздумий она сообщает толпе узников, которых вывели на перекличку: «По крайней мере у одного из вас голубые глаза».

Кадр: @TED‑Ed / YouTube

После обращения возлюбленная диктатора покидает остров. Тот не сердится на неё. Ему кажется, что информация, которую она дала пленным, не опасна и сделанное заявление ничего не изменит. Жизнь на острове будто бы идёт своим чередом.

Однако через 100 дней после визита девушки остров оказывается пуст: все узники потребовали освобождения и навсегда его покинули. Порассуждайте, как же так вышло. Напоминаем: у всех жителей острова превосходная логика.

Число островитян в данном случае не имеет значения. Чтобы упростить задачу, оставим только двух пленников — условных Андрея и Машу. Каждый из них видит узника с голубыми глазами, но знает, что этот голубоглазый может быть единственным.

В первую ночь они оба выжидают. Наутро они видят, что их товарищ по несчастью всё ещё здесь, и это даёт им подсказку. Андрей догадывается, что если его глаза не голубые, то Маша освободилась бы в первую ночь, поняв, что она единственный голубоглазый узник. Точно так же и Маша размышляет про Андрея. Они оба понимают следующее: «Если другой ждёт, мои глаза могут быть только голубыми». На следующее утро они оба покидают остров.

Теперь рассмотрим ситуацию, когда узников трое: Андрей, Маша и Борис. Каждый из них видит двух пленников с голубыми глазами, но не уверен, сколько голубоглазых видят остальные — двух или только одного. В первую ночь узники выжидают, но утро ясности пока что не приносит.

Кадр: @TED‑Ed / YouTube

Борис рассуждает так: «Если мои глаза не голубые, Андрей и Маша наблюдают только друг за другом. Значит, следующей ночью они вместе покинут остров». Но на третье утро Борис видит, что они никуда не делись, и делает вывод, что пленники наблюдают за ним. Андрей и Маша мыслят точно так же, поэтому на третью ночь они все покидают остров.

Это называется индуктивной логикой. Можно увеличивать количество пленных, а рассуждения останутся верными и не будут зависеть от количества островитян. То есть если узников было бы четверо, то они покинули бы остров на четвёртую ночь, пятеро — на пятую, сто — на сотую.

Ключ к этой загадке — концепция общего знания. Это знание, которым обладает каждый член группы, и каждый член группы знает, что все остальные члены группы знают, и все знают, что все знают, что все знают, и так до бесконечности.

Таким образом, становится понятно, что новую информацию островитянам дало не само заявление девушки, а то, что все они услышали его одновременно. Теперь все узники не только знают, что по крайней мере один из них имеет голубые глаза, но и то, что каждый следит за всеми голубоглазыми, и что они все знают это, и так далее.

Единственное, чего каждый отдельно взятый узник не знает, — это то, относится ли он к голубоглазым, за которым наблюдают остальные. Он узнает это только тогда, когда пройдёт столько ночей, сколько заключённых на острове. Конечно, девушка могла избавить узников от 98 ночей на острове, сказав, что минимум 99 из них имеют голубые глаза. Но с непредсказуемым диктатором шутки плохи, и лучше так не рисковать.

Следующая загадка

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:

«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».

После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.

Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?

Решение

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, и так далее. Итого дней — совсем не так много, как в предыдущих решениях.

Следующая загадка

Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?

100% выйти, или с шансом, скажем, 99,99%?

И доступны ли показания выключателя, всем заключённым всегда, вроде какой-нибудь лампочки?

Panzerschrek[CN]
> 100% выйти
Да.
Panzerschrek[CN]
> И доступны ли показания выключателя, всем заключённым всегда, вроде
> какой-нибудь лампочки?
Нет, доступны только тогда, когда в камеру самого приведут.

Т.е. каждого могут туда завести к выключателю хоть по 10 раз, важно лишь понять, что хоть раз все гарантированно там побывали?

+ Показать

Суть такова: выбирается смотрящий, который бы контролировал состояние выключателя.
Когда заключённого вводят в подвал, он выставляет выключатель в 1, если он в 0, причём выставляет он только 1 раз, из всех ему предоставившихся. Рано или поздно в подвал попадает смотрящий. Если выключатель выставлен в 1, значит по меньшей мере 1 новый заключённый там побывал с предыдущего раза. Смотрящий сбрасывает выключатель в 0 запоминает сколько раз он это делал ( сколько заключённых там побывали ). В последний раз, когда попадает смотрящий, он поимает что уже всё.

Для данного метода, единственное допущение - всем известное начальное состояние рубильника. Хотя можно договорится, например, что первый поситивший подвал сбрасывает выключатель в 0.

Mikle
>100%
>Да.
В принципе, для тупых заключённых с длительным сроком заключения можно подождать скажем год, и с большой долей вероятности ( лень считать с какой ), они все там побывают.

Заключенные должны совершать повторяющиеся попытки каждые десять дней. Тот, кто в комнате в первый раз, включает рубильник. Иначе выключает. Если кто-то видит выключенный рубильник, он его не трогает и ждёт нового "сезона". Рано или поздно наступит ситуация, когда по чистой случайности в течение 10 дней каждый зэк будет вызван ровно по разу. Тогда последний из них, увидев включенный рубильник, скажет, что комнату посетили все.

Только я сомневаюсь, что им хватит жизни, чтобы выйти таким образом.

Panzerschrek[CN]
Твой вариант должен быть побыстрее. )

Panzerschrek[CN]
такого допущения нам не давали. начальное значение неизвестно.
значит со смотрящим не прокатывает.

но зато минимум 9 побывавших человек твой способ гарантирует.
но не 10. и никак гарантировать не получается.

Panzerschrek[CN]
> Суть такова: выбирается смотрящий, который бы контролировал состояние
> выключателя.

Это противоречит условиям задачи, они сидят по одному.

Mikle
> Могут ли заключенные гарантированно выйти на свободу, и если да, то как им
> этого добиться?
Отсидеть свои сроки до конца

Получается 9 раз, последний не участвует.
Каждый переключает только 1 раз.
Каждый делает IsFlag = !IsFlag.
Допустим в начале флаг FALSE.

1. On.
2. Off.
3. On.
4. Off.
5. On.
6. Off.
7. On.
8. Off.
9. On.

Тут только, не понятно ему будет 2-й он или 10-й.

Миха Маус
> такого допущения нам не давали. начальное значение неизвестно.
> значит со смотрящим не прокатывает.
что мешает договориться о том, что тот, кого вызывают в первый день, и есть смотрящий?
зэки и дни считать не могут?

Миха Маус
> такого допущения нам не давали. начальное значение неизвестно.
> значит со смотрящим не прокатывает.
В принцепе, не нужно. В первый день, тот кто войдёт, пусть считает что выключатель в 0.
Хаус
> Это противоречит условиям задачи, они сидят по одному.
В начале же дают договорится.
мул
Каждый заключённый может определить в конце сезона, побывал ли тут новенький. Но как тогда посчитать централизованно количество побывавших, если информация об инкременте поступает к разным заключённым.

Следующая загадка

Пришельцы поймали 10 землян. Они уверены, что пленники очень вкусные, но беда в том, что поедать разумных существ им запрещено. К сожалению, инопланетяне не очень‑то верят в интеллектуальные способности невольников, поэтому придумали для них испытание.

Воспользовавшись переводчиком, пришельцы сообщили землянам следующее: «Вас всех построят в один ряд лицом вперёд по росту. Вы сможете видеть всех, кто стоит перед вами. Оглядываться назад или выходить из строя нельзя.

Каждому из вас наденут на голову колпак чёрного или белого цвета в произвольном порядке. Вам не скажут, сколько колпаков какого цвета. Когда подадут сигнал, вы должны будете угадать цвет вашего колпака. Начнут с замыкающего строй и продолжат до впереди стоящего.

Нельзя произносить других слов, кроме „чёрный“ и „белый“, а также подавать какие‑либо подсказки интонацией, иначе вас тут же съедят. Если хотя бы девять из вас правильно отгадают цвет колпака, всех пощадят. У вас пять минут на то, чтобы обсудить план, а затем вас построят, наденут колпаки, и мы начнём».

Как действовать землянам, чтобы спастись?

Замыкающий строй видит все колпаки, но может сказать только «чёрный» или «белый», одновременно сообщив всем скрытую информацию. Пленникам неизвестно общее число чёрных и белых колпаков, возможных вариантов больше двух. Зато они ограничены всего двумя версиями, когда речь идёт о понятии чётности: число может быть либо чётным, либо нечётным.

Ключ к решению задачи таков: пленники договариваются, что первый отвечающий скажет, к примеру, «чёрный», если будет видеть нечётное число чёрных колпаков впереди, и «белый», если увидит чётное число чёрных колпаков.

Скриншот: TED‑Ed / YouTube

Разберём пример с картинки выше. Самый высокий пленник № 1 видит впереди три чёрных колпака. Он говорит вслух «чёрный». Это даёт всем остальным информацию о том, что впереди нечётное число чёрных колпаков. Первый пленник ошибся с цветом своего колпака, но это не страшно: один раз разрешается ответить неверно.

Пленница № 2 видит перед собой нечётное число чёрных колпаков. Она понимает, что на ней белый, и отвечает верно. Пленник № 3 видит чётное число чёрных колпаков и догадывается, что на нём чёрный колпак, который видели два первых пленника.

Пленница № 4 слышит ответ и понимает, что ей стоит искать чётное число чёрных колпаков, ведь за спиной был чёрный, но она видит впереди только один и делает вывод, что и её колпак чёрного цвета. Пленники № 5–9 ищут нечётное количество чёрных колпаков, что они как раз и видят, при этом понимая, что на них колпаки белые. Очередь доходит до десятого пленного. Если пленник № 9 видел нечётное число чёрных колпаков, это означает лишь одно — на пленнике № 10 чёрный колпак.

Вот как этот алгоритм будет работать для любого набора колпаков. Для первого участника вероятность неправильного ответа — 50%, но информация о чётности‑нечётности, которую он сообщит, позволит остальным пленникам угадать цвет их колпака.

Каждый отвечающий начнёт оценивать число чётных и нечётных колпаков впереди. Если подсчитанное в уме число не совпадёт с тем, что он видит, то его колпак того же цвета. Каждый раз в таком случае следующий отвечающий учитывает, что чётность‑нечётность оставшихся колпаков теперь изменилась.

Послесловие

А не существует ли еще более быстрой стратегии действий?

Для 10 заключенных, возможно, и нет, а вот для большего количества — есть. Автор этой стратегии Б. Фельгенауэр назвал ее «пирамидальной».

Как же происходит отдача и прием сигналов в пирамидальной схеме?

А вот как: если во время k-ночи заключенный пришел в комнату и видит переключатель в положении ON, то он принимает k-сигнал и ставит переключатель в OFF. Если к этому моменту у него уже был один k-сигнал, то теперь у него есть два таких сигнала, или один 2k-сигнал (который он попытается либо отдать, либо снова удвоить в период 2k-ночей). Если же он пришел в комнату со своим k-сигналом и видит OFF, то он ставит ON и считает k-сигнал отданным.

Вот, в целом, и всё. Остальное уже является занудными техническими подробностями (какова должна быть продолжительность ночей определенного типа для того, чтобы передача всех нужных сигналов состоялась с достаточной вероятностью, и при этом не было слишком большой задержки перед наступлением следующего типа ночей).

Эта задача имеет самое прямое отношение к теории информации — она демонстрирует, что даже самый узкий (всего 1 бит — ON/OFF) канал позволяет передать достаточно много информации.

Кто именно является автором «тюремной» формулировки, мне неизвестно, но именно эта забавная формулировка буквально покорила мир. Кроме того, несмотря на относительную молодость задачи, она уже успела обрасти кучей самых неожиданных вариаций и усложнений. Например:

Два переключателя. В комнате, куда приводят заключенных, не один, а целых два переключателя (следовательно, выйти на свободу можно быстрее. Вопрос: насколько?)

Две комнаты. Заключенных водят не в одну, а в две разных комнаты, выбирая их также случайным образом. В каждой комнате — свой переключатель.

Разделение передатчика и приемника. Каждую полночь начальник тюрьмы ставит переключатель в положение OFF. В час ночи он приводит туда первого заключенного, потом уводит, а в два часа ночи приводит туда же второго. Таким образом, первый из них должен «сработать» передатчиком информации, а второй — приемником.

Злобный начальник. Начальник тюрьмы знает стратегию узников и каждый день выбирает для посещения комнаты такого заключенного, чтобы максимально затруднить узникам их задачу.

Подсказка

Казалось бы, как заключенный, которого привели в комнату, может воспользоваться тем, что видит переключатель в положении ON? И если он переключит его на OFF — как следующему заключенному воспользоваться этим?

Тем не менее стратегия, гарантированно приводящая узников к спасению, существует. Например, узники могут разбить дни на декады (10-дневные промежутки) и договориться, что дожидаются такого вот события: первого из них заведут в комнату в первый день декады, второго — во второй день и т. д., десятого — в последний день. Поскольку вероятность такого события отлична от нуля, то рано или поздно оно произойдет! Догадайтесь, как они могут действовать, чтобы 10-й смог понять,что такое событие в данной декаде на самом деле произошло.

Читайте также: