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

http://datagenetics.com/blog/december12014/index.html
  • Перевод


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

Спасение невозможно?


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

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

Возможно ли разработать стратегию?


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

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

Возможно ли передать 6 битов информации переворачиванием одной монеты?


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

Начало


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

Две клетки


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



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



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

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



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

Проблема решена!

Индукция


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

Двоичное представление


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

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

Чётность


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

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

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

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

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



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

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

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

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

Всё вместе


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


На левой доске можно выбрать расположение «магической» клетки. Внизу справа указан номер выбранной клетки (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, чтобы быстро посчитать собственную чётность доски. Для этого нужно один раз обойти всю доску и провести эту операцию над каждым значением (порядковым номером) клетки с аверсом.

Математика может спасти вам жизнь!

Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 65
  • +13
    Главное условие решения задачи — заключёнными должны быть два математика-программиста)
    Так-то здорово.
    • +15
      А инженеры бы заметили, что тюремщик почему-то всегда кладёт монеты вверх лысиной и птичкой.
      • +9
        Вот-вот.
        Монета может касаться какой-либо одной стороны клетки или каких-либо двух сторон. Всего восемь положений, закодируем ими столбец.
        Направление верха монеты с шагом в 45° кодирует номер строки.
        • +1
          Зачем? Заходим, одна монета повёрнута. Вот эта клетка.
          • 0
            Тюремщик может положить монеты под любым углом.
            • +3
              Но монету в левом верхнем углу точно положил ваш напарник. Потому что об этом вы договорились с ним заранее.
          • 0
            Если размер клетки не слишком сильно превосходит размер монеты, цена погрешности окажется очень болезненной.
      • +10
        Я наверно уже больше инженер чем математик, потому что первым делом пришло в голову решение, использующее готовую библиотечную функцию, но при этом дающую вероятность спасения в 63% (1 — 1/e).

        Интереса ради, даю и такое решение.

        Пусть у нас есть какая-то «хорошая» хэш-функция из состояния доски в число от 1 до 64. Тогда мы можем передавать нашему другу информацию путём изменения состояния доски так, чтобы результатом хеширования была загаданная тюремщиком клетка.

        Мы можем выбрать одно из 64 состояний доски. Вероятность того что ни одно из них не даст нужный хеш (при условии что хеш функция «хорошая») равна (1-1/64)^64 что примерно равно 1/e = 37%.

        В качестве хеш-функции можно взять младшие 6 бит от sha256.
        • +4
          Минут за 20 у меня получилось почти такое же решение, как в статье. Только вместо фразы «Всё, что нам нужно — найти нужную монету, переворачивание которой изменит комбинацию битов чётности таким образом, чтобы получилось необходимое число (двоичную запись номера «магической» клетки).» была явная формула:
          пусть c[k]=0 для орла и 1 для решки, а тюремщик задумал клетку q. Считаем s=XOR(c[k]*k)^q (XOR берётся по всем k=0..63), и переворачиваем монету на клетке s. Для полученной доски будет XOR(c[k]*k)=q, что нам и нужно.
          • –20
            Разве в такой ситуации можно полагаться на математику и статистику? В такой ситуации антропогенный фактор самый сильный будет. Истерика будет такая, что никакие логические выкладки не сработают.
          • +3
            Если вы переворачиваете монету, это один бит информации.
            Эта неверная фраза нужна только для того, чтобы сбить с толку: на самом деле у нас куда больше, чем один бит информации, потому что информацию передает и то какая монета была перевернута.
            • +7
              Более того, сам факт переворачивания монеты не несёт ни одного бита информации — потому что заранее известно что мы перевернём её.
            • +29
              Прочитал 2 раза и понял, что я был бы обречен)
              • +10
                Массив монет — это строка для хэш-функции. Результат хэширования — номер клетки. Задача — подобрать такую функцию (изначально) и такое расположение монет (переворотом одной в ходе решения задачи), чтобы результат был достижим во всех случаях, и результат хэш-функции однозначно указывал на номер клетки. Стало понятнее?
            • –5
              Я как-то криво читал условие задачи, что ли…
              Мы переворачиваем одну любую монету и наш подельник должен опознать её? Или таки он должен опознать ту клетку, на которую тюремщик указал?
              • +2
                Если доска без маркировки A-H 1-8, то есть четыре возможных начала отсчёта клеток. Если с ними — то два варианта. Так что ещё нужно договориться, например, что нулевая клетка — верхня левая, если смотреть от двери.
                • +2
                  Теперь представьте, что ваш товарищ — выдающийся арабский математик. Если бы не этот факт, вы бы определили, что левый верхний угол — первый. Вы можете вспомнить, что он читает справа налево, или он может вспомнить обратное про вас. Внимание, вопрос: правильно ли вы сделали, что решили, что система кодирования будет соответствовать тому, кто первым зашёл в комнату?
                  • 0
                    В общем договориться про индексацию.
                    • 0
                      •Тюремщик объясняет эти правила вам обоим заранее и даёт время посовещаться, чтобы разработать стратегию.
                      Так что можете попытаться успеть согласовать нумерацию.
                  • 0
                    Обобщением этой задачи занимается стеганография.
                    Еще можно вспомнить про коды Хэмминга и порождающие полиномы, чтобы вычисления отличались минимальной сложностью. Если доска — битовая строка, то подойдет CRC6.
                    • +6
                      Кажется, недостаточно понятно выразился.
                      Стеганография здесь при том, что если число клеток шахматной доски увеличить, то получится растр. Изменение цвета одной точки мало скажется на рисунке, но позволит изменить его сигнатуру так, чтобы передать нужную информацию.
                      Код Хэмминга при том, что если последние шесть клеток доски отвести под контрольные символы, то их можно вычислить исходя из расположения первых 58 монет, чтобы поксоренные номера аверсов всех монет давали в итоге 0. Если на такой доске перевернуть одну монету, то поксоренные номера аверсов дадут номер перевернутой монеты. Так устроены коды, исправляющие ошибки. То есть у кодов Хэмминга и приема решения данной задачи общая математика.
                      Порождающие полиномы при том, что контрольные символы можно считать не только через операцию XOR номеров единиц, но и используя регистр сдвига с обратными связями, положение которых определяется специальным полиномом (подойдет не любой). Это может быть выгоднее при расчетах на аппаратном уровне. То есть математика в этой задаче еще более интересная, чем может показаться на первый взгляд.
                      А так, конечно, нумеруем клетки, ксорим номера аверсов и загаданный номер, результат укажет на номер клетки, монету на которой требуется перевернуть, тогда напарник, поксорив номера аверсов, получит номер загаданной клетки.
                      • +1
                        Да, я тоже про код Хемминга впомнил когда задачу прочитал. Но напрямую его тут применить нельзя, т.к. с помощью 6 контрольных разрядов можно прокодировать только 57 информационных разрядов — на один меньше чем надо.

                        Похоже нужно брать 57 информационных разрядов, 6 контрольных — и ещё одну клетку (можно присвоить ей индекс 0) как «резерв», не участвующий в коде. При этом если второй игрок видит что код хемминга указывает на отсутствие ошибок, то загадана нулевая клетка.
                        • 0
                          Первое решение у меня так и выглядело. Мысленно переворачиваем клетку, задуманную тюремщиком. Проверяем код Хемминга для позиций 1-63. Если он показывает, что ошибка есть, исправляем её. В противном случае переворачиваем клетку 64. Партнёр поступает так же (без этапа виртуального переворачивания). Но через xor это формулируется проще.
                    • 0
                      Я так понял, что доска с маркировкой (либо маркировку «назначают» при обсуждении, как описано в комментах выше). Почему тогда нельзя заранее договориться выбирать клетку A1? Я определённо что-то не понимаю.
                      • +1
                        Наверное, потому что клетку выбирает тюремщик?

                        Когда все монеты будут разложены, тюремщик укажет на одну из клеток и скажет: «Эта!» Указанная клетка — «магическая» — ваш ключ к свободе.
                        • 0
                          Спасибо! Мои извинения за свою невнимательность.
                      • –2
                        Все просто.
                        Двум обреченным надо просто договориться, что волшебная клетка будет слева, ну или справа, от монеты которую перевернет первый. Первый же, переворачивает монету на гурт.
                        • 0
                          Сам не математик и это было первое решение, которое пришло в голову при прочтении условия.
                          • 0
                            переворачивает монету на гурт.
                            1. Перевернуть — значит «повернуть на 180°», т.е. с аверса на реверс или наоборот. Либо повернуть на 180° горизонтально. Или вы когда оладьи переворачиваете — ещё и на ребро их ставите?
                            2. Не каждую монету можно поставить на ребро. Тем более, так, чтобы она на нём устойчиво простояла до прихода напарника.
                            3. Никто не обещал строго горизонтальной или хотя бы устойчивой поверхности, чтобы поставленная вертикально монета не укатилась и не упала.
                            И напоследок: Вот договоритесь вы «слева от стоящей монеты», а тюремщик ткнёт в крайнюю правую, что тогда? Тогда уж договаривайтесь ставить сразу саму монету, выбранную тюремщиком.
                          • 0
                            Таких кодов можно придумать очень много. Например, присвоим каждой клетке какое-нибудь уникальное целое число , где i — индекс клетки, тоже от 0 до 63. Вычислим , где , если монета лежит реверсом, иначе 1. Это и будет индексом нужной монеты. Можно легко заметить, что перевернув одну монету можно изменить это число на любое из диапазона [0;63].
                            Кстати, код с четностью — это частный случай этого кода.
                            • 0
                              С обычной суммой не пройдёт. Допустим, alpha_i=i для всех i=0..63, c_1=1, остальные c_i=0. Тогда n=1. Как вы превратите его в 2?
                              • 0
                                Видимо, под c*alpha тут надо понимать alpha, если с=0, и побитовое отрицание alpha, если c=1. Или умножение с с=-1 для реверса, +1 для аверса.
                                • 0
                                  Да, действительно чушь написал. Уже одно то, что одна из клеток ни на что не влияет (та, которая с alpha_i = 0) это показывает. Конечно, должно быть по сумме на разряд.
                                  • 0
                                    я думаю не чушь, а вполне интуитивное и простое решение. Достаточно в этой формуле правильно определить две операции сложения и вычитания. В данном случае для обоих подходит побитовый XOR.
                                    Нулевая клетка тоже нужна, потому что если сумма окажется той что нужно, то придётся переворачивать нулевую клетку, от которой сумма не изменится, так как XOR(x,0) == x
                              • +1
                                Напомнило похожую задачу, где первом заключенному дают 5 случайных карт из колоды в 52 карты, а затем в комнату запускают второго. Первый в определённом порядке показывает второму 4 своих карты, после этого второй должен угадать пятую карту.
                                • 0
                                  4 карты можно показать 24 способами (меняя только порядок карт). значит можно указать только на 24 из оставшихся 48 карт. Нужен еще 1 бит информации. Или все-таки он показывает 5 карт, и только одну показывает рубашкой ко второму (которая может быть на 1-5 позиции)?

                                  или вообще можно показать карту боком? =)

                                  Не пишу про переворот карты, так как ему могут выпасть все карты с картинками (дамы-валеты-короли), которые вроде как симметричны.
                                  • 0
                                    Дело в том, что первый может выбирать, какая карта останется пятой (скрытой). Всё честно, никаких трюков с рубашками, поворотами, боками, итд.
                                    • 0
                                      А можете рассказать правильное решение задачи? Можно в личку чтобы не спойлерить для других.
                                      • 0
                                        Кажется, так. Не знаю, есть ли другие хорошие решения
                                        Насколько я помню, решение такое.
                                        1) хотя бы у двух карт масти совпадают. Будем загадывать карту этой масти.
                                        2) пронумеруем достоинства карт: 0=король, 1=туз, ..., 12 = дама
                                        3) пусть две карты одной масти имеют достоинства X и Y. Тогда либо Y=(X+K) mod 13, либо X=(Y+K) mod 13, где K=1,...,6. В первом случае загадываем Y, во втором X. Оставшуюся карту кладём первой.
                                        4) осталось закодировать число K. Это делается порядком расположения трёх оставшихся карт (о порядке мастей договариваемся заранее): 3 карты — 6 перестановок.
                                        5) партнёр смотрит карты со второй по четвёртую, по их порядку узнаёт K. Потом прибавляет K к значению первой карты, и говорит ответ — карта той же масти, что и первая, но с вычисленным значением.
                                        • 0
                                          например, так
                                          Первой картой показывается масть скрытой карты, оставшимися тремя картами по старшинству перестановки (123<132<213<...<321) кодируется положительный сдвиг (от 1 до 6) по номиналу от первой карты.

                                          Например, первая карта Дама пик, следующие три карты кодируют число 6, тогда скрытая карта Д+6 = 5 пик.
                                          Доказательство, что это всегда работает, — самостоятельно :)
                                  • 0
                                    Есть еще интересная задача про 100 узников и 100 коробок. В комментариях есть ссылка на вики
                                    • –1
                                      Как выйти из тюрьмы:
                                      1) Обслюнявить монету. Напарник по уровню альбедо легко ее вычислит. Даже на глаз, пока влага не испарилась. Когда влага испарится, она будет светиться в УФ освещении.
                                      2) Подержать монету подмышкой. Она будет светиться в тепловизоре какое-то время
                                      3) Отполировать монету о шевелюру.
                                      4) Не попадать в тюрьму
                                      • 0
                                        Мне одному кажется, что подобные вычисления по нахождению опорной монеты для изменения чётности доски в уме не сделать? Или зомби съели мои мозги?
                                        • 0
                                          Если использовать деление доски на области и подсчёт аверсов в каждой из них, то сделать можно. Но это будет довольно долго.
                                          Например, тюремщик задумал монету в 4-м столбце (как на рисунке). Считаете число аверсов по столбцам (интересует только чётность): ЧНННЧЧНЧ. После мысленного переворота монеты на магической клетке получится ЧННЧЧЧНЧ. Нам нужно, чтобы маски 00001111, 00110011 и 01010101 давали чётное число монет. Так что надо перевернуть монету в столбце, который входит в первую и третью маски и не входит во вторую, т.е. в 6-м столбце. Со строками всё ещё проще. Получается 8-я.
                                          Уже когда я это сосчитал, увидел, что клетка (6,8) обведена зелёным :)
                                          Думаю, что после небольшой тренировки мозг сам запомнит 32 «хороших» маски строк и столбцов, и будет сразу подсказывать ближайшую подходящую.
                                        • 0
                                          Очень интересная задача. Вот мое решение.
                                          Понятно, что нужно передать произвольные 6 бит. Сразу же возникла идея разбить доску на 4 квадранта (Рис. 1).



                                          Если взять XOR двух нижних квадрантов, а потом двух левых, то наш друг может передать произвольные 2 бита, меняя один бит в любом месте одного конкретного квадранта. Таким образом мы будем ограничены конкретной областью 4х4 для переворачивания монеты.

                                          Применем тот же способ для всех четырех получившихся квадратнов, то есть в каждом из них должно быть по 4 области: «оранжевая», «синяя», «смешанная» и «белая» (Рис.2 ). Вычислив «оранжевый» и «синий» XOR мы можем передать следующие 2 бита, и ограничиваемся областью 2х2.

                                          Последние 2 бита зашифруем аналогично (Рис. 3).

                                          • 0
                                            8x8 однобитных клеток — это же QR-код!
                                            • +1
                                              Поначалу не мог понять — что же должен сделать второй заключённый? Про это как бы чётко не написано, хотя очевидно, с другой стороны. Но потом прояснилось: 1) посмотреть на доску 2) вычислить её чётность 3) получившееся шестизначное число в двоичной системе счисления перевести в десятеричную 4) это и есть номер «магической» клетки. Может быть, кто-то споткнётся в этом месте, как я, поэтому подчеркну этот момент :)
                                              • 0
                                                А что если тюремщик знает о решении, и сразу располагает монеты так, что они уже указывают на магическую клетку?
                                                А монету то переворачивать обязательно, как я понял. Упс…
                                                • +2
                                                  Тогда нужно перевернуть монету, лежащую на клетке с кодом 0. Она на контрольную сумму не влияет.
                                                  • 0
                                                    Ух, точно. Спасибо.
                                                  • 0
                                                    Если я правильно понял решение, то верхняя левая клетка обладает нулевым номером и не участвует в вычислениях, поэтому ее можно переворачивать не влияя на результат
                                                    Не успел :(
                                                  • 0
                                                    правильно ли я понимаю что всех повесят если хитрый тюремщик повернет между выходом первого заключенного и входом второго доску на 90 градусов? уже судя по условию задачи становится ясно что тюремщик неистово беспределит, я бы не доверял ему.
                                                    • 0
                                                      Остаётся надеяться, что доска — с подписанными строками и рядами (1-8, A-H). А так-то он и монетки попереворачивать может, когда первый выйдет.
                                                    • 0
                                                      Если тюремщик осознает всю суть задачи и также способен ее решить то он не тем в жизне занимается :) или если заключенные решают то казнят тюремщика и назначат заключенных новыми тюремщиками? или имея 'судимость' спасвшимся парням уже не найти норм работы и помыкавшись они возвращаются в тюрьму работать тюремщиками? както вселенная слабо проработана, но механика игры интересная :)
                                                      • 0
                                                        Если общество устроено так, что математиков и программистов легче найти в тюрьме, чем на свободе, то тюремщик занимается как раз тем, чем надо. А то ещё сам в тюрьму попадёт — уже в качестве заключённого.
                                                      • 0
                                                        Напомнило старый фокус.

                                                        Подопытному предлагается задумать (записать) число.

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

                                                        После чего фокусник называет задуманное/записанное число, НЕ СПРАШИВАЯ ПОЛУЧЕННОГО ЧИСЛА. (В принципе, можно предложить записать полученное число, проделать с этой бумажкой некие манипуляции (например, сжечь...), но это уже для антуража).

                                                        Суть, в том, что фокусник наблюдает — сколько времени/усилий потребовалось испытуемому на выполнение каждого действия. Из чего, в принципе, каждый раз можно вытянуть бит информации (например, четное число на 2 будет делиться БЫСТРЕЕ).

                                                        Причем, умственные способности испытуемого непринципиальны, т.к. анализируется ОТНОСИТЕЛЬНОЕ время, потраченное на вычисления.

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

                                                        • 0
                                                          Спасибо, и задачка интересная и перевод качественный: по мере чтения возникал вопрос, обязан ли узник переворачивать монету. Сначала думал, что перевод неточный — ан нет, в оригинале в условии та же неоднозначность.
                                                          Впрочем, для предложенного решения этот вопрос в итоге оказался не принципиальным :)
                                                          • +1
                                                            Я эту задачу решил немного по своему а потом уже нашел ее на хабре. Мое решение мне кажется проще и понятнее (все комменты не читал, надеюсь, никто его еще не привел), оно отталкивается от координат:
                                                            Каждая монета на доске имеет координаты по X и по Y от 0 до 7, то есть для передачи одной координаты достаточно 3 бита информации.
                                                            Дальше договариваемся какое состояние монет будет базовым, пусть это будет например реверс. Записываем в столбик координаты всех реверсов, которые нам разложил тюремщик, в двоичном виде и xor-им их друг с другом:
                                                            X Y
                                                            001 101
                                                            100 101
                                                            111 000
                                                            000 101
                                                            ит.д…
                                                            -----XOR---------
                                                            MMM MMM (результат xor по координатам)

                                                            В результате получаем некий набор бит ("маска" доски). А нам надо добиться того, чтобы в результате у нас получились координаты загаданной клетки, чтобы наш друг придя на испытание сделал ту же саму операцию и в результате узнал координаты клетки, загаданной тюремщиком. Для этого мы должны еще добавить в список для xor координаты загаднной тюремщиком клетки. В итоге получаем координаты клетки которую мы должны перевернуть, это все.

                                                            Если мы посчитаем новую маску (после переворота клетки), то она будет нулевой, а если мы посчитаем ее без клетки загаданной тюремщиком, то как раз получим ее координаты.

                                                            Еще интересная особенность получается — клетку с координатами (0,0) можно не переворачивать )
                                                            • 0
                                                              В принципе можно и без координат обойтись, можно в столбик записывать и xor-ить номера клеток от 0 до 63, это тоже 6 бит. Тогда получим не координаты а номер клетки, которую перевернуть надо.
                                                            • 0
                                                              А как рассчитывается четность доски? Я минут 10 проверял количество аверсов в указаных регионах и серое число под доской не совпадает совершенно.

                                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.