В сегодняшней загадке фигурируют двое заключённых. Назовём их Пайпер и Алекс. Вам нужно будет продумать для них стратегию освобождения из тюрьмы.
Загадки, связанные с побегом из тюрьмы, появились относительно недавно, и берут начало в информатике. Тюрьма – идеальная метафора для задач по эффективным коммуникациям в условиях ограниченного обмена данными.
Четыре коробки
Пайпер и Алекс находятся в одной камере. В камеру приходит охранник и сообщает, что у них есть возможность поучаствовать в игре и шанс выиграть свободу. Заключённых по одному будут выводить в соседнюю камеру, где находятся четыре одинаковых пустых коробки с номерами 1, 2, 3 и 4. Игра будет проходить так:
1) Пайпер отведут в другую камеру. Охранник возьмёт у себя из кармана бумажку и на глазах у Пайпер опустит её в одну из коробок, выбранных случайным образом. Потом охранник закроет коробки, подбросит монетку и положит её на коробку №1. Потом подбросит вторую монетку и положит её на коробку №2, и потом ещё два раза повторит эту процедуру с коробками №3 и 4. У каждой из монет будет шанс 50/50 на то, что она ляжет орлом или решкой вверх. Пайпер увидит, как легли монеты.
Четыре коробки с монетками
2) Пайпер обязана будет перевернуть одну монету (любую), поменяв её ориентацию с орла на решку или наоборот. Затем её выведут из камеры и отведут ещё в одну, отдельную.
3) После этого в камеру с коробками приведут Алекс. Она не сможет заглянуть внутрь коробок, но сможет увидеть, какой стороной лежат все монеты. Её попросят открыть коробку. Если в этой коробке окажется бумажка, заключённых освободят. Если нет, их вернут в камеру.
Какая стратегия поведения Пайпер гарантирует освобождение заключённых?
Заключённые могут обсудить стратегию перед тем, как Пайпер уведут в камеру с коробками, и разработать план. Но после того, как её уведут, они с Алекс уже не смогут обменяться никакой информацией – за исключением переворота одной монеты.
Кажется невозможным, чтобы Пайпер смогла дать Алекс понять, в какой коробке лежит бумажка, при помощи единственной монетки. Ведь у неё будет четыре варианта с коробками и 16 вариантов расположения монет.
Как и со многими другими загадками, для решения этой стоит упростить ситуацию, и посмотреть, не появятся ли какие-то идеи. Давайте так и сделаем. Попробуйте решить точно такую же задачку, только когда коробок в камере будет всего две. Охранник приводит Пайпер в камеру, кладёт бумажку в одну из коробок, закрывает их, и кладёт подброшенные монетки сверху. У каждой монетки шанс оказаться орлом или решкой вверх 50/50. Пайпер увидит, как легли монетки.
Упрошенная версия: две коробки с монетками
Если коробок будет всего две, как Пайпер может передать информацию о том, в какой из коробок лежит бумажка, перевернув только одну монету?
Решение
В случае упрощённого варианта задачи решение будет почти тривиальным. Простейшая стратегия состоит в том, что заключённые договариваются, какая из коробок будет играть роль «индикатора». Монета на этой коробке будет обозначать коробку, в которой лежит бумажка. Допустим, коробка №1 будет индикатором, и монета, лежащая на ней решкой вверх, будет означать, что бумажка находится в коробке №1, а орлом вверх — что бумажка находится в коробке №2.
Если Пайпер увидит, что охранник кладёт бумажку в коробку №2, ей нужно просто убедиться, что монета на коробке №1 лежит орлом вверх. Если монета на 1-й коробке лежит решкой вверх, она её переворачивает, а если орлом – она переворачивает монету на 2-й коробке (поскольку монета на 2-й коробке ни о чём не говорит).
Перейдём к варианту с четырьмя коробками. По сути идея тут та же. В данном случае три коробки, допустим, №№1, 2 и 3, будут играть роль индикаторов. А монету на 4-й надо будет перевернуть, только если монеты на первых трёх коробках указывают на нужную коробку.
Рассмотрим наш трёхкоробочный индикатор. Вариантов комбинаций с монетами на трёх коробках может быть восемь:
РРР, ООО, РРО, ООР, РОР, ОРО, ОРР, РОО.
Это может показаться удивительным, но существует способ так обозначить эти комбинации, что при любом варианте с монетами можно указать на одну из четырёх коробок, и при этом перевернуть нужно будет не более одной монеты.
Пусть комбинации монет обозначают, в какой коробке лежит бумажка, таким образом:
№1: РРР или ООО
№2: РРО или ООР
№3: РОР или ОРО
№4: ОРР или РОО
То есть, если на первых трёх коробках монеты лежат как РРР или ООО, значит бумажка в коробке №1 — и так далее.
Допустим, Пайпер хочет указать на коробку №2. Допустим, после всех приготовлений монеты на коробках расположились в последовательности РОР (что в нашем коде обозначает коробку №3). Ей нужно всего лишь перевернуть первую монету, что даст комбинацию ООР, которая будет указывать на коробку №2.
Присмотревшись к комбинациям, вы увидите, что любую комбинацию, обозначающую одну коробку, можно превратить в комбинацию, обозначающую любую другую коробку, перевернув всего одну монету.
Диаграмма демонстрирует это нагляднее. Синим цветом обозначена коробка №1, красным – 2, розовым – 3, зелёным – 4. Связанные между собой линией комбинации превращаются одна в другую переворотом одной монеты. Каждая из комбинаций любого цвета связана с тремя другими, всех остальных цветов.
Получается, что любую последовательность монет на индикаторных коробках можно превратить в последовательность, указывающую на любую коробку, просто перевернув одну монету. А если Пайпер увидит, что нужная комбинация уже и так получилась, она просто перевернёт монету на коробке №4, как и в упрощённом варианте задачи – эта коробка излишняя, и монета на ней не означает ничего.
Если Пайпер увидит, что охранник кладёт бумажку в коробку №2, ей нужно просто убедиться, что монета на коробке №1 лежит орлом вверх. Если монета на 1-й коробке лежит решкой вверх, она её переворачивает, а если орлом – она переворачивает монету на 2-й коробке (поскольку монета на 2-й коробке ни о чём не говорит).
Перейдём к варианту с четырьмя коробками. По сути идея тут та же. В данном случае три коробки, допустим, №№1, 2 и 3, будут играть роль индикаторов. А монету на 4-й надо будет перевернуть, только если монеты на первых трёх коробках указывают на нужную коробку.
Рассмотрим наш трёхкоробочный индикатор. Вариантов комбинаций с монетами на трёх коробках может быть восемь:
РРР, ООО, РРО, ООР, РОР, ОРО, ОРР, РОО.
Это может показаться удивительным, но существует способ так обозначить эти комбинации, что при любом варианте с монетами можно указать на одну из четырёх коробок, и при этом перевернуть нужно будет не более одной монеты.
Пусть комбинации монет обозначают, в какой коробке лежит бумажка, таким образом:
№1: РРР или ООО
№2: РРО или ООР
№3: РОР или ОРО
№4: ОРР или РОО
То есть, если на первых трёх коробках монеты лежат как РРР или ООО, значит бумажка в коробке №1 — и так далее.
Допустим, Пайпер хочет указать на коробку №2. Допустим, после всех приготовлений монеты на коробках расположились в последовательности РОР (что в нашем коде обозначает коробку №3). Ей нужно всего лишь перевернуть первую монету, что даст комбинацию ООР, которая будет указывать на коробку №2.
Присмотревшись к комбинациям, вы увидите, что любую комбинацию, обозначающую одну коробку, можно превратить в комбинацию, обозначающую любую другую коробку, перевернув всего одну монету.
Диаграмма демонстрирует это нагляднее. Синим цветом обозначена коробка №1, красным – 2, розовым – 3, зелёным – 4. Связанные между собой линией комбинации превращаются одна в другую переворотом одной монеты. Каждая из комбинаций любого цвета связана с тремя другими, всех остальных цветов.
Получается, что любую последовательность монет на индикаторных коробках можно превратить в последовательность, указывающую на любую коробку, просто перевернув одну монету. А если Пайпер увидит, что нужная комбинация уже и так получилась, она просто перевернёт монету на коробке №4, как и в упрощённом варианте задачи – эта коробка излишняя, и монета на ней не означает ничего.
