Задача о 64 монетах, двух заключённых и одной шахматной доске

Задача о 64 монетах, двух заключённых и одной шахматной доске

1300

Перевод незначительно сокращён и переработан, отчасти в силу того, что некие фразы я не сумел перевести/осознать. Примечания переводчика: так как я далёк как от арифметики, так и от британского языка, в переводе наверное находятся маленькие некорректности и грубые ошибки , так что замечания в личном сообщении/комменты приветствуются.
На иллюстрации выше слева аверс (head), справа реверс (tail). Уникальные обозначения сторон монеты head/tail я заменил на аверс/реверс, чтоб не вносить неурядицу русскоязычными орёл/решка.

Спасение нереально?
Это одна из тех обычных загадок о заключённых, в которых вы приговорены к погибели и сможете спастись, лишь раз докажете свои умственные возможности тюремщику. Раз вы его выполните, вы оба будете освобождены. Ваш тюремщик дает для вас испытание. Вы и ваш друг были заключены в тюрьму.

Правила:

Тюремщик отводит вас в отдельную камеру. В камере находятся шахматная доска и банка с 64 монетами.
Раз вы попытаетесь вмешаться в процесс раскладки монет, это повлечёт немедленную погибель. Он помещает монеты произвольно — некие будут обращены ввысь аверсом, некие — реверсом (либо все будут аверсом, либо реверсом, вы понятия не имеете, всё на усмотрение тюремщика). Вы сможете лишь глядеть. Раз вы попытаетесь принудить, порекомендовать либо уверить тюремщика хоть каким методом — немедленная погибель. Тюремщик берёт монеты по одной и кладёт их на каждую клеточку доски.
Когда все монеты будут разложены, тюремщик укажет на одну из клеток и произнесет: «Эта!» Указанная клеточка — «магическая» — ваш ключ к свободе.
Это единственное изменение, которое для вас разрешено сделать в раскладке тюремщика. Лишь одну, но это может быть неважно какая монета на ваш выбор. Тюремщик разрешит для вас перевернуть одну монету на доске.
Раз вы попытаетесь бросить какие-или сообщения либо подсказки для вашего друга… да, вы угадали, немедленная погибель! Потом вы будете выведены из комнаты.
Тюремщик приведёт вашего друга в комнату.
Ваш друг должен будет осмотреть доску (трогать запрещено) и решить, где, на его взор, размещена «магическая» клеточка.
У него лишь одна попытка. Исходя из расположения монет, он должен указать на клеточку и огласить: «Эта!»
Раз ошибочно — вас обоих казнят. Раз он укажет правильно, вы оба будете помилованы и немедля освобождены.
Тюремщик разъясняет эти правила для вас обоим заблаговременно и даёт время посовещаться, чтоб создать стратегию.

Может быть ли создать стратегию?
Мы не можем влиять на тюремщика, раскладка монет может быть неважно какая, и мы понятия не имеем, на какую клеточку тюремщик укажет (практически, он сам, может быть, не знает, какую клеточку выберет). На 1-ый взор, эту задачку нереально решить.

26 вероятных ответов. Раз вы переворачиваете монету, это один бит инфы. Нам необходимо 6 битов инфы, чтоб точно идентифицировать клеточку. Задумайтесь, раз друг заходит в комнату и лицезреет 63 аверса и 1 реверс, он не может знать, что единственный реверс — это монета, которые вы перевернули, либо перед вами была доска с 62 аверсами и 2 реверсами, и вы перевернули один реверс! 64 клеточки, на которые он может указать. Так как мы не можем передать состояние доски «до», у нашего друга нет способности указать, какая монеты была перевёрнута.

Может быть ли передать 6 битов инфы переворачиванием одной монеты?
Есть стратегия, позволяющая для вас спастись со 100% вероятностью независимо от раскладки монет и положения «магической» клеточки. Решение не предполагает какого-или мошенничества либо уловок, оно чисто математическое.

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

Две клеточки
Есть 4 вероятных варианта расположения монет (А — аверс, Р — реверс): РР, АА, РА, АР. Представьте, что у нас доска всего c 2-мя клеточками.

Тюремщик может выбрать в качестве «магической» как первую клеточку, так и вторую.
Вероятные варианты: Заблаговременно мы договариваемся о одном правиле — раз тюремщик показывает на первую клеточку (белоснежную), то нужно сделать так, чтоб на первой клеточке был аверс.

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

Это подсказка моему другу, что «магическая» клеточка — не 1-ая. Аналогично, раз тюремщик укажет на вторую клеточку, я сделаю так, чтоб на первой клеточке был НЕ аверс.

По нашему правилу это значит, что тюремщик избрал вторую клеточку. Во всех вариантах на первой клеточке не аверс.

Неувязка решена!

Индукция
Арифметики (и некие программеры) произнесут для вас, что это всё, что нам необходимо, чтоб доказать, что решение задачки может быть. Раз мы можем закодировать один бит инфы, используя две клеточки, то с помощью математической индукции мы можем подтвердить, что может быть закодировать 2 бита в 4 клетах, 3 — в 8 … 6 битов — в 64 клеточках.

Двоичное представление
Раз мы промаркируем клеточки от 0 (верхняя левая) до 63 (нижняя правая) в двоичном представлении, мы сможем показать, частью какого вложенного множества любая клеточка является.

Единица в хоть какой позиции указывает, что клеточка находится в одной половине множества, ноль — в иной. Любая цифра представляет множество, к которому клеточка относится. Число в нижнем левом углу показывает номер клеточки в двоичной записи. В оригинале статьи расположено интерактивное изображение доски. По определению любая клеточка неповторима и имеет личный набор битов.

Чётность
Заместо использования 2-ух клеток как в простом примере выше мы разделим доску на разные композиции 2-ух множеств. Применим к сиим двум регионам/множествам то же правило маркировки, что и с одиночными клеточками — будем обозначать, в первом либо втором регионе находится «магическая» клеточка.

Заместо этого мы перевернём одну монету. Мы можем посчитать количество аверсов в регионе — раз их число будет нечётным, воспримет это за единицу, раз чётным — ноль. Так как регионы являются коллекциями клеток, мы не можем просто повернуть все монеты в регионе аверсом. Переворачивание одном монеты в регионе изменит число аверсов с нечётного на чётное, и напротив (прибавление/вычитание единицы к хоть какому числу инвертирует его чётность/нечётность).

Переключение из 1-го состояния в другое прибавлением либо вычитанием 1-го бита обширно употребляется в компах. Таково понятие чётности.

Чтоб поменять чётность региона, нам довольно перевернуть одну монету в нём.

Ниже изображены разные методы разделения доски, основанные на состоянии битов (степени двойки) в номере клеточки. Совмещение этих фильтров дозволяет найти одну клеточку, которую можно перевернуть, чтоб поменять чётность хоть какого/всех битов. Используя маски степеней двойки, мы можем поделить доску на регионы несколькими методами.

20 эквивалентно логическому «И» (AND) с 000001, 21 — 000010 … 25 — 100000.

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

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

Всё, что нам необходимо — отыскать подходящую монету, переворачивание которой изменит комбинацию битов чётности таковым образом, чтоб вышло нужное число (двоичная запись номера «магической» клеточки). Мы знаем, что можем перевернуть одну всякую монету, и это приведёт к изменению 1-го/пары битов числа. Для идентификации «магической» клеточки нам нужно как раз 6 битов, и мы можем закодировать их с помощью чётности.

Всё совместно
Здесь я опять отправляю читателей к интерактивной модели в статье-оригинале.

Внизу справа указан номер избранной клеточки (Target=…), слева — его двоичное представление. На левой доске можно выбрать размещение «магической» клеточки.

Доска справа указывает раскладку монет. Изображены лишь аверсы (из суждений наглядности), реверсы обозначены пустыми клеточками. Клавиша «Random» заполняет доску новеньким случайным набором монет. Клавиша «Clear» переворачивает все монеты реверсом.

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

Откуда эти значения?
Мы уже знаем, откуда взялось число под левой доской. Это просто двоичное описание клеточки, каждый бит числа указывает, находится либо нет эта монета в фильтрах-степенях двойки, изображённых выше.

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

Зеленоватое число указывает номер той клеточки, состояние которой необходимо поменять (перевернуть монету), чтоб чётность доски соответствовала хотимому номеру «магической» клеточки. Оно рассчитывается выполнением битовой операции исключающее «ИЛИ» (XOR) над своей чётностью доски и хотимым значением.

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

(A XOR B) XOR B = A

Применение XOR к числу и какому-то набору (установленных) битов инвертирует в начальном числе эти биты и сохраняет состояние других. Также, раз мы применим XOR к какому-или числу и полному набору битов (числу, состоящему из одних единиц), все биты начального числа будут инвертированы.

Конкретно потому мы употребляли оператор XOR для вычисления положения монеты. Для каждого бита чётности, независимо от того, содержит он уже верное значение, и мы желаем его сохранить (XOR c 0), либо мы желаем переключить его (XOR c 1).

Пример:
Раз номер «магической» клеточки 101001 (41) и собственная чётность доски 010101, то нам необходимо перевернуть монету в клеточке 111100 (60):

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

Математика может спасти для вас жизнь! habrahabr.ru