В сегодняшней загадке фигурируют двое заключённых. Назовём их Пайпер и Алекс. Вам нужно будет продумать для них стратегию освобождения из тюрьмы.
Загадки, связанные с побегом из тюрьмы, появились относительно недавно, и берут начало в информатике. Тюрьма – идеальная метафора для задач по эффективным коммуникациям в условиях ограниченного обмена данными.
Четыре коробки
Пайпер и Алекс находятся в одной камере. В камеру приходит охранник и сообщает, что у них есть возможность поучаствовать в игре и шанс выиграть свободу. Заключённых по одному будут выводить в соседнюю камеру, где находятся четыре одинаковых пустых коробки с номерами 1, 2, 3 и 4. Игра будет проходить так:
1) Пайпер отведут в другую камеру. Охранник возьмёт у себя из кармана бумажку и на глазах у Пайпер опустит её в одну из коробок, выбранных случайным образом. Потом охранник закроет коробки, подбросит монетку и положит её на коробку №1. Потом подбросит вторую монетку и положит её на коробку №2, и потом ещё два раза повторит эту процедуру с коробками №3 и 4. У каждой из монет будет шанс 50/50 на то, что она ляжет орлом или решкой вверх. Пайпер увидит, как легли монеты.
Четыре коробки с монетками
2) Пайпер обязана будет перевернуть одну монету (любую), поменяв её ориентацию с орла на решку или наоборот. Затем её выведут из камеры и отведут ещё в одну, отдельную.
3) После этого в камеру с коробками приведут Алекс. Она не сможет заглянуть внутрь коробок, но сможет увидеть, какой стороной лежат все монеты. Её попросят открыть коробку. Если в этой коробке окажется бумажка, заключённых освободят. Если нет, их вернут в камеру.
Какая стратегия поведения Пайпер гарантирует освобождение заключённых?
Заключённые могут обсудить стратегию перед тем, как Пайпер уведут в камеру с коробками, и разработать план. Но после того, как её уведут, они с Алекс уже не смогут обменяться никакой информацией – за исключением переворота одной монеты.
Кажется невозможным, чтобы Пайпер смогла дать Алекс понять, в какой коробке лежит бумажка, при помощи единственной монетки. Ведь у неё будет четыре варианта с коробками и 16 вариантов расположения монет.
Как и со многими другими загадками, для решения этой стоит упростить ситуацию, и посмотреть, не появятся ли какие-то идеи. Давайте так и сделаем. Попробуйте решить точно такую же задачку, только когда коробок в камере будет всего две. Охранник приводит Пайпер в камеру, кладёт бумажку в одну из коробок, закрывает их, и кладёт подброшенные монетки сверху. У каждой монетки шанс оказаться орлом или решкой вверх 50/50. Пайпер увидит, как легли монетки.
Упрошенная версия: две коробки с монетками
Если коробок будет всего две, как Пайпер может передать информацию о том, в какой из коробок лежит бумажка, перевернув только одну монету?
Если Пайпер увидит, что охранник кладёт бумажку в коробку №2, ей нужно просто убедиться, что монета на коробке №1 лежит орлом вверх. Если монета на 1-й коробке лежит решкой вверх, она её переворачивает, а если орлом – она переворачивает монету на 2-й коробке (поскольку монета на 2-й коробке ни о чём не говорит).
Перейдём к варианту с четырьмя коробками. По сути идея тут та же. В данном случае три коробки, допустим, №№1, 2 и 3, будут играть роль индикаторов. А монету на 4-й надо будет перевернуть, только если монеты на первых трёх коробках указывают на нужную коробку.
Рассмотрим наш трёхкоробочный индикатор. Вариантов комбинаций с монетами на трёх коробках может быть восемь:
РРР, ООО, РРО, ООР, РОР, ОРО, ОРР, РОО.
Это может показаться удивительным, но существует способ так обозначить эти комбинации, что при любом варианте с монетами можно указать на одну из четырёх коробок, и при этом перевернуть нужно будет не более одной монеты.
Пусть комбинации монет обозначают, в какой коробке лежит бумажка, таким образом:
№1: РРР или ООО
№2: РРО или ООР
№3: РОР или ОРО
№4: ОРР или РОО
То есть, если на первых трёх коробках монеты лежат как РРР или ООО, значит бумажка в коробке №1 — и так далее.
Допустим, Пайпер хочет указать на коробку №2. Допустим, после всех приготовлений монеты на коробках расположились в последовательности РОР (что в нашем коде обозначает коробку №3). Ей нужно всего лишь перевернуть первую монету, что даст комбинацию ООР, которая будет указывать на коробку №2.
Присмотревшись к комбинациям, вы увидите, что любую комбинацию, обозначающую одну коробку, можно превратить в комбинацию, обозначающую любую другую коробку, перевернув всего одну монету.
Диаграмма демонстрирует это нагляднее. Синим цветом обозначена коробка №1, красным – 2, розовым – 3, зелёным – 4. Связанные между собой линией комбинации превращаются одна в другую переворотом одной монеты. Каждая из комбинаций любого цвета связана с тремя другими, всех остальных цветов.
Получается, что любую последовательность монет на индикаторных коробках можно превратить в последовательность, указывающую на любую коробку, просто перевернув одну монету. А если Пайпер увидит, что нужная комбинация уже и так получилась, она просто перевернёт монету на коробке №4, как и в упрощённом варианте задачи – эта коробка излишняя, и монета на ней не означает ничего.
Комментарии (18)
agat000
00.00.0000 00:00+1Если коробок всего две - то легко. Определяется контрольная коробка, показание монеты в ней будет указывать номер правильной коробки (орел - первая, решка - вторая).
Если коробок 4 - то... думать надо
aamonster
00.00.0000 00:00+1Тут можно, чуть подумав, сделать решение исходя из битовых операций, а не с придумывания 8 комбинаций.
Пусть положение монет – это 4 бита B0, B1, B2, B3
Для начала чуть упростим задачу: пусть B0^B1^B2^B3 == 0. Это довольно просто: если это не так – пусть Пайпер перед выбором мысленно перевернёт 4-ю монетку.
Соответственно (т.к. Пайпер переворачивала ровно одну монетку) для Алекса будет b0^b1^b2^b3 == 1, а если это не так – то тоже нужно мысленно перевернуть 4-ю монетку.
Теперь всё резко упростилось. Разбиваем монетки на пары. Раз b0^b1^b2^b3 == 1 – значит, b0^b1 != b2^b3, одно из значений будет 0, а другое 1. И какое именно – выбирает Пайпер, перевернув либо одну из монеток (B0, B1), либо одну из монеток (B2, B3).
То же для пар (B0, B2) и (B1, B3).
Итого Алексу остаётся:
1. Посчитать решки, если их нечётное число – мысленно перевернуть четвёртую монетку.
2. Посмотреть, какое из чисел b0^b1 и b2^b3 равно 1, это даст старший бит номера.
3. Посмотреть, какое из чисел b0^b2 и b1^b3 равно 1, это даст младший бит номера.
XenRE
00.00.0000 00:00+4Какое-то слишком мудрёное решение в статье, я придумал проще:
Пронумеруем ящики 0..3. Присвоим монете над каждым ящиком значение Cn = 0 если решка и n если орёл. Пусть Bn = C1 xor C2 xor C3 (а C0 всегда 0 и можно не считать). Тогда Пайпер нужно вычислить Bn для исходного положения монет, по-xor-ить его с номером ящика с бумажкой и перевернуть монету с получившимся номером, а Алекс нужно вычислить Bn и открыть соответствующий ящик.
Доказательство также простейшее: если C = A xor B то B = A xor C, таким образом достаточно переворота одной монеты чтобы скорректировать любое исходное значение Bn до любого требуемого.
Tyusha
00.00.0000 00:00А если монеты уже лежат в нужном положении? Ведь по условию Пайпер обязана перевернуть одну монету в любом случае! Вот тут-то вам и ломается.
AlexanderS
00.00.0000 00:00+5Вариант решения с комбинациями непонятен потому что не объяснена логика выбора пар, которая от этого кажется сложной и неочевидной. Поэтому и кажется что численным способом проще. Ну как проще — кто знает что такое XOR действительно может быть проще)
У нас есть 4 варианта коробок и четырёхбитное слово для кодировки номера коробки. Четвёртый бит выделим в незначащий и будем работать с оставшимися тремя битами. Возьмём стартовый вариант 000. Тогда код коробки можно закодировать перевернув один любой бит, который станет значащим следующим образом:
000 = №1
001 = №2
010 = №3
100 = №4
Если у нас стартовый вариант 111 (побитно инверсный к 000), то значащий бит так же инвертируется:
111 = №1
110 = №2
101 = №3
011 = №4
Таким образом, получается два формата представления номера: условно прямой и условно инверсный и определяется по нахождению одиночного 1 или 0 в трёхбитном слове. Если выпали номера 000/111, то в случае нахождения бумажки в первой коробке меняется незначащий четвёртый бит (потому что мы обязаны перевернуть хоть что-то), в случае любой другой коробки номер можно указать перевернув всего один бит. Если же выпали номера отличные от 000/111, то фокус заключается в том, что переворачивая всего один бит мы одновременно меняем формат представления номера и устанавливаем этот самый номер. Для выпавшей комбинации 010 и нахождения бумажки в коробке 2 достаточно повернуть первый бит, чтобы оставшийся значащий бит указывал на номер коробки: 110. Поэтому Алекс зайдя в комнату и отбросив «мусорный» бит на коробке 4 по количеству 1 или 0 сразу определяет в каком формате закодирован номер и декодирует его.
Но так можно объяснить только если у нас слово трёхбитное, как в условии. Для четырёхбитного слова (5 коробок) это уже работать не будет.Tyusha
00.00.0000 00:00Ровно то, что вы написали и есть в решении в статье.
AlexanderS
00.00.0000 00:00+1Я просто расширил описание, повторив изложенное другими (своими) словами не прибегая к фразам типа «Пусть комбинации монет обозначают, в какой коробке лежит бумажка, таким образом»…
plFlok
00.00.0000 00:00+1Мне больше нравится вариация этой задачи про шахматную доску.
Из-за двумерности пространства коды коррекции там выглядят более мозговзрывательно, хотя по сути то же самое представляют
bunta
00.00.0000 00:00+1Номер ящика кодируется двумя последними монетами - 00 01 10 11 такую комбинацию всегда можно получить одним поворотом как бы не выпали + инверсия по первой монете. Кода две последние совпали и инверсия не требуется, переворачиваем вторую, чтобы соблюсти условие.
bau_ke
00.00.0000 00:00Если выпало чётное количество орлов, то одним переворотом можно сделать так, чтобы монета на нужной коробке лежала отличной от всех стороной. Если нечётное, то для каждой коробки придумать комбинацию 0000,0Х0Х,00ХХ,0ХХ0. Где Х и 0 могут быть как орёл и решка, так и решка и орёл
Menelaj
00.00.0000 00:00Для случая, когда изначально чётное число орлов (и решек), можно предложить простое "практическое" решение (как писали выше, в случае нечётного изначального числа орлов Пайпер и Алекс могут мысленно дополнительно перевернуть какую-то одну определённую монету).
В этом решении, когда Алекс заходит в камеру с коробками, она видит, что ровно на одной из коробок монета лежит не той стороной, что на других. Именно в этой коробке и лежит бумажка.
Пайпер же перед выбором монеты просто делает мысленный перебор: "Что будет, если я переверну первую монету", "Что будет, если я переверну вторую монету" и т.д. Из четырёх возможных исходов она выбирает тот, в котором на коробке с бумажкой окажется отличающаяся от других монета (ровно один из возможных переворотов даст нужную комбинацию).
Доказательство, что это работает: если изначально орлов (как и решек) чётное количество, то после любого переворота станет нечётное количество орлов (как и решек). А в случае четырёх монет это может означать только одну монету одного вида и три монеты другого вида. Таким образом, у Пайпер имеется четыре возможных итоговых варианта вида "одна монета отличается от других". Осталось убедиться, что "отличающаяся" монета во всех четырёх вариантах разная - а это действительно так, потому что нельзя из одной и той же комбинации орлов (О) и решек (Р) получить одним переворотом, например, ОРОО, а другим РОРР - у них слишком много отличающихся позиций (ну и тем более нельзя двумя разными переворотами получить две одинаковые комбинации).
DivoTech
00.00.0000 00:00Просто запоминаем 2 комбинации для каждой коробки:
1, 0, 0, 0 и 1, 1, 0, 0
0, 1, 0, 0 и 0, 1, 1, 0
0, 0, 1, 0 и 0, 0, 0, 0
0, 0, 0, 1 и 0, 1, 0, 1
Где 1 — либо орёл (тогда 0 — решка), либо решка (тогда 1 — орёл)
И выкладываем одну из этих комбинаций монетами (их все можно получить переложив одну монету)
Alexandroppolus
Насколько я знаю, это обобщается для любого количества монет N = 2^k
domix32
И задача сводится к бинарным кодам коррекции.