[Перевод] Занимательные задачки: побег из тюрьмы
В случае упрощённого варианта задачи решение будет почти тривиальным. Простейшая стратегия состоит в том, что заключённые договариваются, какая из коробок будет играть роль «индикатора». Монета на этой коробке будет обозначать коробку, в которой лежит бумажка. Допустим, коробка №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, как и в упрощённом варианте задачи — эта коробка излишняя, и монета на ней не означает ничего.
