Comments 18
Насколько я знаю, это обобщается для любого количества монет N = 2^k
Код коррекции завернутый в отвлекающую историю.
Если коробок всего две - то легко. Определяется контрольная коробка, показание монеты в ней будет указывать номер правильной коробки (орел - первая, решка - вторая).
Если коробок 4 - то... думать надо
Тут можно, чуть подумав, сделать решение исходя из битовых операций, а не с придумывания 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, это даст младший бит номера.
Пронумеруем ящики 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 до любого требуемого.
У нас есть 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 коробок) это уже работать не будет.
Мне больше нравится вариация этой задачи про шахматную доску.
Из-за двумерности пространства коды коррекции там выглядят более мозговзрывательно, хотя по сути то же самое представляют
Ребята, просто договоритесь в какой угол надо положить перевёрнутую монетку. Про то, что ее нельзя перемещать, в задаче ни слова.
Номер ящика кодируется двумя последними монетами - 00 01 10 11 такую комбинацию всегда можно получить одним поворотом как бы не выпали + инверсия по первой монете. Кода две последние совпали и инверсия не требуется, переворачиваем вторую, чтобы соблюсти условие.
Если выпало чётное количество орлов, то одним переворотом можно сделать так, чтобы монета на нужной коробке лежала отличной от всех стороной. Если нечётное, то для каждой коробки придумать комбинацию 0000,0Х0Х,00ХХ,0ХХ0. Где Х и 0 могут быть как орёл и решка, так и решка и орёл
Для случая, когда изначально чётное число орлов (и решек), можно предложить простое "практическое" решение (как писали выше, в случае нечётного изначального числа орлов Пайпер и Алекс могут мысленно дополнительно перевернуть какую-то одну определённую монету).
В этом решении, когда Алекс заходит в камеру с коробками, она видит, что ровно на одной из коробок монета лежит не той стороной, что на других. Именно в этой коробке и лежит бумажка.
Пайпер же перед выбором монеты просто делает мысленный перебор: "Что будет, если я переверну первую монету", "Что будет, если я переверну вторую монету" и т.д. Из четырёх возможных исходов она выбирает тот, в котором на коробке с бумажкой окажется отличающаяся от других монета (ровно один из возможных переворотов даст нужную комбинацию).
Доказательство, что это работает: если изначально орлов (как и решек) чётное количество, то после любого переворота станет нечётное количество орлов (как и решек). А в случае четырёх монет это может означать только одну монету одного вида и три монеты другого вида. Таким образом, у Пайпер имеется четыре возможных итоговых варианта вида "одна монета отличается от других". Осталось убедиться, что "отличающаяся" монета во всех четырёх вариантах разная - а это действительно так, потому что нельзя из одной и той же комбинации орлов (О) и решек (Р) получить одним переворотом, например, ОРОО, а другим РОРР - у них слишком много отличающихся позиций (ну и тем более нельзя двумя разными переворотами получить две одинаковые комбинации).
Просто запоминаем 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 — орёл)
И выкладываем одну из этих комбинаций монетами (их все можно получить переложив одну монету)
Занимательные задачки: побег из тюрьмы