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