Comments 65
Главное условие решения задачи — заключёнными должны быть два математика-программиста)
Так-то здорово.
Так-то здорово.
А инженеры бы заметили, что тюремщик почему-то всегда кладёт монеты вверх лысиной и птичкой.
Вот-вот.
Монета может касаться какой-либо одной стороны клетки или каких-либо двух сторон. Всего восемь положений, закодируем ими столбец.
Направление верха монеты с шагом в 45° кодирует номер строки.
Монета может касаться какой-либо одной стороны клетки или каких-либо двух сторон. Всего восемь положений, закодируем ими столбец.
Направление верха монеты с шагом в 45° кодирует номер строки.
Я наверно уже больше инженер чем математик, потому что первым делом пришло в голову решение, использующее готовую библиотечную функцию, но при этом дающую вероятность спасения в 63% (1 — 1/e).
Интереса ради, даю и такое решение.
Пусть у нас есть какая-то «хорошая» хэш-функция из состояния доски в число от 1 до 64. Тогда мы можем передавать нашему другу информацию путём изменения состояния доски так, чтобы результатом хеширования была загаданная тюремщиком клетка.
Мы можем выбрать одно из 64 состояний доски. Вероятность того что ни одно из них не даст нужный хеш (при условии что хеш функция «хорошая») равна (1-1/64)^64 что примерно равно 1/e = 37%.
В качестве хеш-функции можно взять младшие 6 бит от sha256.
Интереса ради, даю и такое решение.
Пусть у нас есть какая-то «хорошая» хэш-функция из состояния доски в число от 1 до 64. Тогда мы можем передавать нашему другу информацию путём изменения состояния доски так, чтобы результатом хеширования была загаданная тюремщиком клетка.
Мы можем выбрать одно из 64 состояний доски. Вероятность того что ни одно из них не даст нужный хеш (при условии что хеш функция «хорошая») равна (1-1/64)^64 что примерно равно 1/e = 37%.
В качестве хеш-функции можно взять младшие 6 бит от sha256.
Минут за 20 у меня получилось почти такое же решение, как в статье. Только вместо фразы «Всё, что нам нужно — найти нужную монету, переворачивание которой изменит комбинацию битов чётности таким образом, чтобы получилось необходимое число (двоичную запись номера «магической» клетки).» была явная формула:
пусть c[k]=0 для орла и 1 для решки, а тюремщик задумал клетку q. Считаем s=XOR(c[k]*k)^q (XOR берётся по всем k=0..63), и переворачиваем монету на клетке s. Для полученной доски будет XOR(c[k]*k)=q, что нам и нужно.
пусть c[k]=0 для орла и 1 для решки, а тюремщик задумал клетку q. Считаем s=XOR(c[k]*k)^q (XOR берётся по всем k=0..63), и переворачиваем монету на клетке s. Для полученной доски будет XOR(c[k]*k)=q, что нам и нужно.
UFO just landed and posted this here
Если вы переворачиваете монету, это один бит информации.Эта неверная фраза нужна только для того, чтобы сбить с толку: на самом деле у нас куда больше, чем один бит информации, потому что информацию передает и то какая монета была перевернута.
Прочитал 2 раза и понял, что я был бы обречен)
Массив монет — это строка для хэш-функции. Результат хэширования — номер клетки. Задача — подобрать такую функцию (изначально) и такое расположение монет (переворотом одной в ходе решения задачи), чтобы результат был достижим во всех случаях, и результат хэш-функции однозначно указывал на номер клетки. Стало понятнее?
Я как-то криво читал условие задачи, что ли…
Мы переворачиваем одну любую монету и наш подельник должен опознать её? Или таки он должен опознать ту клетку, на которую тюремщик указал?
Мы переворачиваем одну любую монету и наш подельник должен опознать её? Или таки он должен опознать ту клетку, на которую тюремщик указал?
Если доска без маркировки A-H 1-8, то есть четыре возможных начала отсчёта клеток. Если с ними — то два варианта. Так что ещё нужно договориться, например, что нулевая клетка — верхня левая, если смотреть от двери.
Теперь представьте, что ваш товарищ — выдающийся арабский математик. Если бы не этот факт, вы бы определили, что левый верхний угол — первый. Вы можете вспомнить, что он читает справа налево, или он может вспомнить обратное про вас. Внимание, вопрос: правильно ли вы сделали, что решили, что система кодирования будет соответствовать тому, кто первым зашёл в комнату?
Обобщением этой задачи занимается стеганография.
Еще можно вспомнить про коды Хэмминга и порождающие полиномы, чтобы вычисления отличались минимальной сложностью. Если доска — битовая строка, то подойдет CRC6.
Еще можно вспомнить про коды Хэмминга и порождающие полиномы, чтобы вычисления отличались минимальной сложностью. Если доска — битовая строка, то подойдет CRC6.
Кажется, недостаточно понятно выразился.
Стеганография здесь при том, что если число клеток шахматной доски увеличить, то получится растр. Изменение цвета одной точки мало скажется на рисунке, но позволит изменить его сигнатуру так, чтобы передать нужную информацию.
Код Хэмминга при том, что если последние шесть клеток доски отвести под контрольные символы, то их можно вычислить исходя из расположения первых 58 монет, чтобы поксоренные номера аверсов всех монет давали в итоге 0. Если на такой доске перевернуть одну монету, то поксоренные номера аверсов дадут номер перевернутой монеты. Так устроены коды, исправляющие ошибки. То есть у кодов Хэмминга и приема решения данной задачи общая математика.
Порождающие полиномы при том, что контрольные символы можно считать не только через операцию XOR номеров единиц, но и используя регистр сдвига с обратными связями, положение которых определяется специальным полиномом (подойдет не любой). Это может быть выгоднее при расчетах на аппаратном уровне. То есть математика в этой задаче еще более интересная, чем может показаться на первый взгляд.
А так, конечно, нумеруем клетки, ксорим номера аверсов и загаданный номер, результат укажет на номер клетки, монету на которой требуется перевернуть, тогда напарник, поксорив номера аверсов, получит номер загаданной клетки.
Стеганография здесь при том, что если число клеток шахматной доски увеличить, то получится растр. Изменение цвета одной точки мало скажется на рисунке, но позволит изменить его сигнатуру так, чтобы передать нужную информацию.
Код Хэмминга при том, что если последние шесть клеток доски отвести под контрольные символы, то их можно вычислить исходя из расположения первых 58 монет, чтобы поксоренные номера аверсов всех монет давали в итоге 0. Если на такой доске перевернуть одну монету, то поксоренные номера аверсов дадут номер перевернутой монеты. Так устроены коды, исправляющие ошибки. То есть у кодов Хэмминга и приема решения данной задачи общая математика.
Порождающие полиномы при том, что контрольные символы можно считать не только через операцию XOR номеров единиц, но и используя регистр сдвига с обратными связями, положение которых определяется специальным полиномом (подойдет не любой). Это может быть выгоднее при расчетах на аппаратном уровне. То есть математика в этой задаче еще более интересная, чем может показаться на первый взгляд.
А так, конечно, нумеруем клетки, ксорим номера аверсов и загаданный номер, результат укажет на номер клетки, монету на которой требуется перевернуть, тогда напарник, поксорив номера аверсов, получит номер загаданной клетки.
Да, я тоже про код Хемминга впомнил когда задачу прочитал. Но напрямую его тут применить нельзя, т.к. с помощью 6 контрольных разрядов можно прокодировать только 57 информационных разрядов — на один меньше чем надо.
Похоже нужно брать 57 информационных разрядов, 6 контрольных — и ещё одну клетку (можно присвоить ей индекс 0) как «резерв», не участвующий в коде. При этом если второй игрок видит что код хемминга указывает на отсутствие ошибок, то загадана нулевая клетка.
Похоже нужно брать 57 информационных разрядов, 6 контрольных — и ещё одну клетку (можно присвоить ей индекс 0) как «резерв», не участвующий в коде. При этом если второй игрок видит что код хемминга указывает на отсутствие ошибок, то загадана нулевая клетка.
Первое решение у меня так и выглядело. Мысленно переворачиваем клетку, задуманную тюремщиком. Проверяем код Хемминга для позиций 1-63. Если он показывает, что ошибка есть, исправляем её. В противном случае переворачиваем клетку 64. Партнёр поступает так же (без этапа виртуального переворачивания). Но через xor это формулируется проще.
Я так понял, что доска с маркировкой (либо маркировку «назначают» при обсуждении, как описано в комментах выше). Почему тогда нельзя заранее договориться выбирать клетку A1? Я определённо что-то не понимаю.
Все просто.
Двум обреченным надо просто договориться, что волшебная клетка будет слева, ну или справа, от монеты которую перевернет первый. Первый же, переворачивает монету на гурт.
Двум обреченным надо просто договориться, что волшебная клетка будет слева, ну или справа, от монеты которую перевернет первый. Первый же, переворачивает монету на гурт.
Сам не математик и это было первое решение, которое пришло в голову при прочтении условия.
переворачивает монету на гурт.1. Перевернуть — значит «повернуть на 180°», т.е. с аверса на реверс или наоборот. Либо повернуть на 180° горизонтально. Или вы когда оладьи переворачиваете — ещё и на ребро их ставите?
2. Не каждую монету можно поставить на ребро. Тем более, так, чтобы она на нём устойчиво простояла до прихода напарника.
3. Никто не обещал строго горизонтальной или хотя бы устойчивой поверхности, чтобы поставленная вертикально монета не укатилась и не упала.
И напоследок: Вот договоритесь вы «слева от стоящей монеты», а тюремщик ткнёт в крайнюю правую, что тогда? Тогда уж договаривайтесь ставить сразу саму монету, выбранную тюремщиком.
Таких кодов можно придумать очень много. Например, присвоим каждой клетке какое-нибудь уникальное целое число 
, где i — индекс клетки, тоже от 0 до 63. Вычислим 
, где 
, если монета лежит реверсом, иначе 1. Это и будет индексом нужной монеты. Можно легко заметить, что перевернув одну монету можно изменить это число на любое из диапазона [0;63].
Кстати, код с четностью — это частный случай этого кода.
, где i — индекс клетки, тоже от 0 до 63. Вычислим , где , если монета лежит реверсом, иначе 1. Это и будет индексом нужной монеты. Можно легко заметить, что перевернув одну монету можно изменить это число на любое из диапазона [0;63].Кстати, код с четностью — это частный случай этого кода.
С обычной суммой не пройдёт. Допустим, alpha_i=i для всех i=0..63, c_1=1, остальные c_i=0. Тогда n=1. Как вы превратите его в 2?
Видимо, под c*alpha тут надо понимать alpha, если с=0, и побитовое отрицание alpha, если c=1. Или умножение с с=-1 для реверса, +1 для аверса.
Да, действительно чушь написал. Уже одно то, что одна из клеток ни на что не влияет (та, которая с alpha_i = 0) это показывает. Конечно, должно быть по сумме на разряд.
я думаю не чушь, а вполне интуитивное и простое решение. Достаточно в этой формуле правильно определить две операции сложения и вычитания. В данном случае для обоих подходит побитовый XOR.
Нулевая клетка тоже нужна, потому что если сумма окажется той что нужно, то придётся переворачивать нулевую клетку, от которой сумма не изменится, так как XOR(x,0) == x
Нулевая клетка тоже нужна, потому что если сумма окажется той что нужно, то придётся переворачивать нулевую клетку, от которой сумма не изменится, так как XOR(x,0) == x
Напомнило похожую задачу, где первом заключенному дают 5 случайных карт из колоды в 52 карты, а затем в комнату запускают второго. Первый в определённом порядке показывает второму 4 своих карты, после этого второй должен угадать пятую карту.
4 карты можно показать 24 способами (меняя только порядок карт). значит можно указать только на 24 из оставшихся 48 карт. Нужен еще 1 бит информации. Или все-таки он показывает 5 карт, и только одну показывает рубашкой ко второму (которая может быть на 1-5 позиции)?
или вообще можно показать карту боком? =)
Не пишу про переворот карты, так как ему могут выпасть все карты с картинками (дамы-валеты-короли), которые вроде как симметричны.
или вообще можно показать карту боком? =)
Не пишу про переворот карты, так как ему могут выпасть все карты с картинками (дамы-валеты-короли), которые вроде как симметричны.
Дело в том, что первый может выбирать, какая карта останется пятой (скрытой). Всё честно, никаких трюков с рубашками, поворотами, боками, итд.
А можете рассказать правильное решение задачи? Можно в личку чтобы не спойлерить для других.
Кажется, так. Не знаю, есть ли другие хорошие решения
Насколько я помню, решение такое.
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 к значению первой карты, и говорит ответ — карта той же масти, что и первая, но с вычисленным значением.
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 к значению первой карты, и говорит ответ — карта той же масти, что и первая, но с вычисленным значением.
например, так
Первой картой показывается масть скрытой карты, оставшимися тремя картами по старшинству перестановки (123<132<213<...<321) кодируется положительный сдвиг (от 1 до 6) по номиналу от первой карты.
Например, первая карта Дама пик, следующие три карты кодируют число 6, тогда скрытая карта Д+6 = 5 пик.
Доказательство, что это всегда работает, — самостоятельно :)
Как выйти из тюрьмы:
1) Обслюнявить монету. Напарник по уровню альбедо легко ее вычислит. Даже на глаз, пока влага не испарилась. Когда влага испарится, она будет светиться в УФ освещении.
2) Подержать монету подмышкой. Она будет светиться в тепловизоре какое-то время
3) Отполировать монету о шевелюру.
4) Не попадать в тюрьму
1) Обслюнявить монету. Напарник по уровню альбедо легко ее вычислит. Даже на глаз, пока влага не испарилась. Когда влага испарится, она будет светиться в УФ освещении.
2) Подержать монету подмышкой. Она будет светиться в тепловизоре какое-то время
3) Отполировать монету о шевелюру.
4) Не попадать в тюрьму
Мне одному кажется, что подобные вычисления по нахождению опорной монеты для изменения чётности доски в уме не сделать? Или зомби съели мои мозги?
Если использовать деление доски на области и подсчёт аверсов в каждой из них, то сделать можно. Но это будет довольно долго.
Например, тюремщик задумал монету в 4-м столбце (как на рисунке). Считаете число аверсов по столбцам (интересует только чётность): ЧНННЧЧНЧ. После мысленного переворота монеты на магической клетке получится ЧННЧЧЧНЧ. Нам нужно, чтобы маски 00001111, 00110011 и 01010101 давали чётное число монет. Так что надо перевернуть монету в столбце, который входит в первую и третью маски и не входит во вторую, т.е. в 6-м столбце. Со строками всё ещё проще. Получается 8-я.
Уже когда я это сосчитал, увидел, что клетка (6,8) обведена зелёным :)
Думаю, что после небольшой тренировки мозг сам запомнит 32 «хороших» маски строк и столбцов, и будет сразу подсказывать ближайшую подходящую.
Например, тюремщик задумал монету в 4-м столбце (как на рисунке). Считаете число аверсов по столбцам (интересует только чётность): ЧНННЧЧНЧ. После мысленного переворота монеты на магической клетке получится ЧННЧЧЧНЧ. Нам нужно, чтобы маски 00001111, 00110011 и 01010101 давали чётное число монет. Так что надо перевернуть монету в столбце, который входит в первую и третью маски и не входит во вторую, т.е. в 6-м столбце. Со строками всё ещё проще. Получается 8-я.
Уже когда я это сосчитал, увидел, что клетка (6,8) обведена зелёным :)
Думаю, что после небольшой тренировки мозг сам запомнит 32 «хороших» маски строк и столбцов, и будет сразу подсказывать ближайшую подходящую.
Очень интересная задача. Вот мое решение.
Понятно, что нужно передать произвольные 6 бит. Сразу же возникла идея разбить доску на 4 квадранта (Рис. 1).
Если взять XOR двух нижних квадрантов, а потом двух левых, то наш друг может передать произвольные 2 бита, меняя один бит в любом месте одного конкретного квадранта. Таким образом мы будем ограничены конкретной областью 4х4 для переворачивания монеты.
Применем тот же способ для всех четырех получившихся квадратнов, то есть в каждом из них должно быть по 4 области: «оранжевая», «синяя», «смешанная» и «белая» (Рис.2 ). Вычислив «оранжевый» и «синий» XOR мы можем передать следующие 2 бита, и ограничиваемся областью 2х2.
Последние 2 бита зашифруем аналогично (Рис. 3).
Понятно, что нужно передать произвольные 6 бит. Сразу же возникла идея разбить доску на 4 квадранта (Рис. 1).
Если взять XOR двух нижних квадрантов, а потом двух левых, то наш друг может передать произвольные 2 бита, меняя один бит в любом месте одного конкретного квадранта. Таким образом мы будем ограничены конкретной областью 4х4 для переворачивания монеты.
Применем тот же способ для всех четырех получившихся квадратнов, то есть в каждом из них должно быть по 4 области: «оранжевая», «синяя», «смешанная» и «белая» (Рис.2 ). Вычислив «оранжевый» и «синий» XOR мы можем передать следующие 2 бита, и ограничиваемся областью 2х2.
Последние 2 бита зашифруем аналогично (Рис. 3).
8x8 однобитных клеток — это же QR-код!
Поначалу не мог понять — что же должен сделать второй заключённый? Про это как бы чётко не написано, хотя очевидно, с другой стороны. Но потом прояснилось: 1) посмотреть на доску 2) вычислить её чётность 3) получившееся шестизначное число в двоичной системе счисления перевести в десятеричную 4) это и есть номер «магической» клетки. Может быть, кто-то споткнётся в этом месте, как я, поэтому подчеркну этот момент :)
А что если тюремщик знает о решении, и сразу располагает монеты так, что они уже указывают на магическую клетку?
А монету то переворачивать обязательно, как я понял. Упс…
А монету то переворачивать обязательно, как я понял. Упс…
правильно ли я понимаю что всех повесят если хитрый тюремщик повернет между выходом первого заключенного и входом второго доску на 90 градусов? уже судя по условию задачи становится ясно что тюремщик неистово беспределит, я бы не доверял ему.
Если тюремщик осознает всю суть задачи и также способен ее решить то он не тем в жизне занимается :) или если заключенные решают то казнят тюремщика и назначат заключенных новыми тюремщиками? или имея 'судимость' спасвшимся парням уже не найти норм работы и помыкавшись они возвращаются в тюрьму работать тюремщиками? както вселенная слабо проработана, но механика игры интересная :)
Напомнило старый фокус.
Подопытному предлагается задумать (записать) число.
Затем предлагается выполнить над ним серию простых арифметических операций (как правило, деление/умножение на небольшое число).
После чего фокусник называет задуманное/записанное число, НЕ СПРАШИВАЯ ПОЛУЧЕННОГО ЧИСЛА. (В принципе, можно предложить записать полученное число, проделать с этой бумажкой некие манипуляции (например, сжечь...), но это уже для антуража).
Суть, в том, что фокусник наблюдает — сколько времени/усилий потребовалось испытуемому на выполнение каждого действия. Из чего, в принципе, каждый раз можно вытянуть бит информации (например, четное число на 2 будет делиться БЫСТРЕЕ).
Причем, умственные способности испытуемого непринципиальны, т.к. анализируется ОТНОСИТЕЛЬНОЕ время, потраченное на вычисления.
Построить удобную (и неочевидную для испытуемого) последовательность заданий, в принципе, несложно. Для особо одаренных испытуемых можно добавить отвлекающего антуража…
Подопытному предлагается задумать (записать) число.
Затем предлагается выполнить над ним серию простых арифметических операций (как правило, деление/умножение на небольшое число).
После чего фокусник называет задуманное/записанное число, НЕ СПРАШИВАЯ ПОЛУЧЕННОГО ЧИСЛА. (В принципе, можно предложить записать полученное число, проделать с этой бумажкой некие манипуляции (например, сжечь...), но это уже для антуража).
Суть, в том, что фокусник наблюдает — сколько времени/усилий потребовалось испытуемому на выполнение каждого действия. Из чего, в принципе, каждый раз можно вытянуть бит информации (например, четное число на 2 будет делиться БЫСТРЕЕ).
Причем, умственные способности испытуемого непринципиальны, т.к. анализируется ОТНОСИТЕЛЬНОЕ время, потраченное на вычисления.
Построить удобную (и неочевидную для испытуемого) последовательность заданий, в принципе, несложно. Для особо одаренных испытуемых можно добавить отвлекающего антуража…
Спасибо, и задачка интересная и перевод качественный: по мере чтения возникал вопрос, обязан ли узник переворачивать монету. Сначала думал, что перевод неточный — ан нет, в оригинале в условии та же неоднозначность.
Впрочем, для предложенного решения этот вопрос в итоге оказался не принципиальным :)
Впрочем, для предложенного решения этот вопрос в итоге оказался не принципиальным :)
Я эту задачу решил немного по своему а потом уже нашел ее на хабре. Мое решение мне кажется проще и понятнее (все комменты не читал, надеюсь, никто его еще не привел), оно отталкивается от координат:
Каждая монета на доске имеет координаты по X и по Y от 0 до 7, то есть для передачи одной координаты достаточно 3 бита информации.
Дальше договариваемся какое состояние монет будет базовым, пусть это будет например реверс. Записываем в столбик координаты всех реверсов, которые нам разложил тюремщик, в двоичном виде и xor-им их друг с другом:
X Y
001 101
100 101
111 000
000 101
ит.д…
-----XOR---------
MMM MMM (результат xor по координатам)
В результате получаем некий набор бит ("маска" доски). А нам надо добиться того, чтобы в результате у нас получились координаты загаданной клетки, чтобы наш друг придя на испытание сделал ту же саму операцию и в результате узнал координаты клетки, загаданной тюремщиком. Для этого мы должны еще добавить в список для xor координаты загаднной тюремщиком клетки. В итоге получаем координаты клетки которую мы должны перевернуть, это все.
Если мы посчитаем новую маску (после переворота клетки), то она будет нулевой, а если мы посчитаем ее без клетки загаданной тюремщиком, то как раз получим ее координаты.
Еще интересная особенность получается — клетку с координатами (0,0) можно не переворачивать )
Каждая монета на доске имеет координаты по X и по Y от 0 до 7, то есть для передачи одной координаты достаточно 3 бита информации.
Дальше договариваемся какое состояние монет будет базовым, пусть это будет например реверс. Записываем в столбик координаты всех реверсов, которые нам разложил тюремщик, в двоичном виде и xor-им их друг с другом:
X Y
001 101
100 101
111 000
000 101
ит.д…
-----XOR---------
MMM MMM (результат xor по координатам)
В результате получаем некий набор бит ("маска" доски). А нам надо добиться того, чтобы в результате у нас получились координаты загаданной клетки, чтобы наш друг придя на испытание сделал ту же саму операцию и в результате узнал координаты клетки, загаданной тюремщиком. Для этого мы должны еще добавить в список для xor координаты загаднной тюремщиком клетки. В итоге получаем координаты клетки которую мы должны перевернуть, это все.
Если мы посчитаем новую маску (после переворота клетки), то она будет нулевой, а если мы посчитаем ее без клетки загаданной тюремщиком, то как раз получим ее координаты.
Еще интересная особенность получается — клетку с координатами (0,0) можно не переворачивать )
А как рассчитывается четность доски? Я минут 10 проверял количество аверсов в указаных регионах и серое число под доской не совпадает совершенно.
Sign up to leave a comment.
Задача о 64 монетах, двух заключённых и одной шахматной доске