23

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

Заключенные могут оговорить стратегию заранее, но после начала "игры" они не "общаются" ни каким образом. Состояние поля оба заключенных не видят до начала "игры".

Как выиграть?

LEQADA
  • 5,185
Jan Bronnikau
  • 822

2 Answers2

22

Можно поступить следующим образом:

  1. Пронумеровываем все камни в соответствии с их позицией. Т.е., например, камень в клетке 0x0 будет иметь позицию 0, а камень в клетке 16x16 позицию 255
  2. Для всех позиций камней на поле применяем XOR (исключающее ИЛИ) и получаем на выходе некоторое произвольное число от 0 до 255.
  3. Если число из п.2 совпадает с позицией на которую указал тюремщик, то переходим к п.5
  4. Иначе еще раз применяем XOR для полученного в п.2 числа и позиции на которую указал тюремщик. Результирующее число будет позицией той клетки в которой мы и будем менять состояние:
    • Если в клетке уже лежит камень, то убираем его.
    • Иначе добавляем камень.
  5. Теперь когда придет второй заключенный, то проделав п.1 и п.2 он однозначно получит позицию клетки на которую указал тюремщик.
Ilya Pirogov
  • 10,948
  • 1
    Поясните п.2. Первый аргумент операции XOR - N-ная позиция камня от 0 до 255, а второй аргумент ? – Mikola Jul 22 '12 at 11:35
  • 3
    @Mikola, смотрите, к примеру, если у нас лежат камни в позициях 1, 100 и 237, то результатом п.2 для первого заключеного будет выражение: 
    1 XOR 100 XOR 237 = 136

    Если тюремщик укажет на позицию 42, то положив камень в позицию: 136 XOR 42 = 162, второй тюремщик выполнив п.2 получит

    1 XOR 100 XOR 237 XOR 162 = 42

    Т.е. искомую позицию.

     – Ilya Pirogov Jul 22 '12 at 12:04
  • 2
    По-моему, идеально. – Spectre Jul 22 '12 at 12:28
  • @Ilya Pirogov , спасибо, теперь понятно. – Mikola Jul 22 '12 at 13:35
  • А ещё можно использовать суммирование по модулю количества полей. Будет работать и в случае произвольного количества полей (не степень 2). – sercxjo Jul 23 '12 at 07:51
  • @sercxjo, XOR - это и есть суммирование по модулю.

    Про степень 2 не понял. Этот алгоритм будет работать для произвольного числа полей. Или я не понял что вы имеете ввиду.

     – Ilya Pirogov Jul 23 '12 at 08:13
  • 1
    Не по модулю 2 а по модулю количества клеток. Пусть есть 100 клеток, три камня в клетках 1, 23, 95. Суммируем позиции камней по модулю 100: 
    (1 + 23 + 95) mod 100 = 19

    Из адреса указанного поля (42) надо вычесть эту сумму по модулю 100:

    (42 - 19) mod 100 = 23

    Итак первый заключённый кладёт камень в клетку 23.

    второй суммирует:

    (1 + 23 + 23 + 95) mod 100 = 42

    (В условиях задачи не сказано, что нельзя класть второй камень в ту же клетку)

     – sercxjo Jul 23 '12 at 09:53

  • после чего заключенный может изменить состояние одной любой клетки

    По моему, в задаче явно дается понять, что клетка может быть только в двух состояниях. В остальном понял, спасибо.

     – Ilya Pirogov Jul 23 '12 at 10:28
  • 2 @Ilya Pirogov: у вас алгоритм верный но обьяснение как-то запутанно. мне кажется так будет доступнее:

    за состояние каждого поля отвечает 1 конкретный бит. у нас всего 256 позиций. т.е. 8 байт. для того чтоб узнать изначальное расположение полей достаточно запомнить число (легче всего если преобразовать его в 10ричную систему). для того чтоб найти изменившееся поле достаточно сделать XOR текущего состояния с исходным

     – jmu Jul 23 '12 at 19:16
  • 3
    @jmu, ничего вы не поняли. Мы не ищем изменившееся поле, мы ищем клетку указанную тюремщиком. Информация, которая нам нужна - это номер клетки, её адрес. Эта информация - число от 0 до 255 - умещается в одном байте. Второй заключённый не может узнать как выглядело поле до того как первый изменил там состояние одной клетки ни какую клетку он изменил, но может посчитать контрольную сумму адресов тех камней которые он видит с помощью побитного xor. Он получит число от 0 до 255. Первый заключённый должен сделать так, чтобы у второго получился адрес указанной клетки. – sercxjo Jul 24 '12 at 08:08
  • да, затупил чуток – jmu Jul 26 '12 at 09:16
  • 3
    @Ilya Pirogov, как-то у вас много текста) 
    x - позиции исходных камней
y - позиции получившихся камней    
xor() - xor элементов массива
e - позиция изменяемой ячейки
f - позиция указанной ячейки

xor(y) = xor(xor(x), e) = f
e = xor(xor(x), f)
f = xor(y)
    – timka_s Jul 26 '12 at 11:25
  • @timka_s, нигде в условиях задачи не указано, что необходимо вывести формулу или описать алгоритм одним предложением, поэтому я расписал его так, как его, на мой взгляд, проще воспринимать. – Ilya Pirogov Jul 26 '12 at 11:36
4

Предлагаю такой алгоритм (вероятность выигрыша считайте сами).

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

Если оба числа чётные - надо изменить состояние указанной клетки.

Если одно из чисел нечётно, например для горизонтали - надо изменить состояние другой клетки на этой линии, при этом желательно выбрать клетку, у которой сумма по вертикали нечётная.

Если оба числа указанной клетки нечётные - надо найти две другии вертикали и горизонтали с нечётным числом камней и изменить состояние клетки на их пересечении, если такой клетки нет - ничего не делать.

Второй игрок должен найти горизонталь и вертикаль с нечётным количеством камней. Конечно он может ошибиться, первый игрок только уменьшает вероятность этой ошибки.

Модификация: критерий чётность/нечётность выбирается для вертикали и горизонтали отдельно из того каких линий меньше. Т.е. если меньше чётных - берём критерием чётность и т.п. Первый игрок уменьшает количество этих линий на 1.

sercxjo
  • 6,904
  • 2
  • 27
  • 57
  • Самая большая проблема - если кол-во клеток на пересечении линий с нечётным кол-вом камней больше 3-х. – Spectre Jul 22 '12 at 09:12
  • @Spectre, не понятно, объясните подробнее – sercxjo Jul 22 '12 at 09:48
  • А, понял, вы имеете в виду что остаются клетки, которые могут быть ошибочно выбраны вторым игроком. Да, если таких клеток 2 - можно одним камнем их обезвредить, а если больше, проблема останется. – sercxjo Jul 22 '12 at 10:09
  • Да, именно. – Spectre Jul 22 '12 at 10:10