Решение задачи 506

Условие:

Для двух узников подготовили испытание. Сначала первого приводят в комнату, в которой стоит шахматная доска. Охранник раскладывает 64 монеты по клеткам (какие-то орлом вверх, какие-то решкой). Далее он загадывает любую клетку. Первый узник обязан перевернуть ровно одну монету, после чего его выводят. Потом заводят второго узника и он, глядя на расположение монет, должен точно назвать загаданную охранником клетку. Как нужно договориться узникам заранее, чтобы наверняка пройти испытание?

Решение:

Сначала узники должны заменить орлы и решки на единицы и нули соответственно. То есть клетки доски теперь ассоциируются с единицами и нулями. Далее все операции будут происходить по модулю два (0 + 0 = 0, 1 + 0 = 0 + 1 = 1, 1 + 1 = 0).

Закодируем каждую клетку доски шестью битами (главное, чтобы у узников было одна и та же кодировка). Рассмотрим шесть наборов клеток: в i-ый набор попадают клетки, у которых на i-ом месте в коде стоит единица. Например, клетка с кодом 111111 попадет во все наборы, клетка с кодом 000000 - ни в один.

Для каждого набора клеток можно посчитать сумму чисел, которые написаны на них. Заметим, что переворачивая монету, мы меняем суммы чисел на противоположные для наборов, в которые входит клетка с этой монетой.

Имеем следующую тактику. Первый узник знает код клетки. Ему надо сделать так, чтобы суммы в наборах образовывали тот же код. Почему это всегда можно сделать? Обозначим код клетки через x, а суммы в наборах через y. Пусть эти коды отличаются на позициях i1, i2, ..., ik. Рассмотрим код длины шесть с единицами на этих же позициях и нулями на остальным. Найдем клетку с этим кодом. Эта клетка как раз входит в наборы i1, i2, ..., ik. Поэтому если перевернуть монету на ней, то суммы в наборах станут равны x. Второму узнику надо посчитать суммы в наборах и указать на клетку с полученными кодом.