Как освободиться из тюрьмы

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

Ответы

Ответ 1

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

Пронумеровываем все камни в соответствии с их позицией. Т.е., например, камень 
клетке 0x0 будет иметь позицию 0, а камень в клетке 16x16 позицию 255
Для всех позиций камней на поле применяем XOR (исключающее ИЛИ) и получаем на выходе некоторое произвольное число от 0 до 255.
Если число из п.2 совпадает с позицией на которую указал тюремщик, то переходим к п.5
Иначе еще раз применяем XOR для полученного в п.2 числа и позиции на которую указа
тюремщик. Результирующее число будет позицией той клетки в которой мы и будем менять состояние:
Если в клетке уже лежит камень, то убираем его.
Иначе добавляем камень.


Теперь когда придет второй заключенный, то проделав п.1 и п.2 он однозначно получит позицию клетки на которую указал тюремщик.


Ответ 2

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